3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @hardmath why? I don't see any problem here $\endgroup$ – Lust_For_Love Feb 27 '17 at 14:55
  • $\begingroup$ @hardmath actually I make my code work and there is no problem with even numbers, and for simple calculus, everything coincides. no-no-no, at least 2 balls. It can contain 3,4,5,... $\endgroup$ – Lust_For_Love Feb 27 '17 at 14:57
  • $\begingroup$ @hardmath first of all, I have $F$ boxes. So, remaining $F-r$ boxes... I don't get what is redundant... But you are right. $r$ boxes have exactly one ball. $F-r$ boxes - not one ball. $\endgroup$ – Lust_For_Love Feb 27 '17 at 19:23
  • $\begingroup$ Thanks, I understand your Question better now. $\endgroup$ – hardmath Feb 27 '17 at 19:41
  • $\begingroup$ This counting problem can be framed as finding the number of singleton-free partitions having a specific number of parts. The number of partitions of a set of size $n$ with $k$ parts is the Stirling number of the second kind, $S(n,k)$. Authors seem to use a variety of notations for the number of singleton-free partitions (of a set of size $n$), but see Knuth, AoCP vol. 4A (Combinatorial Algorithms), page 436 where he introduces $\overline{\omega}_n'$ for this. $\endgroup$ – hardmath Feb 28 '17 at 17:19
5
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Wow, actually it is a lot easier, than I tried to do. Well, I need to read more about generating functions. Honestly, it is not clear for me how we naturally encode. It sounds like: "Hey lets think that in denominator we will put this number of permutations and at the degree - amount of balls". But why exactly like this -- it is not clear. This idea has not occurred to me. Well, I appreciate your indifferent to the problem, and actually I am sad that I did not think to this solution myself. Thank you! $\endgroup$ – Lust_For_Love Feb 27 '17 at 22:48
  • $\begingroup$ @Dida: You're welcome, thanks! :-) H. Wilf's Generatingfunctionology is the perfect starter. You might find this answer useful. $\endgroup$ – Markus Scheuer Feb 27 '17 at 23:01
1
$\begingroup$

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} $$

$\endgroup$
  • 1
    $\begingroup$ I am sorry, but what for some negative cases? For example, let's try $r = 1$, $k=4$, $F=6$. I can do this by $1|234|0|0|0|0|$ - at least, one way is here. But your formula claims that there is zero combinations. And you will be confused when you will see $(1-4+1)! = (-4)!$ in your formula. And you will be confused when you will get zero in negative power. So, actually, you should make $k-F + j \ge 0$, isn't it? It will add some missing summands... $\endgroup$ – Lust_For_Love Feb 27 '17 at 23:30
  • $\begingroup$ Yes, indeed.$k-F+j\ge 0$ . I will change the limit of the summation. $\endgroup$ – N. Shales Feb 27 '17 at 23:39
  • $\begingroup$ I think this takes care of the limits issue. Please comment if there is anything else. $\endgroup$ – N. Shales Feb 28 '17 at 0:51
  • $\begingroup$ how do you come to $k \ge 0$? Yes, else in this problem desired count will be zero. but you have $l\ge0$ and $l= k-F+j$. There is why I said about $k-F+j \ge 0$. But now I see $k\ge r$. How did $r$ appear there? $\endgroup$ – Lust_For_Love Mar 1 '17 at 9:48
  • 1
    $\begingroup$ Oh, I missed that, thank you! $\endgroup$ – Lust_For_Love Mar 1 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.