Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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)$.

share|improve this answer
    
Are you sure this recursion relation holds true? Take $n = 5$. We know that 5 can be expressed in only one way - 5. Your function says something else. According to your function, $f(5,5) = f(0,5) +... = 0$ but it must be 1. –  Parth Thakkar Jul 24 '13 at 19:00
    
You are right. I have lost a condition. I already have corrected it. –  ILikeMath Jul 24 '13 at 19:06
    
What about $n=7$? It still fails. –  Parth Thakkar Jul 24 '13 at 19:08
    
Note $f(7,5)= f(2,5) + f(1,6) + f(0,7) = 0 + 0 + 1 = 1$. –  ILikeMath Jul 24 '13 at 19:10
1  
If you have the formula $f(n)=\sum\limits_{i = 1}^n {f(n - i)}$ then you will count duplicates. So we need only count partitions in increasing order, adding the other parameter you will reach it. –  ILikeMath Jul 24 '13 at 19:20

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?

share|improve this answer
    
Yeah, thanks for pointing out. Edited. But quite nice that someone is really going through all this - I was feeling that most people wouldn't even bother to read this. :D –  Parth Thakkar Jul 24 '13 at 18:33

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.

share|improve this answer
    
That's what I am basically doing. But I think it might become a really slow process as $n$ gets large. That's why I asked the question here - to find a better way, or maybe to optimize this method. –  Parth Thakkar Jul 24 '13 at 18:32
    
Recurrence relations often admit closed form solutions. The point here is you only keep track of how many solutions there are, not what they are, and the duplicate problem is solved for you. –  Ross Millikan Jul 24 '13 at 18:36
    
But if I don't keep track of what the solutions are, how do I know whether there are any duplicates or not? –  Parth Thakkar Jul 24 '13 at 18:37
    
If it's getting slow, it may mean that you repeatedly calculate the same partition. Make sure that you store any results you already calculated and don't calculate them again. –  celtschk Jul 24 '13 at 18:39
    
@RossMillikan Ramanujan's closed form for partitions shows (a) it is possible; (b) it is surprisingly difficult; (c) the recurrence relations are the simple way of looking at this. See also oeis.org/wiki/Partition_function –  Mark Bennet Jul 24 '13 at 18:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.