11
$\begingroup$

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

Thanks!

$\endgroup$
3

4 Answers 4

Reset to default
22
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ " 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? $\endgroup$
    – user85798
    Nov 8, 2013 at 0:26
  • 4
    $\begingroup$ 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) $\endgroup$
    – André Nicolas
    Nov 8, 2013 at 0:37
  • 5
    $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Nov 8, 2013 at 0:41
  • $\begingroup$ Though am late, but want to add that there are seven integer partitions of $5= 5, 1+4, 2+3, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.$ You stated : "But a set of $4$ elements has $2^4$ subsets.", which applies to permutations possible for $4$ 'rice' markers. $\endgroup$
    – jiten
    Oct 6, 2022 at 1:07
  • $\begingroup$ Though am late, but want to add that there are seven integer partitions of $5= 5, 1+4, 2+3, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.$ You stated : "But a set of $4$ elements has $2^4$ subsets.", which applies to permutations possible for $4$ 'rice' markers. I have feeling that the formula for multisets should work, by taking the five integers and four 'rice' markers. But, that yields: $(5+4-1)C4=8C4= \frac{8\cdot 7\cdot 6\cdot 5}{4\cdot 3\cdot 2}= 70$ instead. $\endgroup$
    – jiten
    Oct 6, 2022 at 1:51
6
$\begingroup$

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.

Groups

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

Gaps

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
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

Compositions-of-4

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .