I need to find the combinatory formula for this set.

Question

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$.

Answer 1

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}.$$

Answer 2

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}$.