Multinomial coefficient of a sequence in specific form

Question

I came across a question which asked me to find the coefficient of $x^{2n}$ in the following polynomial:

$$(\sum\limits_{i=0}^{n-1} x^i )^{2n+1}$$

My approach was to isolate every term, i.e. if we choose $x^2$ , n times and 1 n times again, we get a part of the coefficient of $x^{2n}$. Doing the same for $x^4$, n/2 times and iterating this process over and over would take a lot of time and the answer will be in the form of a sigma which maybe reduced as well.

However, the answer given was rather simple

Required form of answer

${2n+1}\choose{2}$-${{2n+1}\choose{1}}{{3n}\choose{n}}$+${4n}\choose{2n}$

My questions

1. (if possible)How should I proceed with my method so that I reach the same results?
2. Any other method to precisely find the number of solutions for the equation $$(\sum\limits_{i=1}^{2n+1} x_i )=2n$$ where all $0\leq x_i\leq n-1$

Answer 1

You actually want the number of solutions in non-negative integers to the equation

$$\sum_{i=1}^{2n+1}x_i=2n\;.\tag{1}$$

This can be found by a combination of stars and bars calculations and an inclusion-exclusion calculation.

Without the upper limit of $n-1$ this has $\binom{2n+(2n+1)-1}{(2n+1)-1}=\binom{4n}{2n}$ solutions in non-negative integers by the usual stars and bars calculation. For each $k=1,\ldots,2n+1$ we need to subtract the number of solutions in which $x_k\ge n$. These are in bijective correspondence with solutions to

$$\sum_{i=1}^{2n+1}x_i=2n-n=n\;,$$

and by a similar calculation there are $\binom{3n}{2n}=\binom{3n}n$ of them for each $k$. Thus, we need to subtract $(2n+1)\binom{3n}n=\binom{2n+1}1\binom{3n}n$ to correct for overcounting. However, any solution to $(1)$ in which two of the $x_i$ exceed the upper bound have now been subtracted twice and need to be added back in. For each pair of indices $k$ and $\ell$ there is just one solution to $(1)$ in which $x_k\ge n$ and $x_\ell\ge n$, so we must add $\binom{2n+1}2$ to correct the excessive subtraction in the first correction. And now we’re done, since $(1)$ has no solutions in which more than two of the $x_i$ exceed the upper bound: the final result is

$$\binom{4n}{2n}-\binom{2n+1}1\binom{3n}n+\binom{2n+1}2\;.$$

Answer 2

I would view it from the formal-power-series angle: $$\left(\sum_{k=0}^{n-1}x^k\right)^{2n+1}=\left(\frac{1-x^n}{1-x}\right)^{2n+1}=\underbrace{\left(\sum_{k=0}^{2n+1}(-1)^k\binom{2n+1}{k}x^{nk}\right)}_{=(1-x^n)^{2n+1}}\cdot\underbrace{\left(\sum_{k=0}^\infty\binom{2n+k}{k}x^k\right)}_{=(1-x)^{-2n-1}}$$ (both are instances of the binomial series), so that the coefficient of $x^{2n}$ is indeed $$\underbrace{(-1)^0\binom{2n+1}{0}\binom{2n+2n}{2n}}_{[x^{n\cdot 0+2n}]}+\underbrace{(-1)^1\binom{2n+1}{1}\binom{2n+n}{n}}_{[x^{n\cdot 1+n}]}+\underbrace{(-1)^2\binom{2n+1}{2}\binom{2n+0}{0}}_{[x^{n\cdot 2+0}]}.$$

Hence the final result is

$$\binom{4n}{2n}-\binom{2n+1}1\binom{3n}n+\binom{2n+1}2\;$$