How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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$.
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
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.
I'm so late to this discussion, however I think I can add something useful. The method with pennies and grains of rice, described here by @AndreNicolas, can be made more clear. Let's have $N$ pennies in a row with $N-1$ gaps between them. Let's place commas and pluses in these gaps with all possible ways - after applying the addition we'll get all possible ordered partitions of the number $N$. The case $N=4$ is illustrated below:
Here we can replace commas by $0$ and pluses by $1$, and see that there is a one-to-one mapping between ordered partitions of the number $N=4$ and binary numbers with three bits. These binary numbers form a binary hypercube with dimension$=3$, so it's easy to notice other useful properties of these partitions - for example, all partitions with two parts lay on the second level of this cube (counting from the top). This mapping holds for other values of $N>0$, of course.
Please see here for more information.