Number of ways to place $n$ balls in $m$ bins such that no two balls are placed in the same or adjacent bins?

Question

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

Answer 1

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