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$
Best Answer
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:
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} $$