Sum of six numbers from 1 to 4 divisible by 5 (and generalization.) Find the probability that 6 positive integers from 1 to 4 are chosen such that their sum is divisible by 5.
In other words, you could have that $[1, 4, 3, 1, 2, 3], [2, 2, 3, 3, 2, 3], \text{and } [3, 2, 2, 3, 3, 2]$ are three separate sets. In mathematical terms the question is asking $a + b + c + d + e + f \equiv 0 \pmod{5}$ where $a, b, c, d, e, f = 1, 2, 3, \text{or } 4$.
I was confused on how to solve it. First, I tried using casework and finding the number of 6-tuplets that added to 10, 15,  and 20 but found there were too many to keep track. I suppose if I really had to, I could bash it out that way, but I would like to know if there's an elegant way to do this problem.
I know there's a simple formula to find the number of ways you can sum $x_1+x_2+\dots+x_n = k$ (where $x_n$ is a non-negative integer and order matters.) It's just $\binom{n+k-1}{n-1}$. However, I want to know if there's a way to generalize for a specific set of numbers, in this case, $1$ to $4$. For example, a formula for the number of positive integer solutions to each of the $x_i$ for $x_1+x_2+x_3+x_4+x_5+x_6 = 10$ would be great. (And for $15$ and $20$, but if there's a formula for $10$ it should work for $15$ and $20$ too.)
Hopefully there is a much easier way to do this problem than just bashing out all the combinations, and if there isn't, is there still an easier way? Thanks in advance.
-FruDe
 A: Let $p_n$ be the desired probability for $n$ tosses. The desired answer is $p_6$.  Clearly $p_1=0$.
We will work recursively.
If the first $n-1$ tosses sum to something not divisible by $5$ then there is a unique choice for the the last toss. If they sum to a multiple of $5$ then no selection will work for the $n^{th}$ toss.  It follows that $$p_n=\frac 14\times (1-p_{n-1})$$
The rest is now straight forward, even with pencil and paper.  We get $$p_6=\frac {205}{1024}$$
Just as a sanity check, note that $p=\frac 15$ is a fixed point for that recursion. Indeed the process converges to $\frac 15$ very rapidly.  That certainly makes sense (after a bunch of tosses it seems likely that all remainders $\pmod 5$ should be equally probable).
Note:  It is not difficult to verify that the $p_n$  are given by:
$$p_n=1-\frac {4^n+(-1)^{n+1}}{5\times 4^{n-1}}$$
A: The generating function approach is to note that the function for one choice is $x+x^2+x^3+x^4$, so the function for six of them is $(x+x^2+x^3+x^4)^6$  You can ask Alpha to expand it, getting $x^{24} + 6 x^{23} + 21 x^{22} + 56 x^{21} + 120 x^{20} + 216 x^{19} + 336 x^{18} + 456 x^{17} + 546 x^{16} + 580 x^{15} + 546 x^{14} + 456 x^{13} + 336 x^{12 }+ 216 x^{11} + 120 x^{10} + 56 x^9 + 21 x^8 + 6 x^7 + x^6$ and read off the coefficients of the powers of $x$ that have a multiple of $5$ in the exponent.
If I were not allowed Alpha but were allowed a spreadsheet, I would make one with seven columns.  The first would be sums from $-3$ to $24$.  The next would be the number of ways of achieving each sum from the number of draws.  The first column would have $1$ in the $1,2,3,4$ rows.  Each cell in the other columns would have the sum of the four numbers in the column to the left and up one to four rows.  Copy right and copy down would fill the table in quickly and the final column would have all the coefficients above.  This is basically just doing the expansion one factor at a time.
A: Here's a continuation of Ross' argument that avoids expanding the whole GF. We have the generating function:
$$F(x)=(x^4+x^3+x^2+x)^6$$
and we want the sum of the coefficients of $F$ whose exponents are divisible by $5$. That sum is equal to:
$$\frac{F(1)+F(\zeta)+F(\zeta^2)+F(\zeta^3)+F(\zeta^4)}{5}$$
Where $\zeta=e^{\frac{2i\pi}{5}}$ is the fifth root of unity. This would still be a somewhat laborious calculation to carry out, so let's simplify it using the algebraic properties of $\zeta$. $1,\zeta^1,\ldots,\zeta^4$ are the roots of $x^5-1$ which factors to:
$$x^5-1=(x-1)(x^4+x^3+x^2+x+1)$$
so in particular, $\zeta,\zeta^2,\zeta^3,\zeta^4$ are the roots of $x^4+x^3+x^2+x+1$. This means that:
$$\zeta^{4n}+\zeta^{3n}+\zeta^{2n}+\zeta^{n}=(\zeta^{4n}+\zeta^{3n}+\zeta^{2n}+\zeta^{n}+1)-1=-1$$
For $n\in\left\{1,2,3,4\right\}$, so $F(\zeta^n)=(-1)^6$. It's easy to see that $F(1)=4^6$, so:
$$\frac{F(1)+F(\zeta)+F(\zeta^2)+F(\zeta^3)+F(\zeta^4)}{5}=\frac{4^6+4(-1)^6}{5}=820$$
And the desired probability is $\frac{820}{4^6}=\frac{205}{1024}$.
