Tricky Combinatorics question

Question

A student has to attend a test containing 7 questions of in each of which he can either get $0, 1, 2, 3, 4$ or $5$ marks. In how many ways he can get a total of $10$ marks?

For example, he can get $1,5,4,0,0,0,0$ or $3,2,1,4,0,0,0$ or $0,3,1,4,0,2,0$ which are all three different ways.

My attempt:

I related this question to the case when you have $16$ spaces and $6$ identical coins and you have to distribute these coins in these spaces. The problem here is also that there can be no more than $5$ spaces between two consecutive coins. So it seems useless to relate them.

Answer 1

Your attempt can lead to the correct solution.

The question is how many tuples $x_1, \ldots, x_7$ of non-negative integers $\le 5$ such that $x_1 + \ldots + x_7 = 10$. Without the upper bound that $x_i \le 5$ this is, as you correctly noticed $\binom{10+7-1}{7-1} = \binom{16}{6}$. What we need to do now is calculate "bad" possibilities, i.e. tuples $x_1, \ldots, x_7$ such that $x_1 + \ldots + x_7 = 10$ but there is $i$ such that $x_i > 5$. Notice that it's not possible that for $i \neq j$ both $x_i$ and $x_j$ are greater than $5$.

All options for $i$ are symmetrical, so the number of bad tuples with $i=1$ is equal to the number of bad tuples with any other $i$. $x_1 \ge 6$, $0 \le x_2, \ldots, x_7 \le 5$ and $x_1 + \ldots + x_7 = 10$.

Notice that $\underbrace{(x_1 - 6)}_{=x_1'\ge 0} + x_2 + \ldots + x_7 = 4$. Then $x_2, \ldots, x_7 \le 5$ automatically. Thus we need to calculate the number of tuples $x_1', x_2, \ldots, x_7$ such that all $x_1'$ and $x_2, \ldots, x_7$ are non-negative integers. As we know it is $\binom{4+7-1}{7-1} = \binom{10}{6}$. Therefore the answer is $\binom{16}{6} - 7 \binom{10}{6}$.

Answer 2

This can be solved by using generating functions if you are used to it. The generating function for this case is $$G(x) = (1+x+x^2+x^3+x^4+x^5)^7$$ and what is asked to you is the coefficient of the term $x^{10}$ in $G(x)$. In order to find it, we should also use the fact $$1+x+x^2+x^3+x^4+x^5 = \frac{1-x^6}{1-x}\ and\ \frac{1}{1-x} = 1+x+x^2+x^3+...$$ so we have $$G(x) = (1-x^6)^7\cdot\bigg(\frac{1}{1-x}\bigg)^7 = (1-x^6)^7 \cdot(1+x+x^2+x^3+...)^7$$ and we also have $$(1+x+x^2+\cdots)^7 = \sum_{m=0}^\infty \binom{7+m-1}{7-1}x^m$$ which can be proven by induction (I suggest you to prove it since you are dealing with these kind of problems). So, finally we have $$G(x) = (1-x^6)^7\cdot \sum_{m=0}^\infty \binom{6+m}{6}x^m$$ So the coefficient of $x^{10}$ is $$\binom{7}{0} \binom{16}{6}-\binom{7}{1} \binom{10}{6}$$