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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.