combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Safe HaskellNone
LanguageHaskell2010

Math.Combinat.Partitions.Integer.Count

Contents

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)

Counting partitions

countPartitions :: Int -> Integer Source #

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

countPartitionsInfiniteProduct :: Int -> Integer Source #

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

countPartitionsNaive :: Int -> Integer Source #

This uses countPartitions', and is (very) slow

partitionCountTable :: TableOfIntegers Source #

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] Source #

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

partitionCountListInfiniteProduct :: [Integer] Source #

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] Source #

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

partitionCountListNaive == map countPartitionsNaive [0..]

This is very slow.

Counting all partitions

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

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

countPartitionsWithKParts Source #

Arguments

:: Int

k = number of parts

-> Int

n = the integer we partition

-> Integer 

Count partitions of n into k parts.

Naive recursive algorithm.