+5 votes
528 views
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
asked
retagged | 528 views
$\binom{24}{19} - 6*\binom{14}{9} = 30492$
pls give detail approach . yes ans is correct.

## 1 Answer

+16 votes
Best answer
• 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.

answered by Veteran (50.9k points)
edited
Why did you put 1 in first and 19 in latter and not the other way round?

Debashish Deka  (Convolution Rule). Let A(x) be the generating function for selecting items from set A, and let B(x) be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union A∪B is the product A(x) B(x).

Since value of each di is in set {0,1,2,3,4,5,6,7,8,9} .How are d1,d2,...,d6  disjoint ?? Plz explain.

I cannot understand r=0 and r=19 implies $-1^{0}\binom{25}{19}$

means why r u taking r=0 and 19 value?

We need the coefficient of x^19.
So by putting r = 0 in first series (in ans) and r = 19 in second series. We got the coefficient of x^19.
Similarly by putting r = 1 in first series and r = 9 in second series. We got the coefficient of x^19.
Only these two ways we have to get x^19.
ya, got it tnks:)

+1 vote
1 answer
1
0 votes
0 answers
2
0 votes
1 answer
3