Counting Integer Partitions

Problem (Integer Partitions): Given an integer $n$, in how many ways can the integer be expressed as a sum of integers?

Take I: Dynamic Programming

Let's name the function we want to compute $p(n)$. Our first stab would be to think of something like this:

1
2

p 0 = 1
p n = sum $ [p (n-x) | x <- [n,(n-1)..0]]

However, this is not quite correct. We're overcounting the partitions. (Think why)

To avoid overcounting, we instead ask: Given two integers $n$ and $k$, in how many ways can $n$ be partitioned using integers less than or equal to $k$?

1
2
3
4
5
6
7
8
9

import Data.Array

partition :: Int -> Integer
partition n = partition' ! (n, n)
    where
        partition' = listArray ((0,0),(n,n)) [p m k | m <- [0..n], k <- [0..n]]
        p _ 0 = 0
        p 0 _ = 1
        p m k = sum [partition' ! ((m-i), i) | i <- [0..(min m k)]] --this is the dp step

Take II: Generating Functions

(Influenced by Math.Combinat)

It is not hard to see that what we want is the coefficient of $n$ in $g(x) = \prod_{k}\frac{1}{1-x^k}$.

Now, consider the following sequence of power series $f_n(x)$ converging to $g(x)$.

$\frac{1}{(1-x)} = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + + \cdots \\ \frac{1}{(1-x)(1-x^2)} = 1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 + 4x^6 + 4x^7 + \cdots \\ \frac{1}{(1-x)(1-x^2)(1-x^3)} = 1 + x + 2x^2 + 3x^3 + 4x^4 + 5x^5 + 7x^6 + 8x^7 + \cdots$

In general, $f_{n+1} = f_n + x^{n+1}f_{n+1}$.

At this point, let us switch to the infinite list representations of the power series. We have:

1
2
3
4
5
6
7
8

f 0 = [1,0,0,0,0,0,0,0...]
f 1 = [1,1,1,1,1,1,1,1...]
f 2 = [1,1,2,2,3,3,4,4...]
f 3 = [1,1,2,3,4,5,7,8...]
\
--and in general,

f (k+1) == zipWith (+) (f k) (replicate (k+1) 0 ++ f (k+1))

Notice that the first $k+1$ terms of $f_{k+1}$ can be inherited from those of $f_k$, and are the same as those of $g$. To express the same idea in Haskell, we drop the first $k+1$ terms in the power series and get

1

drop (k+1) (f (k+1)) == zipWith (+) (drop (k+1) $ f k) (f (k+1))

This motivates us to exploit the lazyness of haskell and write $f_{k+1}$ in terms of $g$, which, by virtue of laziness, has been calculated to a certain extent, already.

1

f (k+1) = take (k+1) g ++ drop (k+1) (f (k+1))

Now, we have adequate background to implement g itself:

1
2
3
4
5

g = go 1 (1:repeat 0)
        where
        go k (x:xs) = x : go (k+1) ys --think of xs as drop k (f (k-1) )
            where
            ys = zipWith (+) xs (take k final ++ ys) --think of ys as drop k (f k)

It's worth appreceating that the gf solution works really fast as compared to the dynamic programming solution.

Take III: Pentagonal Number Theorem

(I'm hoping someone would explain this better in the comments section.)

Euler's Pentagonal Number Theorem suggests that the denominator of the generating function discussed above could be written as

$(1-x)(1-x^2)(1-x^3)\cdots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \cdots$

The numbers used here are Generalized Pentagonal Numbers.

It can be deduced that $p(k) = p(k - 1) + p(k - 2) - p(k - 5) - p(k - 7) + p(k - 12) + p(k - 15) - p(k - 22) - ...$ where the numbers used are generalized Pentagonal Numbers.

1
2
3
4
5
6
7

import Data.List

genpent = map (\n -> (3*n*n - n) `div` 2) ((concat.transpose) [[1..],[-1,-2..]])

partitions = 1 : go 1
  where go n = sum (zipWith (*) signs (map (\x -> partitions !! (n-x)) (takeWhile (<= n) genpent))) : go (n+1)
        signs = 1: 1: (-1) : (-1) : signs