How many $10$ digit number exists that sum of their digits is equal to $15$?

Question

How many $10$ digit number exists that sum of their digits is equal to $15$?

Additional info: First digit from left is not $0$.we could use any digits from $0$ to $9$.

I saw in some related questions that they used Inclusion-exclusion .I've yet to study it so I would like someone continue one of this approaches in a way that does not need Inclusion-exclusion.However,if it's not possible without Inclusion-exclusion,write your answers anyway.

Thing I have done so far:The main challenge in this problem is counting bad situations. Because we know number of ways that sum of $10$ number is equal to $15$.

I have two approachs:

Approach #1:$$x_1+x_2+\cdots+x_{10}=15\space, \space x_1\geq 1\space ,\space 0\leq x_i\leq9$$

Using stars and bars number of answers of this equation:$$x_1+x_2+\cdots+x_{10}=15\space, \space 0\leq x_i\leq15$$

Is equal to :$${15+10-1 \choose 10-1}={24 \choose 9}$$

Now counting situations that one of $x_i$ is bigger than $10$:$$x'_1=x_1-10 \space, \space x'_2=x_2\space,\cdots,x'_{10}=x_{10}\space, \space x'_{1}+\cdots+x'_{10}=5\space,\space0\leq x'_i\leq5$$

I assume here that $x_1$ is bigger than $10$ but any of $x_i$ could be.So number of situations that one of them is bigger than $10$ is : ${5+10-1 \choose 10-1}\times10={14 \choose 9}\times 10$

Now I don't now what about situations where $x_1= 0$

Approach #2(I like this more):

I was thinking that getting rid of those situations that $x_1 = 0\space$ is much easier.So $$x_1+x_2+\cdots+x_{10}=15\space, \space x_1\geq 1\space ,\space x_2,x_3,\cdots,x_{10}\geq 0$$ So number of answers of this equation is ${15+10-1-1 \choose 10-1}={23 \choose 9}$

Now I should count number of ways one of digits is bigger than 10.I don't know what to do here.

Some updates on approach #2:

if biggest $x_i$ is $15$ , then there is $1$ possible situation with $x_1 \geq 1$.

if biggest $x_i$ is $14$ , then there is $9+9=18$ possible situation with $x_1 \geq 1$.

So my question right now is something like this:

a clever way to count situations where $x_1\geq 1$ and largest $x_i$ is equal to $10$.

Here is a c++ code that counts all these numbers.

#include <iostream>

using namespace std;

bool a(int n)
{
 int i;
 int sum=0;
 while(n != 0)
 {
        i= n % 10;
        sum= sum + i;
        n= n /10;
 }
 if (sum == 15) return true;
 return false;    
 }
int main()
{
int k=0;
for(int j=1000000000;j<9600000000;j++)
{
    if(a(j)) 
    {
     k++;
    }           
}
cout<<k+1<<endl;     
}

Which prints $808753$.

And ${23 \choose 9}-(18+1)=817171$.

So $817171 -808753 = 8418$

if biggest $x_i$ is $13$ , then there is $18+{9 \choose 2}\times 3=126$ possible situation with $x_1 \geq 1$.

So $8418 -126 =8292$.

if biggest $x_i$ is $12$ , then there is $18+6{9 \choose 2}+4{9 \choose 3}=570$ possible situation with $x_1 \geq 1$.

So $8292 - 570=7722$

Answer 1

Suppose you can have "digits" of any size. If you imgagine filling up the digits by adding 1 to each of them one at a time, you have to put a 1 in the first one to begin with. After that, you have 14 1's to place into the 10 digits. Now you can imagine arranging 14 1's and 9 + signs to achieve the same effect. That is, we have 23 symbols and we have to choose 9 of them to be + signs. So the number of ways to do this is: $$ \begin{align} &\text{Ways to choose digits adding to 15}\\ &\text{ with more than 9 allowed in some digits} ={{23}\choose{9}} \end{align} $$

However, we have included some options where there are more than nine in a position. If there are 10 dots anywhere, then there can't be another one with 10 because they won't add to 15. So we can safely count the ways for the rest to add to 5. Note that if one of them has 10 1's to begin with and we then add extra 1's this will cover ways when there are allowed to be more than 10 in that spot.

If the first "digit" is 10 or more, we put 10 1's in that position, and then we have 5 1's left to place between 9 + signs. So that's 14 symbols where we need to choose 9 to be + signs. So we get this many ways with 10 or more in the first digit: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{ with 10 or more in only the first digit} ={{14}\choose{9}} \end{align} $$

If some other digit is 10 or more, then we'll put 10 1's in that position. We have to put a 1 in the first position too. So now there are 4 1's left to place between 9 + signs. This is 13 symbols, 9 of which must be + signs. So for each other digit position we get: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{with 10 or more in a particular digit other than first} = {{13}\choose{9}} \end{align} $$

There are 9 digits to choose from, so we have: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{with 10 or more in any one digit} = {{14}\choose{9}} + 9{{13}\choose{9}} \end{align} $$

Hence, subtracting this from the total ways to fill digits we get the final answer: $$ \begin{align} &\text{Ways to fill digits adding to 15} \\ &\text{so there are no more than 9 in any digit} = {{23}\choose{9}} - {{14}\choose{9}} - 9{{13}\choose{9}} \end{align} $$

---

You could also use generating functions:

1st digit could be 1-9 so that corresponds to $(x+\dots+x^9)$. The other digits could be 0-9 which corresponds to $(1+x+\dots+x^9)$. So the number of ways to do it is the coefficient of $x^{15}$ in this expression: $$ \begin{align} (x+\dots+x^9)(1+x+\dots+x^9)^9 &= x(1+\dots+x^8)\left( \frac{1-x^{10}}{1-x} \right)^9\\ &= x\frac{1-x^9}{1-x}\frac{(1-x^{10})^9}{(1-x)^9}\\ &= x \frac{(1-x^9)(1-x^{10})^9 }{(1-x)^{10}}\\ &= x (1-x^9)(1-x^{10})^9(1-x)^{-10}\\ &= x(1-x^9)\left(1-{9\choose1}x^{10}+{9\choose2}x^{20} - \dots\right)\\ &\quad \times \left(1 -{{-10}\choose{1}}x + {{-10}\choose2}x^{2} - {{-10}\choose3}x^{3} + \dots \right) \end{align} $$ In order to produce an $x^{15}$, we choose terms from the four multiplicands. We have these options:

• $x \times 1 \times 1 \times {{-10}\choose{14}}x^{14}$
• $x \times 1 \times -{9\choose 1}x^{10} \times {{-10}\choose{4}}x^4$
• $x \times - x^9 \times 1 \times - {{-10}\choose{5}}x^5$

So the total number of options is: $$ \begin{align} {{-10}\choose{14}} - {9 \choose 1}{{-10}\choose{4}} + {{-10}\choose{5}} &={{23}\choose{14}} - {9\choose 1}{{13}\choose{4}} - {{14}\choose{5}}\\ &={{23}\choose{9}} - 9{{13}\choose{9}} - {{14}\choose{9}} \end{align} $$

Answer 2

Counting the ways that one 'digit' is larger than 9 (note that in the problem at most one 'digit' can be larger than 9) amounts to counting the number of ways that the largest 'digit' is 10, 11, 12, 13, 14, or 15. Here is how I would calculate the number of ways that the largest 'digit' is 10.

First compute the number of ways that the first digit is 10 $$\binom{13}{8}.$$ Here we have a 9 digit number (with no restriction that the first digit being nonzero) whose digits add to 5. Then compute the number of ways that the largest digit is 10 and the first digit is not 10 $$\binom{12}{8}\cdot9.$$ This is the number of 9 digit numbers whose digits sum to 5 with a nonzero leading digit and a '10' digit placed after any one of the digits. The number of ways that the largest digit is '10' is the sum of these two cases. Repeating this process for 11, 12, 13, 14, and 15 should give you all of the 'bad' cases.

Alternatively, if we drop the requirement that the first digit is nonzero the calculations become a bit easier, as then the number of ways that the largest digit is 10 becomes $$\binom{13}{8}\cdot 10.$$ If you want to then count how many numbers have a digit sum of 15 with a nonzero leading digit you can do the problem for 9 digit numbers (with no restriction on the leading digit) and subtract the result. Both approaches seem to require about the same amount of computation.

Answer 3

Coeffecient of x^15 in the expansion of $$(x+x^2+...+x^9)(1+x+x^2+...+x^9)^9$$ should do it. The first term is for left most digit and the second term for remaining 9.

It simplifies to $$ x\frac{1-x^9}{1-x} \frac{1-x^{10}}{1-x} = x\frac{1-x^9-x^{10}+x^{19}}{(1-x)^2} $$ Which is coefficient of $x^{14}$ in $ \frac{1-x^9-x^{10}}{(1-x)^2}$

Answer 4

Try this: You have 15 1s seperated by 9 bars: $$11|1|111|...|1$$ The number of 1s in the nth block represents the nth digit. then you have to distribute $9$ $|$ into $9+15=24$ positions. That is $ 24 \choose 9$ ways. Now you overcounted, since you don't want a $0$ in the first place (something like $|11|...|1$). Now count those: Similarly this is $23\choose 8$. So there should be $24 \choose 9$ - $23 \choose 8$ ways of doing so.

Edit: You also need to exclude the cases where $10, \ldots, 15$ 1s are in the same box. That shouldn't be too hard. You can put $10$ $1$s in an arbitrary block in the beginning and then to the same trick (Beware: If you put it in the first block you don't need to exclude any solutions).

Answer 5

As already stated the number we are looking for is the coefficient of $x^{15}$ of $(\sum_{i=1}^9 x^i)(\sum_{i=0}^9 x^i)^{9}$ A way to calculate this number:

$$ \begin{eqnarray} \left(\sum_{i=1}^9 x^i\right)\left(\sum_{i=0}^9 x^i\right)^{9} = \\ x\left(\frac{1-x^{9}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^{9}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{(1-x)^{10}}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!}\frac{d^9 }{dx^9}\frac{1}{(1-x)^{10}}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!} \frac{d^9 }{dx^9}\sum_{i=0}^{\infty}x^i = \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!} \sum_{i=0}^{\infty}\frac{(9+i)!}{i!}x^i = \\ x(1-x^{9})(1-x^{10})^{9} \sum_{i=0}^{\infty}\binom{9+i}{9}x^i = \\ x(1-x^{9})(1-9x^{10}+x^{20}p_1(x)) \sum_{i=0}^{\infty}\binom{9+i}{9}x^i = \\ (x-x^{10}-9x^{11}+x^{20}p_2(x)) \sum_{i=0}^{\infty}\binom{9+i}{9}x^i \\ \end{eqnarray}$$

The coefficient of $x^{15}$ is $$\binom{9+14}{9}-\binom{9+5}{9}-9\binom{9+4}{9}=808753\\ $$

Answer 6

I tried brute forcing it but my chromebook wasn't powerful enough or perhaps the program needs to be optimized somehow. Here's the python code:

#How many ten digit numbers sum to 15?

def tentofift(small, big):
    count = 0
    for n in range(small, big):
        nsum = 0
        #print(n)
        for p in str(n):
            nsum += int(p)
            #print(nsum)            
            if nsum == 15:
                count += 1
            if nsum >= 15:
                break
    return count

print(tentofift(1000000000, 9600000002))

Answer 7

Let $A(d,s)$ be the number of $d$-digit positive numbers (thus numbers from $10^{d-1}$ to $10^d - 1$ whose sum of digits is $s$. We have $A(1,s) = 1$ for $s = 1,\ldots,9$, $0$ otherwise. A $d+1$-digit number $y$ is of the form $y = 10 x + j$ where $x$ is a $d$-digit number and $j \in \{0,1,\ldots,9\}$, and the sum of its digits is $j$ plus the sum of the digits of $x$. So $A(d+1,s) = \sum_{j=0}^9 A(d,s-j)$. This lets us compute $A(d,s)$ for $d=1$ to $10$ and $s$ from $0$ to $15$ recursively without too much trouble.