# Stars and bars to find “how many $x$ digit numbers are there with sum of digits $y$”?

This question poses a seemingly very simple method to solve problems of the sort "how many $x$ digit numbers are there with sum of digits $y$?", but I don't understand it. Why are the "bad" solutions in correspondence to the solutions of $y_1 + 10 + x_2 + x_3 + x_4 + x_5 = 23$? What's the idea?

For instance, what "correct solution" corresponds to taking $y_1=13$? How to solve this problem?

• See here – Moya Sep 11 '16 at 14:12
• @igael I don't understand why we make the substitution $y_1=x_1-10$ and not, say $x_1-14$.. the latter would also ensure a "digit"... – combinarcotics Sep 11 '16 at 14:12
• @Moya that still doesn't explain why we take the $-10$ substitution... Why not just take $-6$ in that quesion? Why is the $10$ there? – combinarcotics Sep 11 '16 at 14:14
• @igael I hope somebody will explain.. – combinarcotics Sep 11 '16 at 14:22
• @Moya: yes, it is the basis of the good answer. Perhaps it wasn't well applied in the 1st question. – user354674 Sep 11 '16 at 14:31

I'm also not great at combinatorics, but I'll give this a shot to give you a start. This isn't going to be an answer, but an extended comment.

First, we need to establish the number of nonnegative numbers satisfying \begin{equation}\sum_{i=1}^5 x_i=23\end{equation} (call this (*)). This is a standard stars and bars type problem, where we have $23+(5-1)=27$ stars and $5-1=4$ bars. But we've overcounted, because some of these solutions will have some of the numbers being greater than or equal to 10, which should not be allowed because we wants a 5 digit number. For this, we can use the inclusion-exclusion principle (we want the second quoted equation).

Let $A$ be the set of solutions to (*) where none of the integers is greater than or equal to 10, $B$ the set of solutions where 1 integer is greater than or equal to 10, and $C$ where two of the integers are greater than or equal to 10. After this, we're done, because at most 2 of the $x_i$ in the solutions we counted can be greater or equal to $10$. Then \begin{align} |A\cup B\cup C|= |A| + |B| + |C| - |B\cap C|\end{align} (I excluded the parts of the sum that were empty). We want to know $|A|$, we know $|A\cup B \cup C|$, so we need to compute $|B|,|C|,|B\cap C|$. How one would compute $|B|,|C|$ is given, more or less, in the answer I quoted in the comments.

How one would compute $|B\cap C|$, I'm not sure off the top of my head. We also need to exclude the solutions where $x_1=0$. In the quoted method, the number is small enough to count by hand. For this case we would need a more robust method.

Edit: See also here for ideas. I'm out the door, but best of luck to you!

Edit 2: Back, and I messed up a little in haste. $B\cap C$ is obviously equal to the number of solutions where exactly 2 numbers are $\geq 10$. So we can just take $|A\cup B\cup C|=|A|+|B|+|C|$, where $A$ is as before, $B$ is the number of solutions with exactly one number $\geq 10$, and $|C|$ the number of solutions with exactly two numbers $\geq 10$. Then we'll need to refine by excluding the case where $x_1=0$, this can be done with the trick $x_1'=x_1-1$, though some care will need to be taken.

The referred question asks for the number of non-negative integer solutions of \begin{align*} x_1+x_2+x_3+x_4+x_5=23 \end{align*} with only one additional restriction $0\leq x_1\leq 9$. In this case we do not need the inclusion-exclusion principle.

In order to determine all integer solutions with \begin{align*} x_1+x_2+x_3+x_4+x_5=23\qquad\qquad0\leq x_1\leq 9,0\leq x_2,x_3,x_4,x_5\tag{1} \end{align*}

we look at all integer solutions of

and subtract all solutions of

The solutions of (3) are the so-called bad solutions in the referred question, meaning the invalid solutions which are to subtract when determining the solutions of (2).

In order to calculate (2) with the nice range $x_1,x_2,x_3,x_4,x_5\geq 0$ we can use the stars-and-bars technique and obtain \begin{align*} \binom{23+4}{4}=\binom{27}{4}=17550 \end{align*}

In order to calculate (3) we transform the range by a proper substitution which enables us to apply the stars-and-bars technique again. Instead of $x_1\geq 10$, we substitute $x_1=y_1+10$ and the range $x_1\geq 10$ can then be transformed to $y_1+10\geq 10$ or equivalently $y_1\geq 0$.

This way we obtain from (3)

We are now in the same situation as in (2) and can apply the stars-and-bars technique again.

\begin{align*} \binom{13+4}{4}=\binom{17}{4}=2380 \end{align*}



We finally obtain the number of wanted solutions as the total number of solutions of (2) minus the number of solutions of (3) \begin{align*} \binom{27}{4}-\binom{17}{4}=17550-2380=15170 \end{align*}

• +1. Nice job. The complication comes from the subtraction. Something likes $00599$ is not allowed. – Felix Marin Sep 14 '16 at 21:19
• @FelixMarin: Many thanks, Felix! Btw. $00599$ is a valid string as well as $0000\color{blue}{23}$. Subtraction avoids counting e.g $\color{blue}{10}0580$. – Markus Scheuer Sep 15 '16 at 7:32

If $x_1 + x_2 + x_2 + x_3 + x_ + x_5 = 23$ and one or more of the $x_i$ has more than one digit. Than one or more terms is at least $10$. We can replace the $x_i$s with $x'_i$s where one of the $x'_i = x_i -10 \ge >0$ and the rest of the $x'_j = x_j$. Then $10+ x'_1 + x'_2 + .... + x'_5 = 23$.

So if we eliminate all of those solutions we have eliminated all the solutions in which at least one $x_i$ was double digit.

So we are only left with solutions in which all terms are single digit.

We did not eliminate any extraneous solutions because if $x_1 + ... x_5 = 23$ and all $x_i$ are single digit and $10 + x'_1 +.... + x'_5 = 23$, it is not possible for $x'_j = x_j$ for all but one term; that would make the $x'_i = x_i -10 < 0$.

====

Argh. WRONG!!

By eliminating solutions to $10 + .... = 23$ we will elimate an answer with two multidigit terms twice.

E.G. $10 + 11 + 0 + 1 + 1$ will be eliminated by eliminating $10 + ( 0+ 11 + 0 + 1 + 1)$ and by eliminating $10 + (10 + 1 + 0 + 1 + 1)$ as well.

To avoid double counting we must re add thus with two multidigits.

So the solution should be:

# solut to $x_1 + x_2 + ... + x_5 = 23$ - # solutions to $10 + x_1 + ..+x_5 = 23$ + # solutions to $10 + x_1+.... + x_5 = 23$

Which could be very complicated for sums greater than 30. Best to come up with another method altogether.