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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please, help me out

How to evaluate the number of ordered partitions of the positive integer 5


share|cite|improve this question
[WP link above was broken]( – user2468 Apr 7 '11 at 16:29
Note that the Wikipedia article on partitions (number theory) has to do with unordered partitions. If order matters, then the Wikipedia article to refer to is the one on compositions. – hardmath Apr 7 '11 at 17:57
up vote 13 down vote accepted

Since $5$ is a smallish number, it is reasonable to try to list all of the ordered partitions, and then count. First maybe, lest we forget, write down the trivial partition $5$. Then write down $4+1$, $1+4$. Now list all the ordered partitions with $3$ as the biggest number. This is easy, $3+2$, $2+3$, $3+1+1$, $1+3+1$, $1+1+3$. Continue. After not too long, you will have a complete list.

It so happens that for this type of problem, there is a simple general formula, which one might guess by carefully finding the number of ordered partitions of $1$, of $2$, of $3$, of $4$. And there are good ways of proving that the general formula holds. Let us deal with the case $n=5$.

Put $5$ pennies in a row, leaving a little gap between consecutive pennies. There are $4$ interpenny gaps. CHOOSE any number of these gaps ($0$, $1$, $2$, $3$, or $4$) to put a grain of rice into. Any such choice gives rise to a unique ordered partition of $5$, and all of them arise in this way. For example, the trivial partition $5$ comes from using no grain. The partition $4+1$ comes from putting a grain of rice after the $4$th penny. And so on. So there are exactly as many ordered partitions of $5$ as there are ways of choosing a SUBSET of the set of gaps. But a set of $4$ elements has $2^4$ subsets.

Or else one could attack the problem by induction. For example, let $P(n)$ be the number of ordered partitions of $n$. Now look at $P(n+1)$. Ordered partitions of $n+1$ are of two types: (i) last element $1$ and (ii) last element bigger than $1$. You should be able to see that there are $P(n)$ ordered partitions of $n+1$ of each type, meaning that $P(n+1)=2P(n)$.

But after all this fancy stuff, I would like to urge that you get your hands dirty, that you list and count the ordered partitions of $n$ for $n=1$, $2$, $3$, $4$, $5$, maybe even $6$.

share|cite|improve this answer
" You should be able to see that there are $P(n)$ ordered partitions of $n+1$ of each type" - I know I'm late, but could you be more specific about this? – bwv869 Nov 8 '13 at 0:26
If the last element is $1$, remove it, and you get an ordered partition of $n$. Moreover, all ordered partitions of $n$ arise in this way, for any ordered partition of $n$ can be extended to an ordered partition of $n+1$ by appending a $1$. So there are $P(n)$ ordered partitions of $n+1$ with last element $1$. Now take an ordered partition with last element $k\gt 1$. Replace it by $k-1$, and leave the rest alone. You get an ordered partition of $n$. (Cont) – André Nicolas Nov 8 '13 at 0:37
Moreover, all ordered partitions of $n+1$ with last element $\gt 1$ can be obtained by adding (not appending) a $1$ to the last element of an ordered partition of $n$. So the number of ordered partitions of $n+1$ with last element greater than $1$ is $P(n)$. So to count ordered partitions of $n+1$, we count the ones that end in $1$ ($P(n)$) and the ones that don't (another $P(n)$) for a total of $2P(n)$. We double each time. – André Nicolas Nov 8 '13 at 0:41

So $4+1$ is one example. $2+2+1$ is another

  • What kinds of things add up to 5? (only numbers greater than or equal to 1 are used).

  • What's the least number of numbers you can use? What's the greatest number?

  • What if you rearrange the order of something you already have? Do you get something new (if you consider at as ordered)?

  • Have you done it already for 1,2,3, and 4? You might be able to use those to help with 5.

share|cite|improve this answer

Counting in binary the groups of 1s or 0s form the partitions. Half are the same so there are 2^(n-1). As to be expected this gives the same results as the gaps method, but in a different order.


0000 4 
0001 3,1 
0010 2,1,1 
0011 2,2 
0100 1,1,2 
0101 1,1,1,1 
0110 1,2,1 
0111 1,3


000 4
001 3,1
010 2,2
011 2,1,1
100 1,3
101 1,2,1
110 1,1,2
111 1,1,1,1
share|cite|improve this answer

Your Answer


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.