How to evaluate the number of ordered partitions of the positive integer $ 5 $?
Thanks!
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ en.wikipedia.org/wiki/Partition_(number_theory)should be useful. $\endgroup$– picakhuCommented Apr 7, 2011 at 16:24
-
1$\begingroup$ [WP link above was broken](en.wikipedia.org/wiki/Partition_(number_theory)) $\endgroup$– user2468Commented Apr 7, 2011 at 16:29
-
9$\begingroup$ 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. $\endgroup$– hardmathCommented Apr 7, 2011 at 17:57
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
5
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$.
answered Apr 7, 2011 at 17:55
-
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$ Commented 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$ Commented 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$ Commented 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$– jitenCommented 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$– jitenCommented Oct 6, 2022 at 1:51
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.