Math.Combinat.Partitions.Integer.Count

Counting partitions of integers.

Infinite tables of integers

newtype TableOfIntegers

A data structure which is essentially an infinite list of Integer-s, but fast lookup (for reasonable small inputs)

Constructors

TableOfIntegers [Array Int Integer]

lookupInteger :: TableOfIntegers -> Int -> Integer

makeTableOfIntegers :: ((Int -> Integer) -> Int -> Integer) -> TableOfIntegers

Counting partitions

countPartitions :: Int -> Integer

Number of partitions of n (looking up a table built using Euler's algorithm)

countPartitionsInfiniteProduct :: Int -> Integer

This uses the power series expansion of the infinite product. It is slower than the above.

countPartitionsNaive :: Int -> Integer

This uses countPartitions', and is (very) slow

partitionCountTable :: TableOfIntegers

This uses Euler's algorithm to compute p(n)

See eg.: NEIL CALKIN, JIMENA DAVIS, KEVIN JAMES, ELIZABETH PEREZ, AND CHARLES SWANNACK COMPUTING THE INTEGER PARTITION FUNCTION http://www.math.clemson.edu/~kevja/PAPERS/ComputingPartitions-MathComp.pdf

partitionCountList :: [Integer]

An infinite list containing all p(n), starting from p(0).

partitionCountListInfiniteProduct :: [Integer]

Infinite list of number of partitions of 0,1,2,...

This uses the infinite product formula the generating function of partitions, recursively expanding it; it is reasonably fast for small numbers.

partitionCountListInfiniteProduct == map countPartitions [0..]

partitionCountListNaive :: [Integer]

Naive infinite list of number of partitions of 0,1,2,...

partitionCountListNaive == map countPartitionsNaive [0..]

This is very slow.

Counting all partitions

countAllPartitions :: Int -> Integer

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

Count all partitions fitting into a rectangle. # = \binom { h+w } { h }

Counting fitting into a rectangle

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

Number of of d, fitting into a given rectangle. Naive recursive algorithm.

Partitions with given number of parts

countPartitionsWithKParts

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> Integer

Count partitions of n into k parts.

Naive recursive algorithm.