Generating functions to calculate finite permutations

Question

Ok, so suppose, I roll a seven sided die (has an extra side of 0) three times to find how many ways I get a sum of nine, I need take coefficent of $ x^9$ in this,

$$ S=(1+x+x^2 + x^3 + x^4 + x^5 + x^6)^3$$

Now, a way which a friend told we could do it is

$$ S= ( \frac{1-x^7}{1-x})^3$$

$$ S= (1-x^7)^3 (1-x)^{-3} = (1-x^7)^3 ( 1 +3x +6 x^2...stuff) $$

So, the coefficent of $x^9$ in this is the ways to get the sum of nine.. And this fact completely baffled me. Because, if we compute S by cubing the original equation, we get a finite polynomial. However, if we do it in this way, get an infinite polynomial and for some reason the coefficent of $x^9$ is same in each?? Like what is the intuition for this to work? I think that the two polynomials we get from g.p simplification and direct cubing are different.

Answer 1

That's because $$ \eqalign{ & \left( {{{1 - x^{\,n} } \over {1 - x}}} \right)^{\,m} = \left( {{{x^{\,n} - 1} \over {x - 1}}} \right)^{\,m} = \left( {{{\prod\limits_{k = 0}^{n - 1} {\left( {x - e^{\,i\,{k \over n}2\pi } } \right)} } \over {x - 1}}} \right)^{\,m} = \cr & = \left( {\prod\limits_{k = 1}^{n - 1} {\left( {x - e^{\,i\,{k \over n}2\pi } } \right)} } \right)^{\,m} \cr} $$ That is, whatever is $1 \le n$, $x^n-1$ contains the root $x-1$ which therefore factors out the pole at the denominator, leaving a polynomial of degree $n-1$.

Also note that $$ F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^m $$ and $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as explained in this post

--- answer to your comment ---

$F_b$ is just your polynomial = rational function;
$N_b$ are the coefficients of the polynomial in $x$, which is of degree $m\cdot r$

Answer 2

Let us take a simpler example.

We have $1=\dfrac{1-x}{1-x}$, so we get a priori a infinite formal series $(1-x)\sum_{n\geq 0}x^n$, while $1$ is a polynomial. But in fact, we don't !

Indeed, $(1-x)\sum_{n\geq 0}x^n=\sum_{n\geq 0}x^n-\sum_{n\geq 0}x^{n+1}=\sum_{n\geq 0}x^n-\sum_{n\geq 1}x^n=1.$

The same phenomenon will certainly occur with your more complicated example. Of course, you need to know precisely what is the series $(1-x)^{-3}$, but fortunately we know: it is $(1-x)^{-3}=6\sum_{n\geq 2}n(n-1)x^{n-2}.$ Tedious computations should certainly yield a polynomial expression for $S$, even starting from the series, the same that you would obtain by developping the cube.

Answer 3

The thing is the second is not an infinite sum, but it is finite. $$S= (1-x^7)^3 (1-x)^{-3} = \sum_{i=0}^3{3\choose i}(-x^7)^i\sum_{j=0}^{\infty}{-3\choose j}(-x)^j=\\ \sum_{i=0}^3{3\choose i}(-x^7)^i\sum_{j=0}^{\infty}{3+j-1\choose j}x^j $$ where it was used the negative binomial formula.

Let's find the coefficient of $x^9$: $${3\choose 0}{11\choose 9}-{3\choose 1}{4\choose 2}=55-18=37.$$ Let's find the coefficient of $x^{19}$ (note that the original finite polynomial has the last term of $x^{18}$): $${3\choose 0}{21\choose 19}-{3\choose 1}{14\choose 12}+{3\choose 2}{7\choose 5}=210-273+63=0.$$ Similarly, the coefficients of terms of exponent greater than $18$ will be $0$.