GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
205 views
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
asked in Combinatory by Veteran (12.2k points)   | 205 views
$\binom{24}{19} - 6*\binom{14}{9} = 30492$
pls give detail approach . yes ans is correct.

1 Answer

+9 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 (35.7k points)  
edited by
is second term 6c1*14c9 ??
yes. added
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.
Top Users Jan 2017
  1. Debashish Deka

    7906 Points

  2. Habibkhan

    4736 Points

  3. Vijay Thakur

    4474 Points

  4. sudsho

    4318 Points

  5. saurabh rai

    4200 Points

  6. Arjun

    3638 Points

  7. Bikram

    3494 Points

  8. santhoshdevulapally

    3470 Points

  9. GateSet

    3228 Points

  10. Sushant Gokhale

    3116 Points

Monthly Topper: Rs. 500 gift card

18,944 questions
23,897 answers
52,114 comments
20,213 users