4
$\begingroup$

enter image description here

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!

$\endgroup$
  • $\begingroup$ Must $x_j$ be read as $a_j$ in the definition of $A_j$? $\endgroup$ – drhab Aug 14 '18 at 13:25
  • $\begingroup$ @drhab Yes, that is correct. $\endgroup$ – N. F. Taussig Aug 14 '18 at 13:29
  • $\begingroup$ Yeah sorry I should have clarified, it's a typo and had me confused! $\endgroup$ – Robbie Meaney Aug 14 '18 at 13:30
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ wow thank you for the fantastic answer! Quick question- Why did you choose to use the generalised binomial theorem for h(t) but not g(t)? $\endgroup$ – Robbie Meaney Aug 14 '18 at 13:59
  • 1
    $\begingroup$ If you like, you can think of it as using the generalized binomial theorem in both cases. The binomial theorem just refers to the special case where $n$ is a positive integer. $\endgroup$ – Mike Earnest Aug 14 '18 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.