2
$\begingroup$

Problem 1. Fix a positive integer $n$. For every integer $S \geq n$, let $N_{n,S}$ denote the number of possible ways in which a sum of $S$ can be obtained when $n$ dice are rolled. For example, for $n = 3$ dice and a sum $S = 5$, we have $N_{3,5} = 6$, counting the following possible triples: \begin{align} \left(3,1,1\right), \quad \left(1,3,1\right), \quad \left(1,1,3\right), \quad \left(2,2,1\right), \quad \left(1,2,2\right), \quad \left(2,1,2\right) . \end{align}

(a) Consider the sets \begin{align} A = \left\{ \left(a_1, a_2, \ldots, a_n\right) \in \mathbb{Z}^n ; \ a_i \geq 1 \text{ for all } i, \text{ and } \sum_{i=1}^{n} a_i = S \right\} \end{align} and \begin{align} A_j = \left\{ \left(a_1, a_2, \ldots, a_n\right) \in \mathbb{Z}^n ; \ a_i \geq 1 \text{ for all } i, \ a_j \geq 7 \text{ and } \sum_{i=1}^{n} a_i = S \right\} \end{align} for a fixed $j \in \left\{1, 2, \ldots, n\right\}$.

(i) Write formulas for the numbers of elements in $A$ and $A_j$, respectively. Justify your answers.

(ii) State the Inclusion-Exclusion Formula and use it to prove: \begin{align} N_{n,s} = \sum_{k=0}^n \left(-1\right)^k C^n_k C^{S-1-6k}_{n-1} \end{align} (where $C^a_b$ stands for the binomial coefficient $\dbinom{a}{b}$).

This is the problem I am having difficulty with. For $A$, I think the formula is $$\left|A\right| = {S-1 \choose S-n}.$$

I can't seem to figure a formula for $A_j$, and I don't understand where the variable "x" came from. I have a good understanding of the Inclusion Exclusion formula and think I could complete the proof if I had $A_j$.

$\endgroup$
  • 2
    $\begingroup$ Hint: Define $b_i=a_i$ if $i\neq j$ and $b_i=a_i-6$ if $i=j$. Note that for all $i$, you have $b_i\geq 1$. Also $\sum a_i = S$ if and only if $\sum b_i = S-6$. $\endgroup$ – Hamed Aug 13 '18 at 16:24
  • $\begingroup$ Your formula for $A$ is correct, although it would be better to write it in the form $\binom{S - 1}{S - 1 - (S - n)} = \binom{S - 1}{n - 1}$ in order to obtain the formula you wish to prove. $\endgroup$ – N. F. Taussig Aug 13 '18 at 16:25
  • 1
    $\begingroup$ The $x_j$ seems to be a printing mistake, $a_j \ge 7$ makes more sense here. $\endgroup$ – Ingix Aug 13 '18 at 16:33
  • $\begingroup$ Hamed: So using this would give me the formula $\ S-7 \choose S-n-6 $. Am I following you correctly? $\endgroup$ – Robbie Meaney Aug 13 '18 at 17:31
  • 1
    $\begingroup$ @RobbieMeaney That is correct. However, to get the desired formula for $N_{n,S}$, it would be better to write the formula in the form $$\binom{S - 7}{S - 7 - (S - n - 6)} = \binom{S - 7}{n - 1} = \binom{S - 1 - 6}{n - 1}$$ $\endgroup$ – N. F. Taussig Aug 13 '18 at 17:36
2
$\begingroup$

You have correctly calculated $|A|$. However, in order to obtain the desired formula for $N_{n,S}$, it would be more useful to write $|A|$ in the form $$|A| = \binom{S - 1}{n - 1}$$ which can be obtained from your formula by observing that $$|A| = \binom{S - 1}{S - n} = \binom{S - 1}{S - 1 - (S - n)} = \binom{S - 1}{n - 1}$$ Alternatively, since $$A = \left\{(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n \mid a_i \geq 1~\text{for all $i$ and}~\sum_{i = 1}^{n} a_i = S\right\}$$ we need to count the number of solutions of the equation $$\sum_{i = 1}^{n} a_i = a_1 + a_2 + \cdots + a_n = S$$ in the positive integers. A particular solution corresponds to the placement of $n - 1$ addition signs in the $n - 1$ spaces between successive ones in a row of $n$ ones. For instance, in the case $S = 5$ and $n = 3$, $$1 \square 1 \square 1 \square 1 \square 1$$ choosing to fill the third, fourth, and fifth spaces with addition signs yields $$1 1 1 + 1 + 1$$ which corresponds to the solution $(a_1, a_2, a_3) = (3, 1, 1)$. The number of such solutions is the number of ways we can select $n - 1$ of the $S - 1$ spaces between successive ones to fill with addition signs, which is $$\binom{S - 1}{n - 1}$$

Since we are interested in the number of ways the sum $S$ can be obtained when $n$ six-sided dice are rolled, we must exclude those solutions in which $a_j \geq 7$ for some $j \in \{1, 2, \ldots, n\}$. If we let $$A_j = \left\{(a_1, a_2, \ldots, a_n) \in \mathbb{Z}^n \mid a_i \geq 1~\text{for all}~i, a_j \geq 7,~\text{and}~\sum_{i = 1}^{n} a_i = S\right\}$$ for some fixed $j \in \{1, 2, \ldots, n\}$, then $|A_j|$ is the number of positive integer solutions of the equation $$\sum_{i = 1}^{n} a_i = a_1 + a_2 + \cdots + a_n = S$$ in which $a_j \geq 7$. Since $a_j \geq 7$, $a_j' = a_j - 6$ is a positive integer. Substituting $a_j' + 6$ for $a_j$ in the equation $$a_1 + a_2 + \cdots + a_j + \cdots + a_n = S$$ yields \begin{align*} a_1 + a_2 + \cdots + a_j' + 6 + \cdots + a_n & = S\\ a_1 + a_2 + \cdots + a_j' + \cdots + a_n & = S - 6 \end{align*} which is an equation in the positive integers with $$\binom{S - 6 - 1}{n - 1} = \binom{S - 1 - 6}{n - 1}$$ solutions. Hence, $$|A_j| = \binom{S - 1 - 6}{n - 1}$$ From there, you can use the Inclusion-Exclusion Principle to obtain the formula for $N_{n, S}$.

$\endgroup$
  • 1
    $\begingroup$ That was a very detailed response and I appreciate you taking the time to write that out! $\endgroup$ – Robbie Meaney Aug 13 '18 at 17:51
3
$\begingroup$

The nodes of the poset for use with PIE consists of the subsets $Q\subseteq [n]$ representing $n$-tuples of positive integers that sum to $S$ where the elements at positions $q\in Q$ are at least seven, plus possibly some others. The weight of each tuple is $(-1)^{|Q|}.$ Note that tuples where all elements are less than seven only occur when $Q = \emptyset$ and hence have weight $(-1)^{|\emptyset|} = 1.$ On the other hand tuples with values at least seven exactly at the positions of some $P\subseteq [n]$ are included at all nodes $Q\subseteq P$ for a total weight of

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{p=0}^{|P|} {|P|\choose p} (-1)^p = 0$$

i.e. zero. So the only contribution comes from the tuples being counted by $N_{n,S}.$ We use stars-and-bars to compute the cardinality of the set of tuples being represented by $Q.$ For stars-and-bars the summands to the sum are non-negative and hence to reduce $Q$ to stars-and-bars we have to subtract seven from $S$ at each element of $Q$ and one at those not in $Q$ to get a standard stars-and-bars scenario. (This is the data that is present between bars no matter what.) This yields with $|Q|=k$

$${S - 7\times k - 1\times (n-k) + n-1\choose n-1} = {S - 1 - 6k\choose n-1}.$$

We then have by PIE

$$N_{n,S} = \sum_{k=0}^n {n\choose k} (-1)^k {S - 1 - 6k\choose n-1}.$$

To verify this we may use the closed form

$$[z^S] (z+\cdots+z^6)^n = [z^S] z^n (1+\cdots+z^5)^n = [z^{S-n}] \frac{(1-z^6)^n}{(1-z)^n} \\ = [z^{S-n}] \sum_{k=0}^n {n\choose k} (-1)^k z^{6k} \frac{1}{(1-z)^n} \\ = \sum_{k=0}^n {n\choose k} (-1)^k [z^{S-n-6k}] \frac{1}{(1-z)^n} \\ = \sum_{k=0}^n {n\choose k} (-1)^k {S-n-6k+n-1\choose n-1} = \sum_{k=0}^n {n\choose k} (-1)^k {S-1-6k\choose n-1}.$$

$\endgroup$
  • $\begingroup$ This is a very interesting approach and definitely not the way I would have approached the problem! Thank you for responding and taking the time to do so! $\endgroup$ – Robbie Meaney Aug 13 '18 at 17:52

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.