# Probability of random integer's digits summing to 12

What is the probability that a random integer between 1 and 9999 will have digits that sum to 12?

As a user suggested, I could make a spreadsheet and count them, but is there a quicker way to do this?

• For a range like this, why not make a spreadsheet and count them? Apr 25 '13 at 16:52
• I vote against closing this question.
– MJD
Apr 25 '13 at 17:40
• I also vote against closing this question. Apr 25 '13 at 22:02
• @TheChaz I am very disappointed to see valid questions like this being closed for strange reasons, e.g. "too localized". Ditto for analogous recent votes. Apr 26 '13 at 15:50
• @TheChaz2.0 There appears to have been a spike of rash closure decisions recently (perhaps sparked by meta threads). I hope that those involved will exercise more careful judgment in the future. If taken to extremes such voting could have very harmful effects. In particular, it might alienate the teachers who could best answer your questions. Is that what you desire? Apr 26 '13 at 23:37

The problem does not require a spreadsheet. It does not even require paper.

The question is to count the number of integer tuples $\langle a,b,c,d\rangle$ with $a+b+c+d=12$ and $0\le a,b,c,d < 10$. We could enumerate this by choosing $a$ and then counting the tuples $\langle b,c,d\rangle$ with $b+c+d = 12-a$, and recursing, but an easier method is available.

First, note that if we drop the $a,b,c,d < 10$ restriction, the problem is easy. By the stars and bars method, there are $\binom{15}{12} = 455$ tuples that sum to 12.

From these 455 we need to eliminate the ones that contain $10, 11,$ or $12$. Let $t_i$ be the number of tuples where $a =i$ for $i\in\{10,11,12\}$. Clearly, $t_{12} = 1$: the only tuple is $\langle 12, 0,0,0\rangle$. For $a=11$ we need $b+c+d=1$, so exactly one of $b,c,d$ is 1 and the other two are 0, and thus $t_{11} = 3$.

For $a=10$ there are two possibilities. Either $\{b,c,d\} = \{2,0,0\}$ or $\{b,c,d\} = \{1,1,0\}$. In either case there are 3 tuples, so $t_{10} = 6$.

Since at most one of $a,b,c,d$ is greater than 9, the total number of tuples that contain 10, 11, or 12 is $4(t_{10}+t_{11}+t_{12}) = 40$.

Thus the total number of tuples of just 0 through 9, and the answer to the question, is 455 - 40 = 415; the probability is $\frac{415}{9999}$.

• Note that with the range starting at 1, leading zeros are explicitly OK. This makes it easier. Apr 25 '13 at 18:12
• There are several features of this problem that make it easier than it seems at first: leading zeroes are acceptable, so $a,b,c,$ and $d$ are symmetric. The required sum is close to 9, so only a few integer tuples need to be subtracted, and no inclusion-exclusion argument is needed. Recognizing such features when they appear can be an important aspect of solving this type of problem.
– MJD
Apr 25 '13 at 18:27
• Does not even require paper?? :) Neither did mine Apr 25 '13 at 19:17
• The problem does not require an integer either. What is the probability that randomly chosen combination of four numbers in the range 0 to 9 adds up to to twelve.
– Kaz
Apr 25 '13 at 21:53
• @Kaz Probability is 0, because if you permit $(a,b,c,d) \in \mathbb{R}^4$, even restricting the possible range to between 0 and 9, $a+b+c+d=12$ is still a three-dimentional figure. That's like asking what the probability that a random point in a plane happens to lie on a given line, or the probability that a randomly chosen number just happens to be exactly the same as a given number. Without restricting the digits to integers, the problem becomes trivial. Apr 26 '13 at 1:24

Use generating functions. The generating function for a single digit is:

$$1 + x + \cdots + x^9 = \frac{1-x^{10}}{1-x}.$$

The generating function for the sum of four digits is the fourth power:

$$\frac{(1-x^{10})^4}{(1-x)^4} = (1-x^{10})^4 (1-x)^{-4}.$$

To solve the problem, find the coefficient of $x^{12}$.

$$(1-x^{10})^4 = 1 -4 x^{10} + 6 x^{20} - \cdots$$

So, we only need the coefficients of $x^2$ and $x^{12}$ in $(1-x)^{-4}$ using the generalized binomial theorem. These are $\binom{5}{2} = 10$ and $\binom{15}{12} = 455$. The coefficient of $x^{12}$ is therefore

$$-4\cdot10 + 1\cdot455 = 415.$$

So the answer is $\frac{415}{9999}$.

• where do 5,2,15 and 12 come from in ncr(5, 2) and ncr(15, 12)? Sep 8 '15 at 17:46
• @michaelsnowden The coefficient of $x^2$ in $(1 - x)^{-4}$ is $(-1)^2\binom{-4}{2} = \binom{4 + 2 - 1}{2}$, because of the binomial theorem which says that the coefficient of $z^n$ in $(1+z)^n$ is $\binom{n}{r}$, and the fact that $\binom{-n}{r} = (-1)^r\binom{n + r - 1}{r}$. Similarly, the coefficient of $x^{12}$ in $(1-x)^{-4}$ is $(-1)^{12}\binom{-4}{12} = \binom{4 + 12 - 1}{12}$. Jan 5 '19 at 21:16
• In general, if we're looking for $k$ random digits summing to $n$, by this answer we're looking for the coefficient of $x^n$ in $(1-x^{10})^k (1-x)^{-k}$. This is going to be $$\sum_{10r+s=n} (-1)^{r+s} \binom{k}{r} \binom{-k}{s} = \sum_{10r+s=n} (-1)^{r} \binom{k}{r} \binom{k+s-1}{s}$$ if I'm not mistaken. Jan 5 '19 at 21:24

With Mathematica code (FROM 1 TO 9999):

Count[Map[Total, IntegerDigits[Range]], 12]


415

So: 415/9999

• As an alternative approach: Probability[x == 12, x \[Distributed] Total[IntegerDigits[Range], {2}]] directly yields 415/9999. Apr 25 '13 at 19:05
• Wow, "FrankenLisp".
– Kaz
Apr 25 '13 at 21:54

Just so GAP doesn't get left out. Here's a GAP version to obtain the count:

Number([1..9999],n->Sum(ListOfDigits(n))=12);


which returns 415. So, the probability is $415/9999$.

• Go GAP! Good to see it's still around and alive. Apr 25 '13 at 20:57

With PARI/GP code

Q(n)=if(n<10,n,n%10 + Q(n\10))

sum(i=1,9999,Q(i)==12)/9999

I obtain $$\frac{415}{9999}.$$