How many 7 digit numbers have a digit sum of 11

combinatoricspermutations

I had this challenge question for my perms and combs homework, but I am a bit unsure on how to go about solving it.

How many $7$-digit numbers have a digit sum of $11$?

To do this problem, I tried setting the boundaries for some digits. So, there are in total $8×9×9×9×9×9×9=4251528$ $7$-digit numbers, with a minimum digit sum of $1$ and a maximum sum of $63$.

Order of the digits is used in this equation, so I think need to use permutations, but I am stuck on what $n$ and $r$ would be for the equation, as the digit $0$ cannot be the first digit, and the sum of the digits must total $11$.

I would like some help in how to solve it.

Best Answer

You want to find the number of solutions of $x_1+x_2+x_3+x_4+x_5+x_6+x_7=11$ in non-negative integers with some constraints. The first constraint is that $x_1 \geq 1$ so instead we'll seek the number of solutions of $y_1+x_2+x_3+x_4+x_5+x_6+x_7=10$ with some constraints, where $y_1+1=x_1$.

Stars and bars tells us there are $\binom{16}{6}$ unconstrained solutions to this equation. We know that $y_1 \leq 8$, so let's determine how many solutions are forbidden because $y_1 \geq 9$. There are $7$ such solutions.

Now let's determine how many solutions are forbidden because $x_n \gt 9$ for some $n$ with $2 \leq n \leq 7$. There is exactly $1$ such forbidden solution for each $n$. Thus, there are $13$ forbidden solutions to our unconstrained equation.

There are, therefore $\binom{16}{6}-13=7995$ seven-digit (decimal) numbers with digit sum $11$.