9
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I would do $10$-digit numbers without restriction on initial digit, and then the same for $9$-digit numbers with no restriction. Modifying Stars and Bars to exclude $x_i\gt 9$ is done in the same way for each. $\endgroup$ – André Nicolas Jul 29 '14 at 5:46
  • $\begingroup$ An alternative progam for finding the numbers that sum to 15 is based on what adding 1 to a number does to the digit sum. Note that if a number does not end in 9, then adding 1 also adds 1 to the digit sum. If it ends in one 9, then adding 1 will make the last digit 0, and add a carried 1 to the second-last digit. Thus the digit sum will decrease by 8. If it ends in two 9's, then adding 1 will make the last two digits 0 and increase the next by 1, so the sum will decrease by 17 and so on. $\endgroup$ – DavidButlerUofA Jul 29 '14 at 12:43
4
$\begingroup$

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} $$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ you answer is continuing which approach?#1 or #2? $\endgroup$ – user2838619 Jul 29 '14 at 6:14
  • $\begingroup$ My answer is continuing with approach #2. I am counting the number of cases where 'digits' are larger than 9. If we allow 'digits' to range from 0 to 15 and throw out the cases where any 'digits' are larger than 9 we have the result. $\endgroup$ – Eric Jul 29 '14 at 6:45
  • 1
    $\begingroup$ @RobertIsrael, I am waiting for your answer, pls... $\endgroup$ – Vikram Jul 29 '14 at 6:49
  • $\begingroup$ @RobertIsrael,me too.I want to see your answer. $\endgroup$ – user2838619 Jul 29 '14 at 6:59
1
$\begingroup$

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}$

$\endgroup$
  • 2
    $\begingroup$ What happened to the $9$'th power of $1+x+\ldots + x^9$? Unfortunately $$ x \dfrac{(1-x^9) (1-x^{10})^9}{(1-x)^{10}}$$ is not quite so simple. $\endgroup$ – Robert Israel Jul 29 '14 at 7:32
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I am not sure why there's this box instead of math mode, I am new here and I just typed as in latex :S $\endgroup$ – jan1892 Jul 29 '14 at 7:16
  • $\begingroup$ After 24 \choose 9, put one dollar sign, then - sign, then one dollar sign and then 23 \choose 8 $\endgroup$ – Vikram Jul 29 '14 at 7:31
  • $\begingroup$ Interesting, thanks. $\endgroup$ – jan1892 Jul 29 '14 at 7:35
1
$\begingroup$

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\\ $$

$\endgroup$
0
$\begingroup$

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))
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Then why haven't you done it?! $\endgroup$ – user117644 Jul 29 '14 at 8:14
  • $\begingroup$ What makes you think I haven't? $\endgroup$ – Robert Israel Jul 29 '14 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.