1
$\begingroup$

Assume $m$ distinct bins that are placed on a circle. Therefore, each bin has two neighbors that are its adjacents bins. What is the number of ways that one can place $n$ indistinguishable balls in the bins such that no two balls are placed in the same or adjacent bins. In other words, what is the number of ways that each bin has at most one ball and non-empty bins are not adjacent.

EDIT:

Possible solution:

Since $m$ bins are filled with $n$ balls and each bin carries at most one ball, there are $m-n$ empty bins. Now, assume that empty bins are placed along a line one after another. We have to place $n$ non-empty bins in between these empty bins. The number of candidate positions for non-empty bins would be equal to the number of the inner gaps between $m-n$ empty bins i.e. $m-n-1$ and one more gap that can be considered in front of last empty bin and called outer gap. Now, the problem is quite similar to the famous problem of stars and bars where starts correspond to empty bins and bars correspond to non-empty bins. We have to count the number of ways that one can place bars in the candidate position. It should be noted that when a bar (non-empty) is located in the outer gap, that arrangement is associated with two distinct arrangements in the circular setup. Thus, we separate the arrangement into two cases. The first is when all the non-empty bins are placed in inner gaps and the second is when one non-empty bin is placed in the outer gap. This gives the total number of ways as, $$\left[\binom{m-n}{n}-\binom{m-n-1}{n}\right]\times2 +\binom{m-n-1}{n} =2\times\binom{m-n}{n}-\binom{m-n-1}{n} $$

$\endgroup$
  • $\begingroup$ Do you distinguish arrangements that are not equal but can be rotated into each other? For instance, if $m=4$ and and $n=2$, do you count one way, or two? $\endgroup$ – Brian M. Scott Nov 30 '15 at 15:54
  • $\begingroup$ @Shailesh, I posted a possible solution. $\endgroup$ – MMotie Dec 2 '15 at 1:47
  • $\begingroup$ @BrianM.Scott: Yes, the bins are distinct so rotation does matter. and for your example it would be two different cases. $\endgroup$ – MMotie Dec 2 '15 at 1:49
  • $\begingroup$ You’ve interchanged $m$ and $n$ in your calculation. More important, your calculation isn’t quite right: in the double case you have one ball that’s either in the first or last bin, and the other $n-1$ have to be inserted into the $n-m-1$ gaps. Thus, you should get $$2\binom{m-n-1}{n-1}+\binom{n-m-1}n\;,$$ and you can check that this is equal to my answer. $\endgroup$ – Brian M. Scott Dec 2 '15 at 12:44
  • $\begingroup$ @BrianM.Scott, thank you so much. I updated $m$ and $n$ in my solution, but I think my final result, the one you mentioned in the above comment and the one you obtained in your answer are all the same. $\endgroup$ – MMotie Dec 4 '15 at 21:00
1
$\begingroup$

Imagine that the bins are numbered clockwise from $0$ to $m-1$; the balls will occupy bins $b_0,\ldots,b_{n-1}$, where $0\le b_0<b_1<\ldots<b_{n-1}\le m-1$. Let $x_0=b_1$ be the number of empty bins preceding $b_0$, and for $k=1\ldots,n-1$ let $x_k=b_k-b_{k-1}-1$ be the number of empty bins between $b_{k-1}$ and $b_k$. Finally, let $x_n=n-1-b_{n-1}$ be the number of empty bins after $b_{n-1}$. We want the number of integer solutions to $\sum_{k=0}^nx_k=m-n$ satisfying the conditions $x_k\ge 1$ for $k=1\ldots,n-1$, $x_0,x_n\ge 0$, and $x_0+x_n\ge 1$.

Let $y_k=x_k-1$ for $k=1,\ldots,n-1$, and let $y_0=x_0$ and $y_n=x_n$. Then we want the number of solutions in non-negative integers to $$\sum_{k=0}^ny_k=m-n-(n-1)=m-2n+1\tag{1}$$ that satisfy the condition that $y_0+y_n\ge 1$. If we ignore this last condition, this is a standard stars and bars problem whose solution is

$$\binom{m-2n+1+n}n=\binom{m-n+1}n\;.\tag{2}$$

However, $(2)$ includes solutions to $(1)$ that have $y_0=y_n=0$. These are precisely the solutions in non-negative integers to

$$\sum_{k=1}^{n-1}y_k=m-2n+1\;,$$

of which there are

$$\binom{m-2n+1+n-2}{n-2}=\binom{m-n-1}{n-2}\;,$$

the desired number is

$$\begin{align*} \binom{m-n+1}n-\binom{m-n-1}{n-2}&=\color{red}{\binom{m-n+1}{m-2n+1}}-\binom{m-n-1}{m-2n+1}\\ &=\color{red}{\binom{m-n}{m-2n}+\binom{m-n}{m-2n+1}}-\binom{m-n-1}{m-2n+1}\\ &=\binom{m-n}{m-2n}+\color{blue}{\binom{m-n}{m-2n+1}}-\binom{m-n-1}{m-2n+1}\\ &=\binom{m-n}{m-2n}+\color{blue}{\binom{m-n-1}{m-2n}+\binom{m-n-1}{m-2n+1}}-\binom{m-n-1}{m-2n+1}\\ &=\binom{m-n}{m-2n}+\binom{m-n-1}{m-2n}\\ &=\binom{m-n}n+\binom{m-n-1}{n-1}\;. \end{align*}$$

$\endgroup$

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.