Is there a nice way of expanding multinomials of the form $(1+x+\cdots+x^l)^n$?

I have found an expression for the probability generating function of a random variable:

$G_Y(s)=\frac{1}{(6-k+1)^3}[s^k+\cdots+s^6]^3$

(where $k\in\lbrace1,..,6\rbrace$) and I don't know how to use the multinomial theorem to expand this into something usable.

Essentially I am looking for a formula for the coefficient of $x^i$ in:

$(1+x+\cdots+x^l)^n$

with an explanation being even better. Thanks

Solution 1:

This is a tricky one, in general. The value is $\left(\frac{1-x^{l+1}}{1-x}\right)^n$. Since $\frac{1}{(1-x)^n}=\sum_{k=0}^{\infty} \binom{k+n-1}{n-1}x^n$ and $(1-x^{l+1})^n = \sum_{k=0}^{n} (-1)^k\binom{n}{k}x^{(l+1)k}$, you can get the coefficient for $x^m$ as:

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{m-(l+1)k+n-1}{n-1}$$

That's not a lovely formula, but I believe it is the best you can do.

This sum can also be seen as an inclusion-exclusion formula. If $A$ is the set of all $n$-tuples of non-negative integers $(a_1,a_2,\dots,a_n)$ so that $a_1+\cdots + a_n=m$, and $A_i$ is the subset where $a_i>l$, then you want:

$$|A\setminus (A_1\cup A_2\cup\cdots\cup A_n)|$$

which, when inclusion-exclusion is applied:

$$=|A|-(|A_1|+|A_2|+\cdots+|A_n|) + (|A_1\cap A_2|+|A_1\cap A_3|+\cdots + |A_{n-1}\cap A_n|)-\cdots$$ yields this same formula.

Solution 2:

Essentially I am looking for a formula for the coefficient of $x^i$ in:

$(1+x+\cdots+x^l)^n$

$(1+x+\cdots+x^l)^n = \frac{(1-x^{l+1})^n}{(1-x)^n} = (\sum_{k\ge0} \binom{n-1+k}{n-1}x^k)(\sum_{k=0}^{n} \binom{n}{k}(-x)^{(l+1)k})$

The coefficient of $x^i$ in this expression is $\sum_{p=0}^{n} \binom{n-1+i-(l+1)p}{n-1} \binom{n}{p}(-1)^p$