Number of ways to roll $S$ with $n$ dice.

Question

I have been working on this problem for the past 3 days and I am not having a lot of luck with it. I posted part of a) here already and I got some very useful advice. I am sitting a test in this tomorrow and any help whatsoever would be greatly appreciated as I can't make heads or tails of it.

For 1a) I let the set $A= \binom{S-1}{n-1}$ and thanks to a kind user yesterday understand how the set $Aj = \binom{S-1-6}{n-1}$. Using the IE formula proved trickier than I thought.

I set $N_{n,S}= \sum A - \sum Aj$

and I know to use the inclusion exclusion I need to start adding the individual sums to $S$ and subtracting the intersections of $2$ and add $3$ etc but I'm just not sure how to apply that logically here?

b) For this part here I don't even know where to start. I used $ S_6 $ inside the bracket and got $\sum_{a=1}^{6} t^{a} = \frac{t(1-t^{6})}{1-t}$ but I have no idea how to use this to prove b. I also tried to differentiate it and that didn't work either. Because of this, I think proving the generalised binomial formula a different way will be very difficult. Any help would be greatly appreciated, I am sitting a repeat college exam in this tomorrow and not dropping out would be nice!

Answer 1

For the inclusion exclusion part, the $A_j$ are the "bad" sets of rolls, so you want to count $|A|-|A_1\cup A_2\cup \dots \cup A_n|$. The formula gives $$ |A|-|A_1\cup A_2\cup \dots \cup A_n|=|A|-\sum_{j=1}^n|A_j|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j \cap A_k|+\dots $$ That is, you add up the whole set, subtract the bad sets, add in their pairwise intersections, subtract the triple intersections, add back in the quadruple intersections, etc.

You already know what $|A|$ and $|A_j|$ are. Let's look at the next simplest one, the double intersections $|A_i\cap A_j |$. These are the sets of tuples $(a_1,\dots,a_n)$ which sum to $S$ where $a_i\ge 7$ and $a_j\ge 7$. For each of these tuples, if you subtract $6$ from $a_i$ and $a_j$, you get a "normal" tuple where all of the entries are $\ge 1$, but now there sum is $S-2 \cdot 6.$ Therefore, $$ |A_i\cap A_j|=\binom{S-1-12}{n-1}=C^{S-1-6\cdot 2}_{n-1} $$ Recalling that $|A|=\binom{S-1}{n-1}=C^{S-1}_{n-1}$ and $|A_j|=C^{S-1-6}_{n-1}$, you may be starting to see the pattern. Next we will have $|A_i\cap A_j\cap A_j|=C^{S-1-18}_{n-1}$ because there are three bad dice which need to have $6$ subtracted from them. In general, the intersection of $k$ of these sets has size $C^{S-1-6k}_{n-1}$, which you see appearing in the sum. The $C^n_k$ comes from the fact that there are that many $k$-way intersections of the sets $A_1,\dots,A_n$.

---

For the generating function magic, you have $$ f(t)=t^n\underbrace{(1-t^6)^n}_{g(t)}\underbrace{(1-t)^{-n}}_{h(t)}. $$ Using the binomial theorem, $$ g(t)=(1-t^6)^n=\sum_{i=0}^n C^n_k (-t^6)^{k}=\sum_{i=0}^n C^n_k(-1)^k t^{6k} $$ Using the generalized binomial theorem, $$ h(t) = (1-t)^{-n}=\sum_{i=0}^\infty C^{-n}_k (-1)^kt^k=\sum_{i=0}^\infty C^{n+k-1}_k t^k $$ I used the standard trick to get rid of the negative in the binomial coefficient: $$ C^{-n}_k=\frac{(-n)(-n-1)\cdots (-n-k+1)}{k!}=(-1)^k\frac{(n+k-1)\cdots(n+1)n}{k!}=(-1)^kC^{n+k-1}_k $$ Since $f$ is the product of $g$ and $h$ (times $t^n$, which just causes a shift), the coefficient of $f(t)$ is the convolution of the coefficients of $g$ and $h$. I will let you figure out the rest of the details.