I'm trying to apply stars and bars to answer a dice question: if $n$ players throw $k$-sided dice, what is the probability that exactly $i$ players throw a unique number (where $0 \leq i \leq n$)?
For example, if $4$ players throw $4$-sided dice, and three throw a $3$, and one throws a $4$, then $1$ player threw a unique number. If two throw a $1$ and two throw a $3$, then $0$ players threw a unique number.
This is easy to enumerate and count for small $n$ and $k$: for $4$ players throwing $4$ sided dice, then we have $4^4$ (or $k^n$ total outcomes), with the following probabilities: $$ P_0 = \frac{40}{256}, \, P_1 = \frac{48}{256},\, P_2 = \frac{144}{256},\, P_3 = \frac{0}{256},\, P_4 = \frac{24}{256},$$ where $P_i$ means the probability of exactly $i$ players throwing a unique number.
I was thinking this could be calculated with a stars-and-bars formulation, where we partition $n$ players into $k$ equally likely bins (each bin is a side of the dice). So a partition $[0,0,0,4]$ means all $4$ players threw a $4$, and $[1,1,1,1]$ means each player threw a different number (one player threw a $1$, the next threw a $2$, etc).
There would be $n \choose k$ or ${4+4-1} \choose {4-1}$ = $7 \choose 3$ = $35$ different partitions of $4$ players into $4$ dice-side bins. Of those partitions, $10$ represent the $P_0$ case: of the form $[0,0,0,4]$ or $[0,2,0,2]$, $12$ represent $P_1$, and look like $[0,0,1,3]$, $12$ represent $P_2$ and look like variations of $[0,1,1,2]$, there are zero for $P_3$, and $1$ representing $P_4$ looking like $[1,1,1,1]$.
So I think the analogous question here is: of the $35$ partitions, how many contain exactly $i$ $1$'s? I don't see a way of generalizing this into a general expression of $n$ and $k$.
Best Answer
This can be done using inclusion–exclusion.
Choose $i$ players who roll unique numbers, leaving $k-i$ numbers and $n-i$ players. Impose $n-i$ conditions that these remaining players shouldn’t roll unique numbers. There are $\binom{n-i}j$ ways to choose $j$ particular conditions to be violated, $j!\binom{k-i}j$ ways to choose unique numbers for them and $(k-i-j)^{n-i-j}$ ways to choose numbers for the remaining players (where $0^0=1$). Thus, by inclusion–exclusion the number of outcomes in which exactly the $i$ chosen players roll unique numbers is
$$ \sum_{j=0}^{n-i}(-1)^j\binom{n-i}jj!\binom{k-i}j(k-i-j)^{n-i-j}\;. $$
There are $\binom ni$ ways to choose the $i$ players who roll a unique number and $i!\binom ki$ ways to choose the numbers they roll; and the total number of outcomes is $k^n$. Thus, the probability that exactly $i$ players roll unique numbers is
\begin{eqnarray*} P_i &=& \binom nii!\binom kik^{-n}\sum_{j=0}^{n-i}(-1)^j\binom{n-i}jj!\binom{k-i}j(k-i-j)^{n-i-j} \\ &=& \frac{i!}{k^n}\sum_{j=0}^{n-i}(-1)^jj!\binom n{i,j}\binom k{i,j}(k-i-j)^{n-i-j}\;. \end{eqnarray*}
For your example with $n=k=4$, this yields
$$ P_i=\frac94\cdot\frac1{i!}\sum_{j=0}^{4-i}(-1)^j\frac{(4-i-j)^{4-i-j}}{j!(4-i-j)!^2} $$
and thus
\begin{eqnarray*} P_0 &=&\frac94\cdot\frac1{0!}\left(\frac{4^4}{0!\cdot4!^2}-\frac{3^3}{1!\cdot3!^2}+\frac{2^2}{2!\cdot2!^2}-\frac{1^1}{3!\cdot1!^2}+\frac{0^0}{4!\cdot0!^2}\right) \\ &=& \frac94\left(\frac{256}{576}-\frac{27}{36}+\frac48-\frac16+\frac1{24}\right) \\ &=& \frac5{32}\;, \\ P_1 &=&\frac94\cdot\frac1{1!}\left(\frac{3^3}{0!\cdot3!^2}-\frac{2^2}{1!\cdot2!^2}+\frac{1^1}{2!\cdot1!^2}-\frac{0^0}{3!\cdot0!^2}\right) \\ &=& \frac94\left(\frac{27}{36}-\frac44+\frac12-\frac16\right) \\ &=& \frac3{16}\;, \\ P_2 &=&\frac94\cdot\frac1{2!}\left(\frac{2^2}{0!\cdot2!^2}-\frac{1^1}{1!\cdot1!^2}+\frac{0^0}{2!\cdot0!^2}\right) \\ &=& \frac98\left(\frac44-\frac11+\frac12\right) \\ &=& \frac9{16}\;, \\ P_3 &=&\frac94\cdot\frac1{3!}\left(\frac{1^1}{0!\cdot1!^2}-\frac{0^0}{1!\cdot0!^2}\right) \\ &=& \frac9{24}\left(\frac11-\frac11\right) \\ &=& 0\;, \\ P_4 &=&\frac94\cdot\frac1{4!}\left(\frac{0^0}{0!\cdot0!^2}\right) \\ &=& \frac9{96}\left(\frac11\right) \\ &=& \frac3{32}\;, \end{eqnarray*}
in agreement with your results.
Here’s Java code that calculates the probabilities for general $n$ and $k$. The results for $n=10$ and $k=20$ are in agreement with the ones given in HighDiceRoller’s answer.