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

• 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
is second term 6c1*14c9 ??
i did same but doing (-x)^10r so i was getting postive value for both terms  :P

by the way thank you for quick reply :)
@debashish,can you pleeasee explain how from your second last step,you came to last step??not able to understand at all.

there was a typo ..corrected nw...sorry.

thanks a lot for clarifying :-)

(1-x10)6 is expanded by binomial theorem..right ??

and (1- x)6 is expanded by the formula you gave in note..right?btw which formula is this?

and in these type of questions,we have to eventualy calculate the coefient of the required term by putting possible value of 'r'?

thanks..:-)

and can you share some good link for studying generating functions because i have almost no idea about them and all these questions of finding coefficents are using these functions.
Like all would agree on Kenneth for gate. I also think kenneth generating function + generalized permutation and combination chapter. There is also a very good pdf ( not long) only on gen function. Go though the how to use link in this post and in the new page ..there  in the first paragraph page15 link.
Why did you put 1 in first and 19 in latter and not the other way round?

+1 vote