MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I don't know the answer, but I do know that this problem is related to (in fact, essentially equivalent to):… and… via the finite field method – Sam Hopkins Jan 21 '13 at 21:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.