Math.Combinat.Partitions.Integer

Partitions of integers. Integer partitions are nonincreasing sequences of positive integers.

See:

• Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 3B.
• http://en.wikipedia.org/wiki/Partition_(number_theory)

For example the partition

Partition [8,6,3,3,1]

can be represented by the (English notation) Ferrers diagram:

Type and basic stuff

newtype Partition

A partition of an integer. The additional invariant enforced here is that partitions are monotone decreasing sequences of positive integers. The Ord instance is lexicographical.

Constructors

Partition [Int]

Instances

Eq Partition

Ord Partition

Read Partition

Show Partition

HasNumberOfParts Partition

class HasNumberOfParts p where

Methods

numberOfParts :: p -> Int

Instances

HasNumberOfParts Partition

HasNumberOfParts SetPartition

HasNumberOfParts NonCrossing

mkPartition :: [Int] -> Partition

Sorts the input, and cuts the nonpositive elements.

toPartitionUnsafe :: [Int] -> Partition

Assumes that the input is decreasing.

toPartition :: [Int] -> Partition

Checks whether the input is an integer partition. See the note at isPartition!

isPartition :: [Int] -> Bool

Note: we only check that the sequence is ordered, but we do not check for negative elements. This can be useful when working with symmetric functions. It may also change in the future...

fromPartition :: Partition -> [Int]

height :: Partition -> Int

The first element of the sequence.

width :: Partition -> Int

The length of the sequence.

heightWidth :: Partition -> (Int, Int)

weight :: Partition -> Int

The weight of the partition (that is, the sum of the corresponding sequence).

dualPartition :: Partition -> Partition

The dual (or conjugate) partition.

_dualPartition :: [Int] -> [Int]

elements :: Partition -> [(Int, Int)]

Example:

elements (toPartition [5,4,1]) ==
  [ (1,1), (1,2), (1,3), (1,4), (1,5)
  , (2,1), (2,2), (2,3), (2,4)
  , (3,1)
  ]

_elements :: [Int] -> [(Int, Int)]

Automorphisms

countAutomorphisms :: Partition -> Integer

Computes the number of "automorphisms" of a given integer partition.

_countAutomorphisms :: [Int] -> Integer

Dominance order

dominates :: Partition -> Partition -> Bool

q `dominates` p returns True if q >= p in the dominance order of partitions (this is partial ordering on the set of partitions of n).

See http://en.wikipedia.org/wiki/Dominance_order

Generating partitions

_partitions'

Arguments

:: (Int, Int)

(height,width)

-> Int

d

-> [[Int]]

Integer partitions of d, fitting into a given rectangle, as lists.

partitions'

Arguments

:: (Int, Int)

(height,width)

-> Int

d

-> [Partition]

Partitions of d, fitting into a given rectangle. The order is again lexicographic.

countPartitions' :: (Int, Int) -> Int -> Integer

_partitions :: Int -> [[Int]]

Partitions of d, as lists

partitions :: Int -> [Partition]

Partitions of d.

countPartitions :: Int -> Integer

allPartitions'

Arguments

:: (Int, Int)

(height,width)

-> [[Partition]]

All integer partitions fitting into a given rectangle.

allPartitions :: Int -> [[Partition]]

All integer partitions up to a given degree (that is, all integer partitions whose sum is less or equal to d)

countAllPartitions' :: (Int, Int) -> Integer

# = \binom { h+w } { h }

countAllPartitions :: Int -> Integer

Partitions with given number of parts

partitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> [Partition]

Lists partitions of n into k parts.

sort (partitionsWithKParts k n) == sort [ p | p <- partitions n , numberOfParts p == k ]

Naive recursive algorithm.

countPartitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> Integer

Sub-partitions of a given partition

isSubPartitionOf :: Partition -> Partition -> Bool

Returns True of the first partition is a subpartition (that is, fit inside) of the second. This includes equality

subPartitions :: Int -> Partition -> [Partition]

Sub-partitions of a given partition with the given weight:

sort (subPartitions d q) == sort [ p | p <- partitions d, isSubPartitionOf p q ]

_subPartitions :: Int -> [Int] -> [[Int]]

allSubPartitions :: Partition -> [Partition]

All sub-partitions of a given partition

_allSubPartitions :: [Int] -> [[Int]]

ASCII Ferrers diagrams

data PartitionConvention

Which orientation to draw the Ferrers diagrams. For example, the partition [5,4,1] corrsponds to:

In standard English notation:

 @@@@@
 @@@@
 @

In English notation rotated by 90 degrees counter-clockwise:

@  
@@
@@
@@
@@@

And in French notation:

 @
 @@@@
 @@@@@

Constructors

EnglishNotation

English notation

EnglishNotationCCW

English notation rotated by 90 degrees counterclockwise

FrenchNotation

French notation (mirror of English notation to the x axis)

Instances

Eq PartitionConvention

Show PartitionConvention

asciiFerrersDiagram :: Partition -> ASCII

Synonym for asciiFerrersDiagram' EnglishNotation '@'

Try for example:

autoTabulate RowMajor (Right 8) (map asciiFerrersDiagram $ partitions 9)

asciiFerrersDiagram' :: PartitionConvention -> Char -> Partition -> ASCII