How many 5 digit numbers are possible having sum = 22?

$\begingroup$

How many $5$ digit numbers are possible having sum of their digits = $22$ ?

How can I solve it by using Stars and Bars problem ?

$\endgroup$ 1

1 Answer

$\begingroup$

This is an inclusion-exclusion question.

Count how many solutions to $a_1+a_2+a_3+a_4+a_5=22$ with $a_1\geq 1$ and $a_2,a_3,a_4,a_5\geq 0$.

Then subtract the number of solutions with $a_1\geq 10,$ then the number of solutions with $a_2\geq 10,$ etc.

Then add back in the cases where two of the $a_i$ are $\geq 10$, since you've subtracted these cases twice.

Each of the values you need for this can be computed with stars and bars.

The ultimate count you get is:

$$\binom{21+4}{4} - \binom{12+4}{4}-\binom{4}{1}\binom{11+4}{4} + \binom{4}{1}\binom{2+4}{4} +\binom{4}{2}\binom{1+4}{4}$$

$\endgroup$ 0