Number of arrangements of balls in boxes

55 Views Asked by At

Given integer $0 < t < n$. There are $n$ boxes, labelled $1$ to $n$, is placed on a circle (which means, $n$ box and $1$ box is adjacent). Place a total of $n$ indistinguishable balls in the boxes, with $0$, $1$ or $2$ in each box, such that no adjacent boxes simultaneously have $0$ balls or simultaneously have $2$ balls, and there's exactly $t$ boxes with $2$ balls (hence exactly $t$ boxes with $0$ balls). How much possible arrangements of balls are there?


What I've tried: first determine all boxes with $2$ balls; we have $\binom{n-t}{t} + \binom{n-t-1}{t-1}$ choices. Then determine empty boxes. I'm stuck here.


Edit. Here's some equivalent problems.

  1. There are $n$ different points on a circle. Draw some segments between adjacent points. There's exactly $t$ chains (a single point is not a chain). What's the number of ways to draw these segments?

  2. There are $n$ different points on a circle. Some are red and some are blue. A run is some contiguous red points such that there's no contiguous sequence of red points containing it (i.e. maximal). One single red point is not a run. There are exactly $t$ runs. The way to color these points?

  3. The sum of all coefficient of $x_{i_1}^4x_{i_2}^4\cdots x_{i_t}^4x_{i_{t+1}}^2x_{i_{t+2}}^2\cdots x_{i_{n-2t}}^2$ in $\prod_{i=1}^n (x_i - x_{i+1})^2$ ($x_{n+1} = x_1$).