2
$\begingroup$

Well, task is in the title. 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 some number from set $ S = \{\mathbb{N}\setminus\{1\}\} \cup\ \{0\} $. I mean that they should not contain exactly one ball.

In addition, I should say that balls are indistinguishable 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 F r$ my favourite boxes (which I want to contain my lonely balls)

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 F 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 $\binom {F+k -1}{k}$ ways to place $k$ balls into $F$ boxes. According to a famous combinatoric task. (Am I right here?) However, It means that the whole sum equals

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

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

NOW I have 4 equations with some difficult recursion. I really do not like it. I can't do anything with these formulas. I want some help to simplify this or another solution. Now even my python code does not solve it because of recursion restrictions. All I want is to be able to compute this.

PS I have already asked this question on this site, but I was so bad in my explanations that it got off-topic, down-voted and etc it did not receive as much attention as I need :( I really need some help here. I hope I will meet a good attitude now :)

PPS I am sorry if it is very bad behavior from me. and sorry for my bad English.

PPS Am I right in my solution? I have some doubts.

$\endgroup$
  • $\begingroup$ I would have thought: choose the $r$ that will contain exactly $1$. That leaves $F-r$ boxes and $k-r$ balls. Now, the $F-r$ boxes must contain either $0$ or at least $2$. There are, at most $\lfloor \frac {k-r}2\rfloor$ that contain $2$ or more so choose some $i$ from $1$ to that upper bound and choose that many of the remaining boxes. Placing two balls in each of those discharges the requirement, and now you can just distribute the excess over those boxes however you like. $\endgroup$ – lulu Feb 26 '17 at 14:18
3
$\begingroup$

Here is a different approach based upon generating functions.

Just one aspect regarding your approach. Since the $k$ balls are indistinguishable we do not consider $\binom{k}{r}$ different selections of the favourite balls. All these selections collapse in fact into just one selection of $r$ balls.

Since precisely $r$ boxes shall contain one ball we select these boxes at first and get \begin{align*} \binom{F}{r} \end{align*} as number of different configurations with exactly $r$ out of $F$ boxes containing one ball.

Next we focus on the remaining $F-r$ boxes which shall contain zero or more than one ball. We encode the number of balls in one of these $F-r$ boxes as exponent and obtain \begin{align*} 1+x^2+x^3+x^4+\cdots=\frac{1}{1-x}-x\tag{1} \end{align*} Note that $x^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*} [x^{k-r}]\left(\frac{1}{1-x}-x\right)^{F-r} \end{align*}

We finally conclude the wanted number of placing $k$ indistinguishable balls into $F$ distinguishable boxes, so that precisely $r$ boxes contain $1$ ball is \begin{align*} \binom{F}{r}[x^{k-r}]\left(\frac{1}{1-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*} \binom{4}{2}&[x^4]\left(\frac{1}{1-x}-x\right)^{2}\\ &=6\cdot[x^4](1+2x^2+2x^3+\color{blue}{3}x^4+4x^5+\cdots)\\ &=6\cdot 3\\ &=18 \end{align*}

The $\binom{4}{2}$ configurations correspond to \begin{array}{cccc} 1&1&.&.\\ 1&.&1&.\\ 1&.&.&1\\ .&1&1&.\\ .&1&.&1\\ .&.&1&1\\ \end{array} and each of them correspond to $3$ valid configurations resulting in a total of $18$ valid configurations. For example the first one expands to \begin{array}{cccc} 1&1&\color{blue}{0}&\color{blue}{4}\\ 1&1&\color{blue}{2}&\color{blue}{2}\\ 1&1&\color{blue}{4}&\color{blue}{0}\\ \end{array} Note that the two invalid configurations $1 1 \color{blue}{1} \color{blue}{3}$ and $1 1 \color{blue}{3} \color{blue}{1}$ are excluded.

$\endgroup$
  • $\begingroup$ Wow, it is very beautiful and cool solution. I really appreciate that! Thank you! However, coefficient of operator is hard to compute... But I will try my best. $\endgroup$ – Lust_For_Love Feb 26 '17 at 23:17
  • $\begingroup$ @Dida: You're welcome. Good to see the answer is useful! :-) ... and you might be able to obtain an explicit formula by applying the binomial series expansion, the geometric series and the binomial theorem. This way you will get a triple sum. ... $\endgroup$ – Markus Scheuer Feb 26 '17 at 23:22
  • $\begingroup$ Can you look at my answer below on this page. I tried my best and I obtain accurate formula! Wow, I want you to check me and to enjoy some pleasure. Maybe you can make it even more simplier? $\endgroup$ – Lust_For_Love Feb 27 '17 at 0:46
  • $\begingroup$ Can I ask you one more question? What I should do if balls are dist. I don't get how series should change in this new task. $\endgroup$ – Lust_For_Love Feb 27 '17 at 11:24
  • $\begingroup$ Well, I am out ideas. It is better to ask new question. Really strange that I am interested so much in this problem of balls. $\endgroup$ – Lust_For_Love Feb 27 '17 at 12:22
1
$\begingroup$

Markus Scheuer answered my question. He obtain this formula for the answer \begin{align*} \binom{F}{r}[x^{k-r}]\left(\frac{1}{1-x}-x\right)^{F-r}\tag{2} \end{align*} See his answer to understand meaning of it. But there is an interesting operator coefof. And now I would like to compute it using binomial theorem. I will use: \begin{equation} (x+y)^r =\sum_{k=0}^\infty {r \choose k} x^{r-k} y^k \end{equation} and \begin{equation} \frac{1}{(1-x)^s} = \sum_{k=0}^\infty {s+k-1 \choose k} x^k \end{equation} Both of them you can find here: binomical theorem

So, let's start \begin{multline*} \left(\frac{1}{1-x}-x\right)^{F-r} = \sum_{a = 0}^{\infty} \binom{F-r}{a} (-x)^a \left(\frac{1}{1-x}\right)^{F-r-a} =\\= \sum_{a = 0}^{\infty} \binom{F-r}{a} (-x)^a \sum_{b=0}^\infty {F-r-a+b-1 \choose b} x^b = \\ = \sum_{a = 0}^{\infty} \sum_{b=0}^\infty \binom{F-r}{a} (-1)^a {F-r-a+b-1 \choose b} x^{a+b} \end{multline*}

Now I want to find coef of $x^{k-r}$ in this equation. So, I should sum up in the following way:

\begin{multline*} [x^{k-r}] \left(\frac{1}{1-x}-x\right)^{F-r} = \sum_{a,b:\ a+b=k-r} \binom{F-r}{a} (-1)^a {F-r-a+b-1 \choose b} = \sum_{a = 0}^{k-r} \binom{F-r}{a} (-1)^a {F-r-a+k-r-a-1 \choose k-r-a} = \\ = \sum_{a = 0}^{k-r} \binom{F-r}{a} (-1)^a {F+k-2r-2a-1 \choose k-r-a} \end{multline*}

Now, If I am not mistaken, I can say that answer to my task is: $$ N(r,k,F) = \binom{F}{r} \sum_{a = 0}^{k-r} \binom{F-r}{a} (-1)^a {F+k-2r-2a-1 \choose k-r-a} $$

PS. For the example $F = 4, r = 2, k = 6$ this formula really gives $18$

$\endgroup$
  • 1
    $\begingroup$ Congrats! Great work, it looks good to me! :-) (+1) $\endgroup$ – Markus Scheuer Feb 27 '17 at 2:17
0
$\begingroup$

Your question is equivalent to asking the number of ways to put k indistinguishable balls in $F-r$ distinguishable bins.

This is a well known problem called "stars and bars". Basically the idea is that we put the $k$ balls in a row, and we separate the $k$ "stars" (i.e. the indistinguishable balls) with $F-r-1$ "bars". This may sound confusing, so here is a more in-depth explanation:

  1. All the "stars" to the left of the first "bar" will go in the first bin. Similarly, all "stars" to the right of the last "bar" will go in the last bin. If there are no "stars", that means the respective bin will be empty.

  2. Bin number $i$ (for $2\le i\le F-r-1$) will contain the "stars" between the $i-1$th and $i$th "bars". So for example, bin number $3$ will contain the "stars" between the second and third "bars". If there are no "stars" between the two "bars", then the respective bin will be empty.

Note that our setup means that for every possible way to sort the balls in the bins there exists an arrangement of "stars" and "bars" to match this. In other words, the number of possible ways to sort the balls in the bins is equal to the number of ways to arrange the indistinguishable stars and bars. Since there are $k$ stars and $F-r-1$ bars, the answer is simply $\binom{k+F-r-1}{k}$.

$\endgroup$
  • $\begingroup$ Sorry, but my question is not equivalent to your statement. In these $F-r$ bins I want to put $k$ balls under condition that ZERO boxes contain exactly one ball. I mean that there is no boxes with exactly one ball in it. Your binomial coef does not consider that condition. There are some ways with 1-ball boxes in this number. $\endgroup$ – Lust_For_Love Feb 26 '17 at 18:51

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.