Previous in Permutation and Combination Next in Permutation and Combination
Question Number 21800 by Tinkutara last updated on 04/Oct/17
$$\mathrm{The}\:\mathrm{number}\:\mathrm{of}\:\mathrm{integers}\:\mathrm{which}\:\mathrm{lie} \\ $$$$\mathrm{between}\:\mathrm{1}\:\mathrm{and}\:\mathrm{10}^{\mathrm{6}} \:\mathrm{and}\:\mathrm{which}\:\mathrm{have}\:\mathrm{sum} \\ $$$$\mathrm{of}\:\mathrm{digits}\:\mathrm{equal}\:\mathrm{to}\:\mathrm{12}\:\mathrm{is} \\ $$
Commented by mrW1 last updated on 27/Dec/17
![For example to find such numbers with 6 digits: let abcdef be such a number. we have a+b+c+d+e+f=12 ...(i) 1≤a≤9 0≤b,c,d,e,f≤9 number of solutions for (i) is the coefficient of x^(12) in (x+x^2 +...+x^9 )(1+x+x^2 +...+x^9 )^5 =x(1+x+x^2 +...+x^8 )(1+x+x^2 +...+x^9 )^5 =((x(1−x^9 )(1−x^(10) )^5 )/((1−x)^6 )) let [x^n ] denote the coefficient of term x^n [x^(12) ] ((x(1−x^9 )(1−x^(10) )^5 )/((1−x)^6 )) =[x^(11) ] (((1−x^9 )(1−x^(10) )^5 )/((1−x)^6 )) =[x^(11) ] (1−x^9 −5x^(10) )Σ_(k=0) ^∞ C_k ^(k+5) x^k =C_(11) ^(16) −C_2 ^7 −5C_1 ^6 =4317 similarily 5 digits: C_(11) ^(15) −C_2 ^6 −4C_1 ^5 =1330 4 digits: C_(11) ^(14) −C_2 ^5 −3C_1 ^5 =342 3 digits: C_(11) ^(13) −C_2 ^4 −2C_1 ^3 =66 2 digits: C_(11) ^(12) −C_2 ^3 −C_1 ^2 =7 ⇒Σ=6062](Q22016.png)
$$\mathrm{For}\:\mathrm{example}\:\mathrm{to}\:\mathrm{find}\:\mathrm{such}\:\mathrm{numbers} \\ $$$$\mathrm{with}\:\mathrm{6}\:\mathrm{digits}: \\ $$$$\mathrm{let}\:\mathrm{abcdef}\:\mathrm{be}\:\mathrm{such}\:\mathrm{a}\:\mathrm{number}.\:\mathrm{we}\:\mathrm{have} \\ $$$$\mathrm{a}+\mathrm{b}+\mathrm{c}+\mathrm{d}+\mathrm{e}+\mathrm{f}=\mathrm{12}\:\:...\left(\mathrm{i}\right) \\ $$$$\mathrm{1}\leqslant\mathrm{a}\leqslant\mathrm{9} \\ $$$$\mathrm{0}\leqslant\mathrm{b},\mathrm{c},\mathrm{d},\mathrm{e},\mathrm{f}\leqslant\mathrm{9} \\ $$$$ \\ $$$$\mathrm{number}\:\mathrm{of}\:\mathrm{solutions}\:\mathrm{for}\:\left(\mathrm{i}\right)\:\mathrm{is}\:\mathrm{the} \\ $$$$\mathrm{coefficient}\:\mathrm{of}\:\mathrm{x}^{\mathrm{12}} \:\mathrm{in} \\ $$$$\left(\mathrm{x}+\mathrm{x}^{\mathrm{2}} +...+\mathrm{x}^{\mathrm{9}} \right)\left(\mathrm{1}+\mathrm{x}+\mathrm{x}^{\mathrm{2}} +...+\mathrm{x}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$=\mathrm{x}\left(\mathrm{1}+\mathrm{x}+\mathrm{x}^{\mathrm{2}} +...+\mathrm{x}^{\mathrm{8}} \right)\left(\mathrm{1}+\mathrm{x}+\mathrm{x}^{\mathrm{2}} +...+\mathrm{x}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$=\frac{\mathrm{x}\left(\mathrm{1}−\mathrm{x}^{\mathrm{9}} \right)\left(\mathrm{1}−\mathrm{x}^{\mathrm{10}} \right)^{\mathrm{5}} }{\left(\mathrm{1}−\mathrm{x}\right)^{\mathrm{6}} } \\ $$$$ \\ $$$$\mathrm{let}\:\left[\mathrm{x}^{\mathrm{n}} \right]\:\mathrm{denote}\:\mathrm{the}\:\mathrm{coefficient}\:\mathrm{of}\:\mathrm{term}\:\mathrm{x}^{\mathrm{n}} \\ $$$$ \\ $$$$\left[\mathrm{x}^{\mathrm{12}} \right]\:\frac{\mathrm{x}\left(\mathrm{1}−\mathrm{x}^{\mathrm{9}} \right)\left(\mathrm{1}−\mathrm{x}^{\mathrm{10}} \right)^{\mathrm{5}} }{\left(\mathrm{1}−\mathrm{x}\right)^{\mathrm{6}} } \\ $$$$=\left[\mathrm{x}^{\mathrm{11}} \right]\:\frac{\left(\mathrm{1}−\mathrm{x}^{\mathrm{9}} \right)\left(\mathrm{1}−\mathrm{x}^{\mathrm{10}} \right)^{\mathrm{5}} }{\left(\mathrm{1}−\mathrm{x}\right)^{\mathrm{6}} } \\ $$$$=\left[\mathrm{x}^{\mathrm{11}} \right]\:\left(\mathrm{1}−\mathrm{x}^{\mathrm{9}} −\mathrm{5x}^{\mathrm{10}} \right)\underset{\mathrm{k}=\mathrm{0}} {\overset{\infty} {\sum}}\mathrm{C}_{\mathrm{k}} ^{\mathrm{k}+\mathrm{5}} \mathrm{x}^{\mathrm{k}} \\ $$$$=\mathrm{C}_{\mathrm{11}} ^{\mathrm{16}} −\mathrm{C}_{\mathrm{2}} ^{\mathrm{7}} −\mathrm{5C}_{\mathrm{1}} ^{\mathrm{6}} =\mathrm{4317} \\ $$$$ \\ $$$$\mathrm{similarily} \\ $$$$\mathrm{5}\:\mathrm{digits}:\:\mathrm{C}_{\mathrm{11}} ^{\mathrm{15}} −\mathrm{C}_{\mathrm{2}} ^{\mathrm{6}} −\mathrm{4C}_{\mathrm{1}} ^{\mathrm{5}} =\mathrm{1330} \\ $$$$\mathrm{4}\:\mathrm{digits}:\:\mathrm{C}_{\mathrm{11}} ^{\mathrm{14}} −\mathrm{C}_{\mathrm{2}} ^{\mathrm{5}} −\mathrm{3C}_{\mathrm{1}} ^{\mathrm{5}} =\mathrm{342} \\ $$$$\mathrm{3}\:\mathrm{digits}:\:\mathrm{C}_{\mathrm{11}} ^{\mathrm{13}} −\mathrm{C}_{\mathrm{2}} ^{\mathrm{4}} −\mathrm{2C}_{\mathrm{1}} ^{\mathrm{3}} =\mathrm{66} \\ $$$$\mathrm{2}\:\mathrm{digits}:\:\mathrm{C}_{\mathrm{11}} ^{\mathrm{12}} −\mathrm{C}_{\mathrm{2}} ^{\mathrm{3}} −\mathrm{C}_{\mathrm{1}} ^{\mathrm{2}} =\mathrm{7} \\ $$$$\Rightarrow\Sigma=\mathrm{6062} \\ $$
Commented by Tinkutara last updated on 09/Oct/17
$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{very}\:\mathrm{much}\:\mathrm{Sir}! \\ $$