1.1k views
How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)
retagged | 1.1k views
+7
$\binom{24}{19} - 6*\binom{14}{9} = 30492$
0
pls give detail approach . yes ans is correct.

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

edited
+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.

Without using generating functions.

From inclusion exclusion principle $Total \ objects = \ Total \ combinations\ - \ combinations \ with \ a\ digit > 9 \ = C(24,19) \ -\ 6*C(14,9)$
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

1