retagged by
2,843 views
17 votes
17 votes
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
retagged by

2 Answers

Best answer
28 votes
28 votes
  • The number is $<$ $1000000$ , $\Rightarrow$ it contains 6 digits.
  • Each of these digits can be one of $0,1,2,3....9$

$\Rightarrow$ problem reduces to no of integral solution to the following equation

$d_1+d_2+d_3+d_4+d_5+d_6 = 19$ where $0\leq d_i \leq 9$

Using generating function : (how to use)

$$\begin{align*} & \ \ \ \left [ x^{19} \right ]\left ( 1+x+x^2+x^3+....+x^9 \right )^{6} \\ &=\left [ x^{19} \right ]\left [ \frac{1-x^{10}}{1-x} \right ]^{6}\\ &=\left [ x^{19} \right ]\left ( 1-x^{10} \right )^{6}. \sum_{r=0}^{\infty}\binom{5+r}{r}.x^{r} \\ &=\left [ x^{19} \right ]\left [ \sum_{r=0}^{6}.\binom{6}{r}.\left ( -x^{10} \right )^{r} \right ]. \left [ \sum_{r=0}^{\infty}\binom{5+r}{r}.x^{r} \right ] \\ &=\left ( -1 \right )^{0}*\binom{24}{19} + \left ( -1 \right )^{1}*6*\binom{14}{9} \\ &=30492\\ \end{align*}$$

NOTE:

1. $1+x+x^2+x^3+.....x^n = \frac{1-x^{n+1}}{1-x}$

2. $\frac{1}{(1-x)^n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}.x^r$

3. $\left [ x^{19} \right ]$ means coefficient of $x^{19}$ of the whole expression.

edited by
2 votes
2 votes
Without using generating functions.

From inclusion exclusion principle $Total \ objects = \ Total \ combinations\ - \ combinations \ with \ a\  digit > 9 \ =  C(24,19) \ -\ 6*C(14,9) $
edited by

Related questions

2 votes
2 votes
2 answers
1
2 votes
2 votes
4 answers
2
jaydip74 asked Jul 22, 2023
462 views
In how many ways can 3 non-negative integers be chosen such that a + b + c = 10 where a >= -1 , b >= -5 and c >= 3 ? 3666105None
0 votes
0 votes
2 answers
3
Lakshman Bhaiya asked Oct 30, 2018
1,668 views
9 different books are to be arranged on a bookshelf. 4 of these books were written by Shakespeare, 2 by Dickens, and 3 by Conrad. How many possible permutations are there...