# How to divide a positive integer $x$ in $n$ pieces so that every possible division is equally likely?

I am asking for an algorithm or a procedure $p: \{x, n\} \rightarrow \mathbb{N}^n$, where $x$ and $n$ are two positive integers so that $x \ge n$. Two additional conditions:

• $p$ will return a set of non-negative integers $R$ so that the sum of the elements in $R$ equals $x$.
• Any possible output from $p$ that fulfills the above condition is equally likely. For example, if $x=10$ and $n=4$ then the output $\{4, 4, 1, 1\}$ should be just as likely as $\{10, 0, 0, 0\}$. (Note that the output is a set, so the order of the elements does not matter.)

One can attempt to implement the procedure through various means, such as by taking the uniform distribution several times etc., but I have not come up with a solution which I am convinced that will fulfill the second condition. Any thoughts?

Note: https://en.wikipedia.org/wiki/Partition_(number_theory) would be applicable here apart from that I am asking for non-negative integers, not only positive integers.

• If I'm not mistaken, this should be accomplished with the stars and bars construction: en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) Commented Dec 20, 2016 at 12:38
• You could generate recursively all the possible outputs for $p$, and then pick one at random... Not very efficient, but works Commented Dec 20, 2016 at 12:39
• @Diminik: I am afraid you are mistaken. The stars and bars is for putting indistinguishable balls into distinguishable bins. My problem asks for indistinguishable bins.
– Sid
Commented Dec 20, 2016 at 13:30

You can adapt the stars and bars argument

• Choose $n-1$ integers randomly from $\{1,2,3,\ldots, x+n-1\}$ without replacement.
• Include $0$ and $x+n$ in your sample set so it now has $n+1$ elements
• Sort your sample set so it has $n+1$ ordered elements starting at $0$ and ending at $x+n$
• Take the differences so you have $n$ differences each at least $1$ adding up to $x+n$
• Subtract $1$ from each of the differences so you have $n$ values of non-negative integers adding up to $x$

There are $\displaystyle {x+n-1 \choose n-1}$ equally likely possibilities for the first point, as you would expect

If instead you wanted all your values to be positive integers, you would change $x+n$ to $n$ in the first four points and ignore the final point

• This answer is unfortunately wrong, since it assumes that the set $R$ is ordered. The stars and bars theorem is not applicable here for that reason. Furthermore, this algorithm can lead to negative integers in the output if you sample the same integer in the first step.
– Sid
Commented Dec 20, 2016 at 13:31
• @Sid You cannot "sample the same integer in the first step" as the sampling is supposed to be "without replacement". Commented Dec 20, 2016 at 13:38
• I'm so sorry, my brain somehow read "with" replacement. But the former part of my comment is unfortunately still true; we are talking about partions here, not the stars and bars, since the output is not supposed to be ordered.
– Sid
Commented Dec 20, 2016 at 13:40
• @Sid - apparently so - my method gives equal probabilities to compositions rather than partitions. For partitions, one possible approach would be to generate them all and then pick one of them, though not very efficient for large $x$ and $n$. Commented Dec 20, 2016 at 13:53