[Math] If we have $m$ indistinguishable objects how many ways is it possible to put them in $n$ indistinguihable positions

combinatoricsdiscrete mathematics

if we have $m$ indistinguishable objects, how many ways is it possible to put them in $n$ indistinguishable positions? (for 2 cases 1: without empty position allowed 2: empty positions are allowed.)

We already know that if objects were distinct and the positions are undistinguishable, the number is called Stirling number $S(m,n)$ (without empty positions allowed).

Best Answer

Elaborating on @Andre's answer, let $p_k(n)$ denote the number of ways to write the natural number $n$ as the sum of exactly $k$ natural numbers, in nonincreasing order. For example, $p_2(3)=1$ because $3=2+1$ is the only such sum. $p_2(4)=2$ because $4=3+1$ and $4=2+2$ are the two different such sums. We also have $p_3(3)=1$ since $3=1+1+1$ is the only such sum, and $p_3(4)=1$ since $4=2+1+1$ is the only such sum. We have $p_4(3)=0$ since there is no such sum with four parts. We call these functions partitions of $n$ into $k$ parts. We may also add up $p_1(n)+p_2(n)+p_3(n)+\cdots$ to get all the partitions of $n$ (into any number of parts). This is represented by $p(n)$.

Now I'll explain why these functions are relevant to your problem. Suppose I have $m$ identical marbles, and $n$ identical bowls. I place the marbles in the bowls. Then, since the marbles are identical, all I can tell about each bowl is how many marbles are inside it. So, perhaps I have a bowl with 4 marbles, a bowl with 2 marbles, a bowl with 7 marbles. However, the bowls all look the same, so I may as well arrange the bowls so that each bowl has at least as many marbles as the next bowl. That is, I'll put the bowl with 7 marbles first, then the bowl with 4 marbles, then the bowl with 2 marbles. We can think of this as $13=7+4+2$. If we want to put our $13$ marbles into exactly three bowls, and each bowl gets at least one marble, then this is bijective with partitions of $13$ into exactly $3$ parts, i.e. $p_3(13)$. If instead we want to put our $13$ marbles into exactly three bowls, and some bowls may be empty, then we want to count $13=7+4+2$, but also $13=9+4 (+0)$. Hence this case is counted by $p_3(13)+p_2(13)+p_1(13)$. Lastly, if we have an unlimited number of bowls at our disposal (although we'll never need more than 13), then we want $p_1(13)+p_2(13)+p_3(13)+p_4(13)+\cdots =p(13)$.

Many identities are known about these partition functions, although in my opinion not as many as for binomial coefficients. You can read about some of them on Wikipedia. Some samples are:

  • The sequence $p(n)$ has the generating function $\prod_{k\ge 1}=\frac{1}{1-x^k}$

  • If $n\equiv 4\pmod{5}$, then $p(n)$ is a multiple of $5$ (due to Ramanujan)

  • $p(n)\approx \frac{1}{4n\sqrt{3}}e^{\left(\pi \sqrt{2n/3}\right)}$ as $n\rightarrow \infty$ (also due to Ramanujan, but with Hardy and independently by Uspensky)

  • The number of partitions where the largest part has size exactly $k$ is equal to $p_k(n)$.