GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
578 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 (13.6k points) 25 58 127
retagged by | 578 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 (56.9k points) 36 189 499
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.
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.

 

@ Debashish

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}$.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23338 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7912 Points

  4. srestha

    6228 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4286 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question makhdoom ghaya
Popular Question junaid ahmad
Notable Question learner_geek
Notable Question jothee
Popular Question jothee
Notable Question Jeffrey Jose
Notable Question air1ankit
Nice Question jothee
Verified Human shaleen25
Popular Question jothee
27,290 questions
35,142 answers
83,920 comments
33,231 users