Generalized permutation and combination

Question

How many positive integers less than 1,000,000 have the sum of their digits equal to 19? (using generating function)

Comments

$\binom{24}{19} - 6*\binom{14}{9} = 30492$

---

pls give detail approach . yes ans is correct.

Answer 1

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

Comments

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

---

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

---

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

Answer 2

Without using generating functions.

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

Comments

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.

---

thanks