The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 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.9k points)
retagged by | 1.1k views
+7
$\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.6k points)
edited by
+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.

0

alternate way to proceed after second step in Debashish's answer.

0

Akriti sood Follow these lectures (https://trevtutor.com/discretemath/discrete-math-2/) Sufficient to cover generating functions in detailed way.

+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.3k 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

Related questions



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

44,251 questions
49,748 answers
164,061 comments
65,844 users