Counting Integer Partitions

Problem (Integer Partitions): Given an integer nn, 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)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 nn and kk, in how many ways can nn be partitioned using integers less than or equal to kk?

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 nn in g(x)=k11xkg(x) = \prod_{k}\frac{1}{1-x^k}.

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

1(1x)=1+x+x2+x3+x4+x5+x6+x7++1(1x)(1x2)=1+x+2x2+2x3+3x4+3x5+4x6+4x7+1(1x)(1x2)(1x3)=1+x+2x2+3x3+4x4+5x5+7x6+8x7+ \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, fn+1=fn+xn+1fn+1f_{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+1k+1 terms of fk+1f_{k+1} can be inherited from those of fkf_k, and are the same as those of gg. To express the same idea in Haskell, we drop the first k+1k+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 fk+1f_{k+1} in terms of gg, 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

(1x)(1x2)(1x3)=1xx2+x5+x7x12x15+ (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(k1)+p(k2)p(k5)p(k7)+p(k12)+p(k15)p(k22)...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

Note by Agnishom Chattopadhyay
3 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

i don't understand programming very well, but i can see your hard work . Keep it up :) .

Sabhrant . - 3 years ago

Log in to reply

Thanks!

i don't understand programming very well

Let's change that fact.

Agnishom Chattopadhyay Staff - 3 years ago

Log in to reply

cool

Charlotte Milanese - 2 years, 11 months ago

Log in to reply

this is really cool ! I want to know more

Charlotte Milanese - 2 years, 11 months ago

Log in to reply

The Wikipedia page is a good place to start.

Agnishom Chattopadhyay Staff - 2 years, 11 months ago

Log in to reply

ok thanks I appreaciate it :)

Charlotte Milanese - 2 years, 11 months ago

Log in to reply

Can you please elaborate on the dynamic approach? Can you provide other links which can help me understand such algorithms in Haskell better? Thank you.

Atmadeep arya - 1 year, 8 months ago

Log in to reply

You can check out this wiki I wrote to understand dynamic programming

Agnishom Chattopadhyay Staff - 1 year, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...