The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.1k 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 Boss (15.6k points)
retagged by | 1.1k views
+6
$\binom{24}{19} - 6*\binom{14}{9} = 30492$
0
pls give detail approach . yes ans is correct.

2 Answers

+26 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 (57.4k points)
edited by
0
is second term 6c1*14c9 ??
0
yes. added
+1
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 :)
0
@debashish,can you pleeasee explain how from your second last step,you came to last step??not able to understand at all.
+2

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

0

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'?

0
0
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.
+3
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.
0
Why did you put 1 in first and 19 in latter and not the other way round?
0

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.

0

@ 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?

+1
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.
+1
ya, got it tnks:)
0
@Hemant Parihar

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

@bhuv where it is written like this?

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

0
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

If still someone is unable to understand the following part

Expand $(1-x^{10})^6$, and every time if power x goes more than 19 leave that term.
once you expand it, there will be only two terms useful to us first is $1$ and second is $-6x^{10}$
If we multiply 1 with $x^{19}$ and $-6x^{10}$ with $x^9$ we get $x^{19}$
1 has + sign and $-6x^{10}$ has -ve sign.
Coefficient of $x^{19}$ will be 24C19 - 6*14C9 = 30,492. 

0

@Manu Thakur

$\left ( 1-x \right )^{-6}$

then why it's expansion is

$\binom{5+r}{r}$

should it not be $\binom{6+r}{r}$

as 6 is in power of -ve series?

+1

@Srestha
it is because formula is n+r-1Cr
1 has been subtracted.

+2 votes
Without using generating functions.

From inclusion exclusion principle $Total \ objects = \ Total \ combinations\ - \ combinations \ with \ a\  digit > 9 \ =  C(24,19) \ -\ 6*C(14,9) $
answered by Loyal (6.2k points)
edited by
0

Aghori can you explain in etail brother ,  i know formula for mutual  exclusion but  how many

terms will be there in  n(AUBUCU...)  how you got 24  thanks advance 

0
@sumitgoyal1 assign x1 of the digit value 10, now equation becomes = x1 + x2 +...+x6 = 9. you can do this for all the 6 digits. so subtract them finally from the overall combinations.
0
thanks


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

40,965 questions
47,600 answers
146,681 comments
62,338 users