Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not).


Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die are numbered $0,1,\ldots,k-1$. The dice are unbiased and the tosses are independent. 


**What is the probability $P(n,k)$ that no non-empty subset of the dice adds to a multiple of $k$?** 


One can get answers with inclusion-exclusion, but it becomes rapidly more difficult as $n$ increases. Simple cases are
$$k P(1,k) = k-1,$$
$$k^2 P(2,k) = (k-1)(k-2).$$
David desJardins found that
$$ k^3 P(3,k) = k^3 - 7 k^2 + 15 k - 9 - d\_2(k), $$
$$ k^4 P(4,k) = k^4 - 15 k^3 + 80 k^2 - 170 k + 104 - (10 k - 40) d\_2(k) + 10 d\_3(k),$$
where
$$ d\_2(k) = 1 \text{ if $k$ is even, 0 otherwise},$$ 
$$ d\_3(k) = 1 \text{ if $k$ is 0 mod 3, otherwise}.$$
David also found the leading terms as $k\to\infty$ for fixed $n$, starting with
$$ P(n,k) = 1 - (2^n - 1)/k
 + 1/2 (4^n - 3^n - 2^n + 1)/k^2 + \cdots .$$


However, nobody found an exact formula, recursion, or generating function, or in fact any method for rapid computation when $n$ is large. **That's my question.**



probability of zero subset sum
First off, let me prove that all $P(n,k)=0$ for $n\geq k$, which follows from a simple lemma:


**Lemma.** In any sequence of $k\geq 1$ integers $m\_1, m\_2, \dots, m\_k$, there exists a subsequence summing to a multiple of $k$.


**Proof.** Define $s\_i := (m\_1+m\_2+\dots+m\_i)\bmod k$, including $s\_0=0$. By the pigeonhole principle, among the integers $s\_0, s\_1, s\_2, \dots, s\_k\in\{0, 1,\dots,k-1\}$, there exist two equal ones, say, $s\_i=s\_j$ for some $i<j$. Then $m\_{i+1}, m\_{i+2}, \dots, m\_j$ form a required subsequence. QED




---


Now, let me discuss computing $P(n,k)$ for fixed $k$.


For any positive integer $n$ and any $S\subset \mathbb{Z}\_k$, let $Q(n,S)$ denote the number of $n$-tuples from $\mathbb{Z}\_k^n$ such that sum of any nonempty subsequence is not in $S$.


Then
$$Q(n,S) = \sum\_{t\in \mathbb{Z}\_k\setminus S} Q(n-1,S\cup (S-t)),$$
where $S-j := \{ s-t\mid s\in S\}$.
Furthermore, by definition we have $$Q(0,S) = 1.$$


In other words, if we fix and arbitrary indexing of the subsets of $\mathbb{Z}\_k$, and let $\bar{Q}(n) := [Q(n,S\_1),Q(n,S\_2),\dots,Q(n,S\_{2^k})]^T$, then
$$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$
where $M$ is a $2^k\times 2^k$ matrix with $M\_{ij}$ equal the number of $t\in \mathbb{Z}\_k\setminus S\_i$ such that $S\_j = S\_i \cup (S\_i - t)$. Clearly, $\bar{Q}(0)=[1,1,\dots,1]^T$.


It follows that for any $S$, the sequence $(Q(n,S))\_{n\geq 0}$ satisfies an order $2^k$ linear recurrence, and in particular so does $k^n P(n,k) = Q(n,\{0\})$. This, however, is not so exciting as we know that the sequence $(k^n P(n,k))\_{n\geq 0}$ stabilizes to $0$ starting with $n=k$. Still, the aforementioned formulae allow to compute $P(n,k)$ routinely, at least for small $k$.




---


**Example for $k=2$.** Let us fix the indexing: $S\_1 = \emptyset$, $S\_2=\{0\}$, $S\_3=\{1\}$, and $S\_4=\{0,1\}$. Then
$$M = \begin{bmatrix}
2 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0
\end{bmatrix}$$
with the minimal polynomial $x^4 - 3x^3 + 2x^2$. Hence, for $n\geq 4$
$$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$
In particular, $(2^n P(n,2))\_{n\geq 0} = (1,1,0,0,0,\dots)$, i.e., $P(n,2)=0$ for $n\geq 2$ as we already know.


**Examples for $k\leq 10$.**
\begin{split}
(2^n P(n,2))\_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\
(3^n P(n,3))\_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\
(4^n P(n,4))\_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\
(5^n P(n,5))\_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\
(6^n P(n,6))\_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\
(7^n P(n,7))\_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\
(8^n P(n,8))\_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\
(9^n P(n,9))\_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\
(10^n P(n,10))\_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots).
\end{split}


**P.S.** I've added these values to the OEIS as the [sequence A309106](https://oeis.org/A309106).


