Number of ways of partitioning a number $n$ in unique ways.

Question

Given any number $n$, what is the method of finding out how many possible ways (unique) are there in which you can partition it - with the condition that all the numbers in each 'part' must be greater than or equal to 5.

e.g. say $n = 17$

So, $17$ can be written as:

1. $17$

2. $5 + 12$ (since the least number in each part must be 5)

3. $ 6 + 11 $

4. $ 7 + 10 $

5. $ 8 + 9 $ (same as $9 + 8$)

6. $ 5 + 6 + 6 $

7. $ 5 + 7 + 7 $

So $17$ can be partitioned in $7$ ways.

The question then is, what is the algorithm to find the number of all possible ways (the ways themselves aren't important)?

My way: use DP.

Let's say the function we are gonna write is $f$.

Calculate $f(5)$ ( $= 1$), remember it. Similarly calculate $f(6)...f(9)$

Now, coming to $f(10)$ from 10, at most we can cut off $5$ and hence $10 = 5 + 5$

Do this recursively and check for duplicates.

The problem with my method: But this seems a really naive algorithm and it seems to be slow (with all the checking of duplicates).

So, I am looking for some better method.

Answer 1

Note that we need to list partitions in increasing order to avoid duplicates. It follows we need to know, in determinate instance of this proccess, the number $n$ to partition and a lower bound wich we start to partition this number. If you consider $f(n,m)$ means the number of ways to partition $n$ with numbers $\geqslant m$ in increasing order (possibly $0$ numbers if $m>n$), then a recurrence is

$f(n,m) = \sum\limits_{i = m}^n {f(n - i,i)}$ if $n\geqslant1$,

and the base case would be when $n=0$, no matter the value of $m$, the number of ways of partiton $0$ is 1. So

$f(0,m) = 1$.

Then the answer will be $f(n,5)$.

Answer 2

The question was becoming really huge and I feared people would skim the text in it. So I am adding this here (the following is quite answer-ish too!)

An interesting insight:

While working out manually for numbers till 20, I found out quite an amazing fact (which seems to hold for all integers) about repetition.

So, calculate $f$ for $ 10 $ to $15$.

$10 \to 10, 5+5$

$11 \to 11, 6+5$

...

$14 \to 14, 5+9, 6+8, 7+7$

... till $16$.

The interesting part comes here:

Consider $f(17)$

$17 \to 17$

$17 \to 5+12 \to \{ 5+6+6, 5+5+7 \}$ (using the result of 12)

$17 \to 6+11 \to \mathfrak{\{ 6+5+6 \}}$ (REPETITION using the result of 11)

$17 \to 7+10 \to \mathfrak{\{ 7+5+5 \}}$ (REPETITION using the result of 10)

$17 \to 8+9$

The thing to be noticed is (as you will see by working out manually till 20 or more maybe) is that once you get a repetition, your further attempts to expand the expandable numbers (e.g. 12,11,10 in the above cases) will be useless - all of them will be repetitions. The condition for such a thing to happen is if you go this way:

First, go downwards (that is, in the 17 example, first divide it as $5+12$ and then move downwards to $6+11$ etc.) and then for each answer you just got while going downwards, 'expand' it using the previous results.

Second, when you are expanding some number using its previously calculated partition, take the partitions of that number in the descending order.

e.g. when you are going to expand the $14$ in $20 = 6 + 14$, write $20$ as:

$20 = 6 + (7+7)$

$20 = 6 + (6+8)$

$20 = 6 + (5+9)$

etc.

I know this is quite odd, but it seems to be working. Suggestions/ideas?

Answer 3

This kind of thinking leads to recurrence relations which are a very useful way to enumerate partitions among other things. You need to be careful-I don't see how you make sure you don't count both $17=6+11=6+5+6$ and $17=5+12=5+6+6$. One way is to keep the numbers sorted. Define $F(n,k)$ as the number of partitions of $n$ into pieces of at least $k$. Then you can write $$F(n,5)=\sum_{i=5}^\infty F(n-5,i)\\F(n,6)=\sum_{i=6}^\infty F(n-6,i)$$,etc.