How many six-digit numbers are there such that their sum of digits is $\le 47$? The only idea I have for now is that we'll need to subtract the number of all combinations of numbers whose sum of digits is $\le 47$ from $900000$ (all $6$-digit numbers).
Please, help.
Thank you.
 A: Let $x_1$ be the furthest left digit, let $x_2$ be the second digit, etc...
This problem can be reworded as
Find the number of non-negative integer solutions to the following system:
$\begin{cases}
x_1+x_2+x_3+x_4+x_5+x_6\leq 47\\
1\leq x_1\leq 9\\
0\leq x_2\leq 9\\
0\leq x_3\leq 9\\
0\leq x_4\leq 9\\
0\leq x_5\leq 9\\
0\leq x_6\leq 9\end{cases}$
We can make the following changes.
Let $y_1=x_1-1$ and $y_i=x_i$ for each other $i\in\{2,\dots,6\}$.
Let $r = 47-x_1-x_2-x_3-x_4-x_5-x_6$.
Our problem then becomes finding the number of non-negative integer solutions to the system:
$\begin{cases} y_1+y_2+y_3+y_4+y_5+y_6+r=46\\
0\leq y_1\leq 8\\
0\leq y_2\leq 9\\
0\leq y_3\leq 9\\
0\leq y_4\leq 9\\
0\leq y_5\leq 9\\
0\leq y_6\leq 9\\
0\leq r\end{cases}$
This is now in a form we are more familiar with, but we still have the upper bound conditions to be concerned about.  Approach the rest of the problem via inclusion-exclusion based on which of the six upper boundary conditions are violated.
A: Yes, that Idea is very good. So we have to count the six digit numbers which have sum of digits more than $47$. Notice if each digit is $9$ then the sum of digits is $54$, to make it $48$ we would have to subtract one from some digits $6$ times. To make it $49$ we would have to subtract one from some digits $5$ times etc.
So how many ways are there to subtract one  from some of the $6$ positions $6$ times? This is equal to the number of ways to add to $6$ using non-negative integers $a_1+a_2+a_3+a_4+a_5+a_6=45$.
Because $6\leq 9$ we can solve this easily using stars and bars ( notice we need $6\leq 9$ because otherwise some combinations would be weird, like subtracting $10$ from digit $1$ for example , as this would make digit $1$ be $-1$).
We try to solve it by stars and bars, there are going to be $6-1=5$ bars and $6$ stars. So there are $\binom{6+5}{5}$ ways to do it.
Using the same reasoning there are $\binom{5+5}{5}$ ways to substract $5$ times, $\binom{4+5}{5}$ ways to subtract $4$ times and so on.
So the final answer is $\sum_{i=0}^6\binom{i+5}{5}$, we don't have to do this sum, this sort of sum is fairly common, and via the hockey stick identity is equal to $\binom{5+7}{6}=924$. Thus final answer is $900000-924=899076$.

The following c++ code verifies this:
#include <cstdio>
int sumd(int a){
    int b=0;
    while(a!=0){
        b+=a%10;
        a/=10;
    }
    return(b);
}
int main(){
    int a,b=0;
    for(a=100000;a<1000000;a++){
        if(sumd(a)<=47){
            b++;
        }
    }
    printf("%d\n",b);
}

