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

2 Answers

+27 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*}$$


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.5k points)
edited by
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}$.

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. 


@Manu Thakur

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

then why it's expansion is


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

as 6 is in power of -ve series?


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


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


Akriti sood Follow these lectures ( 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.1k points)
edited by

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 

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

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
49,548 questions
54,174 answers
71,129 users