6
$\begingroup$

The question is:

Find number of ways of arranging $2n$ white and $2n$ black balls such that no $n$ consecutive white balls are together.

What I did was to arrange the black balls and number the $2n+1$ gaps between them as $x_i$ where $1\le i\le 2n+1$ and now use the relation: $$\sum_{i=1}^{2n+1}x_i=2n$$ where $0\le x_i\le n-1$ and $x_i$ denotes number of white balls in the $i^{th}$ gap.

This yields the solution for the number of ways as the coeff. of $x^{2n}$ in $(1+x+x^2+...+x^{n-1})^{2n+1}$

This is where I'm having a problem. How do I calculate this coefficient?

Any help or alternate methods would be appreciated.

$\endgroup$
3
  • $\begingroup$ I suppose you could write $(1+x+x^2+...+x^{n-1})^{2n+1}=(1-x^n)^{2n+1}(1-x)^{-2n-1}$ and then use series expansion/product, not sure if it yields anything nice. $\endgroup$
    – Sil
    Sep 6, 2020 at 9:42
  • 1
    $\begingroup$ @Sil I tried it but couldn't go too far. $\endgroup$ Sep 6, 2020 at 9:44
  • $\begingroup$ The number with a group of $2n-k$ white balls is $2{2n+k-1\choose k}+(2n+k-1){2n+k-2\choose k}$ as the group needs a black ball at either end unless the group is at one end. $\endgroup$
    – Empy2
    Sep 6, 2020 at 10:24

1 Answer 1

2
$\begingroup$

To finish where you left off, to get the coefficient of $x^{2n}$ we write $$ (1+x+x^2+...+x^{n-1})^{2n+1}=(1-x^n)^{2n+1}(1-x)^{-2n-1}. $$ Now we can use Binomial theorem and Binomial series expansion to get $$ \left(\sum_{i=0}^{2n+1}(-1)^i\binom{2n+1}{i}x^{in}\right) \cdot \left(\sum_{j=0}^{\infty}(-1)^j\binom{-2n-1}{j}x^{j}\right). $$ Since we are interested in coefficient of $x^{2n}$, we must have $in+j=2n$, and so $j$ is divisible by $n$. Thus only possible choices for $(i,j)$ are $(2,0)$, $(1,n)$ and $(0,2n)$ and the coefficient is $$ (-1)^2\binom{2n+1}{2}(-1)^0\binom{-2n-1}{0}+ (-1)^1\binom{2n+1}{1}(-1)^n\binom{-2n-1}{n}+\\ (-1)^0\binom{2n+1}{0}(-1)^{2n}\binom{-2n-1}{2n} $$ which simplifies to $$ \bbox[#ffd,10px]{\binom{4n}{2n}-(2n+1)\left[\binom{3n}{n}-n\right]}. $$ Here we have used also $\binom{-2n-1}{n}=\binom{3n}{n}(-1)^n$ and $\binom{-2n-1}{2n}=\binom{4n}{2n}$, which follow directly from definition of generalized binomial coefficient $\binom{\alpha}{k}=\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}$.

$\endgroup$
1
  • 1
    $\begingroup$ Nice, I forgot about the generalized definitions of binomial coefficients $\endgroup$ Sep 6, 2020 at 10:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .