Number of ways to put $k$ dist balls in $F$ dist boxes where exactly $r$ boxes contain exactly one ball.

Question

I need number of ways to place $k$ balls in $F$ boxes where exactly $r$ boxes contain exactly one ball. It means that exactly $r$ boxes should contain exactly one ball and another $F - r$ boxes should contain either $0$ or at least 2 balls $(0,2,3,4,5...)$.

In addition, I should say that balls are distinguishable and boxes are distinguishable.

Actually, that's all.

Well, I can tell you my solution.

Let's consider that $N(r,k,F)$ - the answer to my question. i.e. number of ways to place $k$ balls in $F$ boxes where exactly $r$ boxes contain exactly one ball.

Well, let's compute it. Firstly, I can choose with $\binom k r$ ways my favourite balls (which I want to be lonely) and $\binom F r$ my favourite boxes (which I want to contain my lonely balls) and I can make with $r!$ ways concordance between $r$ balls and $r$ boxes. According to a combinatoric rules all of it give $\binom k r \cdot \binom F r \cdot r!$ ways of doing it.

After this, what should I do now? Now I have $F-r$ boxes and $k-r$ balls. And I should place them under condition that ZERO boxes contain exactly one ball. See similarity? It is exactly $N(0, k-r, F-r)$. Hm, Well, now I have equation:

$$ N(r,k,F) =\binom k r \cdot \binom F r \cdot r! \cdot N(0, k-r, F-r) $$

of course $r$ should be $r\le\min(k,F)$ here.

Now I have some recursion. Well, let's think of initial conditions.

$$N(0,0,F) = 1$$

$$N(0,k,0) = 0$$

It is not enough. If I did not have this strange condition about favourite balls I would have $ F^k $ ways to place $k$ balls into $F$ boxes according to a famous basic combinatoric task. However, It means that the whole sum equals

$$ \sum_{s=0} ^{\min(k, F)} N(s,k,F) = F^k $$

Consequently, let's think of $N(0, k, F)$ here. $$ N(0,k,F) = F^k - \sum_{s=1} ^{\min(k, K)} N(s,k,F) $$

NOW I have again 4 equations with some difficult recursion. I really do not like them. I can't do anything with these formulas. I want some help to simplify this or another solution. By the way, now my Python code does solve it. But I want to get some beautiful solution to this problem.

PS I have already asked similar question and get a perfect answer for the case of indistinguishable balls.

Number of ways to place $k$ balls in $F$ boxes where exactly $r$ boxes contain exactly one ball.

But now I am trying to get solution for this case of distinguishable balls. I do not get how I should change solution of Markus with generating functions.

Answer 1

Here is an approach based upon generating functions.

At first we focus on the $r$ out of $k$ distinguishable balls which have to be placed in $r$ out of $F$ distinguishable boxes, each box containing precisely one ball.

• Since balls are distinguishable we have $\binom{k}{r}$ different choices to select $r$ balls out of $k$.

• Since precisely $r$ boxes shall contain one ball we have $\binom{F}{r} $ different choices to select $r$ boxes out of $F$.

• The selection of $r$ distinguishable balls can be placed in $r!$ different ways in the $r$ selected boxes.

We therefore get a total of \begin{align*} \binom{k}{r}\binom{F}{r}r! \end{align*} different configurations to place the $r$ balls into the boxes.

Next we focus on the remaining $F-r$ boxes which shall contain zero or more than one ball. We use generating functions to encode the configurations and since we have distinguishable objects we take exponential generating functions. We encode the number of balls in one of these $F-r$ boxes as exponent and we consider \begin{align*} 1+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots=e^x-x\tag{1} \end{align*} Note that $\frac{x^1}{1!}$ is explicitely excluded guaranteeing that a box will not contain precisely $1$ ball. As we don't know how many balls can be placed in a box, we do not restrict the number of balls per box, indicated by $+\cdots$ in the series. We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series.

We want to place exactly $k-r$ balls in $F-r$ boxes. So, we are looking for \begin{align*} (k-r)![x^{k-r}]\left(e^{x}-x\right)^{F-r} \end{align*}

We finally conclude the wanted number of placing $k$ distinguishable balls into $F$ distinguishable boxes, so that precisely $r$ boxes contain $1$ ball is \begin{align*} \binom{k}{r}&\binom{F}{r}r!(k-r)![x^{k-r}]\left(e^{x}-x\right)^{F-r}\\ &=k!\binom{F}{r}[x^{k-r}]\left(e^{x}-x\right)^{F-r}\tag{2} \end{align*}

With some effort we can expand the expression (2) and represent the wanted number as expression with multiple sums.

Example: Let's look at a simple example to better see what's going on. We take \begin{align*} F=4,k=6,r=2 \end{align*}

We expand the generating function (2) with the help of Wolfram Alpha and obtain

\begin{align*} 6!\binom{4}{2}&[x^4]\left(e^x-x\right)^{2}\\ &=6!\cdot6\cdot[x^4](1+\frac{x^2}{2!}+2\frac{x^3}{3!}+\color{blue}{8}\frac{x^4}{4!}+11\frac{x^5}{5!}+\cdots)\\ &=6!\cdot 6\cdot \frac{\color{blue}{8}}{4!}\\ &=1440 \end{align*}

We encode the six balls with $\{1,2,3,4,5,6\}$ and place for illustration purpose the selection $\{1,2\}$ in two out of six boxes.

We see there are $\binom{4}{2}2!=12$ different configurations. \begin{array}{cccccccc} 1&2&.&.\qquad&\qquad2&1&.&.\\ 1&.&2&.\qquad&\qquad2&.&1&.\\ 1&.&.&2\qquad&\qquad2&.&.&1\\ .&2&1&.\qquad&\qquad.&1&2&.\\ .&2&.&1\qquad&\qquad.&1&.&2\\ .&.&2&1\qquad&\qquad.&.&1&2\\ \end{array} and since there are $\binom{6}{2}=15$ valid configurations to select $2$ balls out of $6$, we have a total of $12\cdot 15=480$ configurations of the above kind.

Each of them correspond to $8$ valid configurations placing the remaining $4$ balls into $F-r=2$ boxes, resulting in a total of $480\cdot8=1440$ valid configurations. For example the first one expands to \begin{array}{cccc} 1&2&\color{blue}{0}&\color{blue}{3,4,5,6}\\ 1&2&\color{blue}{3,4}&\color{blue}{5,6}\\ 1&2&\color{blue}{3,5}&\color{blue}{4,6}\\ 1&2&\color{blue}{3,6}&\color{blue}{4,5}\\ 1&2&\color{blue}{4,5}&\color{blue}{3,6}\\ 1&2&\color{blue}{4,6}&\color{blue}{3,5}\\ 1&2&\color{blue}{5,6}&\color{blue}{3,4}\\ 1&2&\color{blue}{3,4,5,6}&\color{blue}{0}\\ \end{array}

Answer 2

The generating function for this is of the exponential variety and is

$$f(x)=\binom{F}{r}x^r(e^x-x)^{F-r}$$

This is the exponential generating function for selections of words length $k\ge r$ from a multiset of $r$ types of letters such that exactly 1 each of $r$ must be used and any non-negative amount except 1 of the remaining $F-r$ letters may be used.

We allow each letter type choose one of the locations (numbered balls) $1,2,\ldots,k$ to be in the box labelled with said letter type.

The desired count is therefore $\left[\frac{x^k}{k!}\right]f(x)$.

The function may be expanded as a binomial then the exponential as a Taylor series

$$\begin{eqnarray}f(x)&=&\binom{F}{r}x^r\sum_{j=0}^{F-r}(-1)^{F-r-j}\binom{F-r}{j}x^{F-r-j}e^{jx}\\ &=&\binom{F}{r}\sum_{j=0}^{F-r}x^{F-j}(-1)^{F-r-j}\binom{F-r}{j}\left(\sum_{l\ge 0}\frac{j^lx^l}{l!}\right)\\ &=&\binom{F}{r}\sum_{j=0}^{F-r}\sum_{l\ge 0}(-1)^{F-r-j}\binom{F-r}{j}\frac{j^l}{l!}x^{F+l-j}\\ &=&\binom{F}{r}\sum_{j=0}^{F-r}\sum_{k\ge F-j}(-1)^{F-r-j}\binom{F-r}{j}\frac{j^{k-F+j}}{(k-F+j)!}x^{k}\\ &=&\binom{F}{r}\sum_{k\ge r}\left(k!\sum_{j=\max(0,F-k)}^{F-r}(-1)^{F-r-j}\binom{F-r}{j}\frac{j^{k-F+j}}{(k-F+j)!}\right)\frac{x^{k}}{k!}\end{eqnarray}$$

the last step involves swapping the order of summation so that $$\text{desired count}=\left[\frac{x^k}{k!}\right]f(x)= \begin{cases} \displaystyle\binom{F}{r}k!\sum_{j=\max(0,F-k)}^{F-r}(-1)^{F-r-j}\binom{F-r}{j}\frac{j^{k-F+j}}{(k-F+j)!}&,\, k\ge r\\ 0&,\, \text{else}. \end{cases} $$