578 views
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
retagged | 578 views
$\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.

answered by Veteran (56.9k points) 36 189 499
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?

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:)
@Hemant Parihar

How $$\binom{5}{19}\rightarrow \binom{24}{19} ?$$ I didn't get that. May be I'm missing something.

@bhuv where it is written like this?

$\binom{24}{19}$ = $\binom{24}{5}$ . This is correct.

Got it, I was reading from the pic in the comment, there he wrote in step 4 $\binom{5}{r} instead\ of \binom{5+r}{r}$.

+1 vote