combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Math.Combinat.Partitions.Integer.Count

Description

Counting partitions of integers.

Synopsis

# Infinite tables of integers

newtype TableOfIntegers Source #

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

Constructors

 TableOfIntegers [Array Int Integer]

# Counting partitions

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

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

This uses countPartitions', and is (very) slow

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

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

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..]

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

partitionCountListNaive == map countPartitionsNaive [0..]

This is very slow.

# Counting all partitions

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

# Counting fitting into a rectangle

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

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

# Partitions with given number of parts

Arguments

 :: Int k = number of parts -> Int n = the integer we partition -> Integer

Count partitions of n into k parts.

Naive recursive algorithm.