Combinatorics – How Many Six-Digit Numbers Have a Sum of Digits $\le 47$?

combinatorics

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.

Best Answer

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);
}
Related Question