Generating functions to calculate finite permutations 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.
 A: 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$.
A: 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$
A: 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.
