How-many-6-digit-numbers-exist-whose-digits-have-exactly-the-sum-13-for-example-120505-is-such-a-number-

Question Number 102816 by mr W last updated on 11/Jul/20

$${How}\:{many}\:\mathrm{6}\:{digit}\:{numbers}\:{exist} \\ $$$${whose}\:{digits}\:{have}\:{exactly}\:{the}\:{sum}\:\mathrm{13}? \\ $$$$ \\ $$$${for}\:{example}\:\mathrm{120505}\:{is}\:{such}\:{a}\:{number}. \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

Universal Set {0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3, 4,4,4,5,5,6,6,7,8,9}

$$\mathrm{Universal}\:\mathrm{Set} \\ $$$$\left\{\mathrm{0},\mathrm{0},\mathrm{0},\mathrm{0},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{3},\mathrm{3},\mathrm{3},\mathrm{3},\right. \\ $$$$\left.\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{4},\mathrm{4},\mathrm{4},\mathrm{5},\mathrm{5},\mathrm{6},\mathrm{6},\mathrm{7},\mathrm{8},\mathrm{9}\right\} \\ $$

Commented by aurpeyz last updated on 11/Jul/20

660100 508000 309000...it will be much o. how should this be[done?

$$\mathrm{660100}\:\mathrm{508000}\:\mathrm{309000}…\mathrm{it}\:\mathrm{will}\:\mathrm{be}\:\mathrm{much}\:\mathrm{o}.\:\mathrm{how}\:\mathrm{should}\:\mathrm{this}\:\mathrm{be}\left[\mathrm{done}?\right. \\ $$

Commented by mr W last updated on 11/Jul/20

$${Rasheed}\:{sir}:\:{i}\:{don}'{t}\:{know}\:{much} \\ $$$${about}\:{set}\:{methods}.\:{can}\:{you}\:{give}\:{some} \\ $$$${explanation}\:{and}\:{how}\:{to}\:{arrive}\:{at}\:{the} \\ $$$${result}?\:{thanks}! \\ $$

Commented by mr W last updated on 11/Jul/20

$${i}\:{see},\:{thanks}!\:{do}\:{you}\:{have}\:{other}\:{ideas}? \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

Sir, actually it′s not much helpfull,I think now.I only extended the set{0,1,2,...,9} by writing maximum possible occurigs of each digit in the required numbers.

$${Sir},\:{actually}\:{it}'{s}\:{not}\:{much} \\ $$$${helpfull},{I}\:{think}\:{now}.{I}\:{only}\:\: \\ $$$${extended}\:{the}\:{set}\left\{\mathrm{0},\mathrm{1},\mathrm{2},…,\mathrm{9}\right\}\:{by} \\ $$$${writing}\:{maximum}\:{possible}\: \\ $$$${occurigs}\:{of}\:{each}\:{digit}\:{in}\:{the}\: \\ $$$${required}\:{numbers}. \\ $$

Commented by mr W last updated on 11/Jul/20

$${i}\:{got}\:\mathrm{6027}\:{such}\:{numbers}. \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

Sir I thought to attack the problem as follows: (i) To determine the number of partions(in an order) of 13 using above ′universal set′ {0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3, 4,4,4,5,5,6,6,7,8,9} (ii)To determine number of ′permutations′ of each partitions. (iii)After than number of excluding unwanted numbers. I am not confident of these ideas.You can do better.

$${Sir}\:{I}\:{thought}\:{to}\:{attack}\:{the} \\ $$$${problem}\:{as}\:{follows}: \\ $$$$\left({i}\right)\:\mathcal{T}{o}\:{determine}\:{the}\:{number} \\ $$$${of}\:{partions}\left({in}\:{an}\:{order}\right) \\ $$$${of}\:\mathrm{13}\:{using}\:{above}\:'{universal}\:{set}' \\ $$$$\left\{\mathrm{0},\mathrm{0},\mathrm{0},\mathrm{0},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{1},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{2},\mathrm{3},\mathrm{3},\mathrm{3},\mathrm{3},\right. \\ $$$$\left.\:\:\:\:\:\:\:\:\:\mathrm{4},\mathrm{4},\mathrm{4},\mathrm{5},\mathrm{5},\mathrm{6},\mathrm{6},\mathrm{7},\mathrm{8},\mathrm{9}\right\} \\ $$$$\left({ii}\right)\mathcal{T}{o}\:{determine}\:{number}\:{of} \\ $$$$'{permutations}'\:{of}\:{each} \\ $$$${partitions}. \\ $$$$\left({iii}\right){After}\:{than}\:{number}\:{of} \\ $$$${excluding}\:{unwanted}\:{numbers}. \\ $$$$\:\:\:\:\:{I}\:{am}\:{not}\:{confident}\:{of}\:{these} \\ $$$${ideas}.{You}\:{can}\:{do}\:{better}. \\ $$

Commented by prakash jain last updated on 11/Jul/20

This method i think is known as generating function method, used in problem involving coins etc.

Commented by prakash jain last updated on 11/Jul/20

Thanks. I will recheck calculation for both methods.

$$\mathrm{Thanks}.\:\mathrm{I}\:\mathrm{will}\:\mathrm{recheck}\:\mathrm{calculation} \\ $$$$\mathrm{for}\:\mathrm{both}\:\mathrm{methods}. \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

Sir itis really hard . But I might find a different way. For instance let find the 3 digits numbers in between 100 and 200 whose digit sum is 12 Sum of digits Numbers 1 −−−−100 2−−−−101−−−−110 3−−−−102−−−−111−−−−120 4−−−−103−−−−112−−−−121−−−−130 5−−−−104−−−−113−−−−122−−−−131 6−−−−105−−−−114−−−−123−−−−132 7−−−−106−−−−115−−−−124−−−−133 8−−−−107−−−−116−−−−125−−−−134 9−−−−108−−−−117−−−−126−−−−135 10−−− 109−−−−118−−−− 127−−−−136 11−−−−−−−−−119−−−−128−−−−137 12−−−−−−−−−−−−−−−129−−−−138 and so on.. so the first number is 129 and the last number is 129+9×n<200 n=7 ∴ no. of 3 digits number whose sum is 12 is = 7+1=8 sir is it can be helpful for such problems ? Sir Rasheed and Mr.Wsir please share your comments.

$$\mathrm{Sir}\:\mathrm{itis}\:\mathrm{really}\:\mathrm{hard}\:.\:\mathrm{But}\:\mathrm{I}\:\mathrm{might}\:\mathrm{find}\:\mathrm{a}\:\mathrm{different} \\ $$$$\mathrm{way}. \\ $$$$\mathrm{For}\:\mathrm{instance}\:\mathrm{let}\:\mathrm{find}\:\mathrm{the}\:\mathrm{3}\:\mathrm{digits}\:\mathrm{numbers}\:\mathrm{in}\:\mathrm{between} \\ $$$$\mathrm{100}\:\mathrm{and}\:\mathrm{200}\:\mathrm{whose}\:\mathrm{digit}\:\mathrm{sum}\:\mathrm{is}\:\mathrm{12}\: \\ $$$$\boldsymbol{\mathrm{Sum}}\:\boldsymbol{\mathrm{of}}\:\boldsymbol{\mathrm{digits}}\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{Numbers}} \\ $$$$\mathrm{1}\:−−−−\mathrm{100} \\ $$$$\mathrm{2}−−−−\mathrm{101}−−−−\mathrm{110} \\ $$$$\mathrm{3}−−−−\mathrm{102}−−−−\mathrm{111}−−−−\mathrm{120} \\ $$$$\mathrm{4}−−−−\mathrm{103}−−−−\mathrm{112}−−−−\mathrm{121}−−−−\mathrm{130} \\ $$$$\mathrm{5}−−−−\mathrm{104}−−−−\mathrm{113}−−−−\mathrm{122}−−−−\mathrm{131} \\ $$$$\mathrm{6}−−−−\mathrm{105}−−−−\mathrm{114}−−−−\mathrm{123}−−−−\mathrm{132} \\ $$$$\mathrm{7}−−−−\mathrm{106}−−−−\mathrm{115}−−−−\mathrm{124}−−−−\mathrm{133} \\ $$$$\mathrm{8}−−−−\mathrm{107}−−−−\mathrm{116}−−−−\mathrm{125}−−−−\mathrm{134} \\ $$$$\mathrm{9}−−−−\mathrm{108}−−−−\mathrm{117}−−−−\mathrm{126}−−−−\mathrm{135} \\ $$$$\mathrm{10}−−−\:\mathrm{109}−−−−\mathrm{118}−−−−\:\mathrm{127}−−−−\mathrm{136} \\ $$$$\mathrm{11}−−−−−−−−−\mathrm{119}−−−−\mathrm{128}−−−−\mathrm{137} \\ $$$$\mathrm{12}−−−−−−−−−−−−−−−\mathrm{129}−−−−\mathrm{138} \\ $$$$\boldsymbol{\mathrm{and}}\:\boldsymbol{\mathrm{so}}\:\boldsymbol{\mathrm{on}}.. \\ $$$$\boldsymbol{\mathrm{so}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{first}}\:\boldsymbol{\mathrm{number}}\:\boldsymbol{\mathrm{is}}\:\mathrm{129}\:\boldsymbol{\mathrm{and}}\:\boldsymbol{\mathrm{the}}\:\boldsymbol{\mathrm{last}}\:\boldsymbol{\mathrm{number}}\: \\ $$$$\boldsymbol{\mathrm{is}}\:\mathrm{129}+\mathrm{9}×\boldsymbol{\mathrm{n}}<\mathrm{200} \\ $$$$\boldsymbol{\mathrm{n}}=\mathrm{7} \\ $$$$\therefore\:\mathrm{no}.\:\mathrm{of}\:\mathrm{3}\:\mathrm{digits}\:\mathrm{number}\:\mathrm{whose}\:\mathrm{sum}\:\mathrm{is}\:\mathrm{12}\:\mathrm{is} \\ $$$$=\:\mathrm{7}+\mathrm{1}=\mathrm{8} \\ $$$$\mathrm{sir}\:\mathrm{is}\:\mathrm{it}\:\mathrm{can}\:\mathrm{be}\:\mathrm{helpful}\:\mathrm{for}\:\mathrm{such}\:\mathrm{problems}\:? \\ $$$$\mathrm{Sir}\:\mathrm{Rasheed}\:\mathrm{and}\:\mathrm{Mr}.\mathrm{Wsir}\:\mathrm{please}\:\mathrm{share}\:\mathrm{your} \\ $$$$\mathrm{comments}. \\ $$

Commented by mr W last updated on 11/Jul/20

yes! this is the best method to solve. please recheck your formula, i think it contains an error. i got: C_5 ^(17) −C_5 ^8 −5C_5 ^7 =6027

$${yes}!\:{this}\:{is}\:{the}\:{best}\:{method}\:{to}\:{solve}. \\ $$$${please}\:{recheck}\:{your}\:{formula},\:{i}\:{think} \\ $$$${it}\:{contains}\:{an}\:{error}.\:{i}\:{got}: \\ $$$${C}_{\mathrm{5}} ^{\mathrm{17}} −{C}_{\mathrm{5}} ^{\mathrm{8}} −\mathrm{5}{C}_{\mathrm{5}} ^{\mathrm{7}} =\mathrm{6027} \\ $$

Commented by mr W last updated on 11/Jul/20

$${big}\:{thanks}\:{to}\:{all}\:{for}\:{the}\:{many}\:{ideas}! \\ $$

Commented by prakash jain last updated on 11/Jul/20

$$\mathrm{See}\:\mathrm{Q22040} \\ $$

Commented by prakash jain last updated on 11/Jul/20

$$\mathrm{Q55502} \\ $$

Commented by prakash jain last updated on 11/Jul/20

Several other questions answered by mr W only using method. mr W, is the same method not applicable here. I did remember some previous questions so searched.

$$\mathrm{Several}\:\mathrm{other}\:\mathrm{questions}\:\mathrm{answered} \\ $$$$\mathrm{by}\:\mathrm{mr}\:\mathrm{W}\:\mathrm{only}\:\mathrm{using}\:\mathrm{method}. \\ $$$$\mathrm{mr}\:\mathrm{W},\:\mathrm{is}\:\mathrm{the}\:\mathrm{same}\:\mathrm{method}\:\mathrm{not} \\ $$$$\mathrm{applicable}\:\mathrm{here}. \\ $$$$\mathrm{I}\:\mathrm{did}\:\mathrm{remember}\:\mathrm{some}\:\mathrm{previous}\: \\ $$$$\mathrm{questions}\:\mathrm{so}\:\mathrm{searched}. \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{sirs} \\ $$

Commented by mr W last updated on 11/Jul/20

$${there}\:{is}\:{no}\:{standard}\:{way}\:{for}\:{such} \\ $$$${problems}.\:{the}\:{way}\:{you}\:{are}\:{trying}\:{can} \\ $$$${reach}\:{the}\:{goal},\:{but}\:{it}\:{could}\:{be}\:{tough}. \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

Sir an idea comes to me! If sum of digits is 13 that means numbers which leaves remainder 1 when they′re divided by 3. That is 3k+1 type numbers. The numbers leaves remainder 4 when they′re divided by 9. That is the numbers of 9k+4 types....Some extra numbers ....

$${Sir}\:{an}\:{idea}\:{comes}\:{to}\:{me}!\:{If}\:{sum} \\ $$$${of}\:{digits}\:{is}\:\mathrm{13}\:{that}\:{means} \\ $$$${numbers}\:{which}\:{leaves} \\ $$$${remainder}\:\mathrm{1}\:{when}\:{they}'{re} \\ $$$${divided}\:{by}\:\mathrm{3}.\:{That}\:{is}\:\mathrm{3}{k}+\mathrm{1}\:{type} \\ $$$${numbers}. \\ $$$$\:\mathcal{T}{he}\:{numbers}\:{leaves}\:{remainder} \\ $$$$\mathrm{4}\:{when}\:{they}'{re}\:{divided}\:{by}\:\mathrm{9}. \\ $$$$\mathcal{T}{hat}\:{is}\:{the}\:{numbers}\:{of}\:\mathrm{9}{k}+\mathrm{4} \\ $$$${types}….{Some}\:{extra}\:{numbers} \\ $$$$…. \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

sir but the number 300001 =3×100000+1 but 3+0+0+0+0+1≠13 and 3×94528+1=283585≠13

$$\mathrm{sir}\:\mathrm{but}\:\mathrm{the}\:\mathrm{number} \\ $$$$\mathrm{300001}\:=\mathrm{3}×\mathrm{100000}+\mathrm{1} \\ $$$$\mathrm{but}\:\mathrm{3}+\mathrm{0}+\mathrm{0}+\mathrm{0}+\mathrm{0}+\mathrm{1}\neq\mathrm{13} \\ $$$$\mathrm{and} \\ $$$$\mathrm{3}×\mathrm{94528}+\mathrm{1}=\mathrm{283585}\neq\mathrm{13} \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

$${Hello}\:{sir}\:{PRITHWISH}\:{SEN}! \\ $$$${You}'{re}\:{right}\:{sir}!\:{Some}\:{extra} \\ $$$${numbers}\:{will}\:{also}\:{included}.{So}… \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

Please check this 1^(st) Digit No. of numbers 9 The coefficient of 4 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 8 The coeffi. of 5 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 7 The coeffi. of 6 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 6 The coeffi. of 7 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 5 The coeffi. of 8 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 4 The coeffi. of 9 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 3 The coeffi. of 10 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 2 The coeffi. of 11 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5 1 The coeffi. of 12 in (a^0 +a^1 +a^2 +a^3 +a^4 +a^5 +a^6 +a^7 +a^8 +a^9 )^5

$$\mathrm{Please}\:\mathrm{check}\:\mathrm{this} \\ $$$$\:\mathrm{1}^{\boldsymbol{\mathrm{st}}} \:\boldsymbol{\mathrm{Digit}}\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{No}}.\:\boldsymbol{\mathrm{of}}\:\boldsymbol{\mathrm{numbers}} \\ $$$$\:\:\:\:\mathrm{9}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coefficient}}\:\boldsymbol{\mathrm{of}}\:\mathrm{4}\:\boldsymbol{\mathrm{in}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{8}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\mathrm{5}\:\boldsymbol{\mathrm{in}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{7}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{6}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{6}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{7}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{5}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{8}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{4}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{9}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{3}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{10}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{2}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{11}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\boldsymbol{\mathrm{The}}\:\boldsymbol{\mathrm{coeffi}}.\:\boldsymbol{\mathrm{of}}\:\:\mathrm{12}\:\boldsymbol{\mathrm{in}}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left(\boldsymbol{\mathrm{a}}^{\mathrm{0}} +\boldsymbol{\mathrm{a}}^{\mathrm{1}} +\boldsymbol{\mathrm{a}}^{\mathrm{2}} +\boldsymbol{\mathrm{a}}^{\mathrm{3}} +\boldsymbol{\mathrm{a}}^{\mathrm{4}} +\boldsymbol{\mathrm{a}}^{\mathrm{5}} +\boldsymbol{\mathrm{a}}^{\mathrm{6}} +\boldsymbol{\mathrm{a}}^{\mathrm{7}} +\boldsymbol{\mathrm{a}}^{\mathrm{8}} +\boldsymbol{\mathrm{a}}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \\ $$

Commented by prakash jain last updated on 11/Jul/20

First digits 1 to 9 rest all 0 to 9 (x^1 +....+x^9 )(1+...+x^9 )^5 Digits with sum 13 is given by coefficient of x^(13) in above expression. ((x(1−x^9 ))/(1−x))×(((1−x^(10) )^5 )/((1−x)^5 )) =x(1−x^9 −x^(10) +higherpower)(1−x)^(−6) =x(1−x^9 −5x^(10) )(1+Σ_(i=1) ^∞ ^(6+i−1) C_i x^i ) =(x−x^(10) −x^(11) )(...) Terms in ()that will given x^(13 ) x^(12) ,x^3 ,x^2 ^(17) C_5 −^8 C_3 −5^7 C_2 (correction (1−x^(10) )^5 was earlier written (1−x^(10) +..) it should be (1−5x^(10) +..)

$$\mathrm{First}\:\mathrm{digits}\:\mathrm{1}\:\mathrm{to}\:\mathrm{9} \\ $$$$\mathrm{rest}\:\mathrm{all}\:\mathrm{0}\:\mathrm{to}\:\mathrm{9} \\ $$$$\left({x}^{\mathrm{1}} +….+{x}^{\mathrm{9}} \right)\left(\mathrm{1}+…+{x}^{\mathrm{9}} \right)^{\mathrm{5}} \\ $$$$\mathrm{Digits}\:\mathrm{with}\:\mathrm{sum}\:\mathrm{13}\:\mathrm{is}\:\mathrm{given}\:\mathrm{by} \\ $$$$\mathrm{coefficient}\:\mathrm{of}\:{x}^{\mathrm{13}} \:\mathrm{in}\:\mathrm{above}\:\mathrm{expression}. \\ $$$$\frac{{x}\left(\mathrm{1}−{x}^{\mathrm{9}} \right)}{\mathrm{1}−{x}}×\frac{\left(\mathrm{1}−{x}^{\mathrm{10}} \right)^{\mathrm{5}} }{\left(\mathrm{1}−{x}\right)^{\mathrm{5}} } \\ $$$$={x}\left(\mathrm{1}−{x}^{\mathrm{9}} −{x}^{\mathrm{10}} +\mathrm{higherpower}\right)\left(\mathrm{1}−{x}\right)^{−\mathrm{6}} \\ $$$$={x}\left(\mathrm{1}−{x}^{\mathrm{9}} −\mathrm{5}{x}^{\mathrm{10}} \right)\left(\mathrm{1}+\underset{{i}=\mathrm{1}} {\overset{\infty} {\sum}}\:^{\mathrm{6}+{i}−\mathrm{1}} {C}_{{i}} {x}^{{i}} \right) \\ $$$$=\left({x}−{x}^{\mathrm{10}} −{x}^{\mathrm{11}} \right)\left(…\right) \\ $$$$\mathrm{Terms}\:\mathrm{in}\:\left(\right)\mathrm{that}\:\mathrm{will}\:\mathrm{given}\:{x}^{\mathrm{13}\:} \: \\ $$$${x}^{\mathrm{12}} ,{x}^{\mathrm{3}} ,{x}^{\mathrm{2}} \\ $$$$\:\:^{\mathrm{17}} {C}_{\mathrm{5}} −^{\mathrm{8}} {C}_{\mathrm{3}} −\mathrm{5}\:^{\mathrm{7}} {C}_{\mathrm{2}} \\ $$$$\left(\mathrm{correction}\:\left(\mathrm{1}−{x}^{\mathrm{10}} \right)^{\mathrm{5}} \:\mathrm{was}\right. \\ $$$$\mathrm{earlier}\:\mathrm{written}\:\left(\mathrm{1}−{x}^{\mathrm{10}} +..\right) \\ $$$$\mathrm{it}\:\mathrm{should}\:\mathrm{be}\:\left(\mathrm{1}−\mathrm{5}{x}^{\mathrm{10}} +..\right) \\ $$

Commented by mr W last updated on 11/Jul/20

$${yes}\:{sir}!\:{i}\:{solved}\:{similar}\:{questions} \\ $$$${sometimes}\:{ago},\:{but}\:{i}\:{can}'{t}\:{remember} \\ $$$${the}\:{old}\:{posts}.\:{how}\:{did}\:{you}\:{find}\:{these} \\ $$$${old}\:{posts}? \\ $$

Commented by prakash jain last updated on 11/Jul/20

I searched for generating or just generat etc. tried 2−3 search text.

$$\mathrm{I}\:\mathrm{searched}\:\mathrm{for}\:\mathrm{generating}\:\mathrm{or}\:\mathrm{just} \\ $$$$\mathrm{generat}\:\mathrm{etc}.\:\mathrm{tried}\:\mathrm{2}−\mathrm{3}\:\mathrm{search}\:\mathrm{text}. \\ $$

Commented by mr W last updated on 11/Jul/20

$${thanks}\:{sir}!\:{in}\:{this}\:{way}\:{one}\:{can}\:{find} \\ $$$${some}\:{old}\:{posts},\:{great}! \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

sir prakash jain i think your 2^(nd) expression will be (1+....+x^9 )^5 not 6

$$\mathrm{sir}\:\mathrm{prakash}\:\mathrm{jain} \\ $$$$\mathrm{i}\:\mathrm{think}\:\mathrm{your}\:\mathrm{2}^{\mathrm{nd}} \mathrm{expression}\:\mathrm{will}\:\mathrm{be} \\ $$$$\left(\mathrm{1}+….+\mathrm{x}^{\mathrm{9}} \right)^{\mathrm{5}} \:\mathrm{not}\:\mathrm{6} \\ $$

Commented by prakash jain last updated on 11/Jul/20

$${yes}.\:{it}\:{is}\:\mathrm{5}. \\ $$

Commented by prakash jain last updated on 11/Jul/20

$${ok}.\:{I}\:{realize}\:{now}.\:{in}\:{previous}\:{step} \\ $$$${i}\:{have}\:{written}\:{six}. \\ $$

Answered by mr W last updated on 11/Jul/20

let′s look at the general case: how many n digit numbers exist whose digits have exactly the sum m? say such a number is d_1 d_2 d_3 ...d_n with the conditions: 1≤d_1 ≤9 0≤d_2 ,d_3 ,...,d_n ≤9 so the question is how many integral solutions the following equation d_1 +d_2 +d_3 +...+d_n =m ...(I) has under the given conditions. we can use the generating functions for d_1 : x+x^2 +x^3 +...+x^9 for d_2 ,d_3 ,...,d_n : 1+x+x^2 +x^3 +...+x^9 for d_1 +d_2 +d_3 +...+d_n it is then (x+x^2 +x^3 +...+x^9 )(1+x+x^2 +x^3 +...+x^9 )^(n−1) =((x(1−x^9 )(1−x^(10) )^(n−1) )/((1−x)^n )) =x(1−x^9 )(1−x^(10) )^(n−1) Σ_(k=0) ^∞ C_(n−1) ^(k+n−1) x^k =x(1−x^9 )[Σ_(r=0) ^(n−1) (−1)^r C_r ^(n−1) x^(10r) ][Σ_(k=0) ^∞ C_(n−1) ^(k+n−1) x^k ] the coefficient of the x^m term in this generating function represents the number of solutions of eqn. (I). example: n=6, m=13 GF=x(1−x^9 )(1−5x^(10) +...)Σ_(k=0) ^∞ C_5 ^(k+5) x^k =x(1−x^9 −5x^(10) +...)Σ_(k=0) ^∞ C_5 ^(k+5) x^k coefficient of x^(13) term is (for k=12, 3, 2) C_5 ^(17) −C_5 ^8 −5C_5 ^7 =6027

$${let}'{s}\:{look}\:{at}\:{the}\:{general}\:{case}: \\ $$$${how}\:{many}\:{n}\:{digit}\:{numbers}\:{exist} \\ $$$${whose}\:{digits}\:{have}\:{exactly}\:{the}\:{sum}\:{m}? \\ $$$${say}\:{such}\:{a}\:{number}\:{is} \\ $$$${d}_{\mathrm{1}} {d}_{\mathrm{2}} {d}_{\mathrm{3}} …{d}_{{n}} \\ $$$${with}\:{the}\:{conditions}: \\ $$$$\mathrm{1}\leqslant{d}_{\mathrm{1}} \leqslant\mathrm{9} \\ $$$$\mathrm{0}\leqslant{d}_{\mathrm{2}} ,{d}_{\mathrm{3}} ,…,{d}_{{n}} \leqslant\mathrm{9} \\ $$$${so}\:{the}\:{question}\:{is}\:{how}\:{many}\:{integral} \\ $$$${solutions}\:{the}\:{following}\:{equation} \\ $$$${d}_{\mathrm{1}} +{d}_{\mathrm{2}} +{d}_{\mathrm{3}} +…+{d}_{{n}} ={m}\:\:\:…\left({I}\right) \\ $$$${has}\:{under}\:{the}\:{given}\:{conditions}. \\ $$$${we}\:{can}\:{use}\:{the}\:{generating}\:{functions} \\ $$$${for}\:{d}_{\mathrm{1}} :\:{x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} +…+{x}^{\mathrm{9}} \\ $$$${for}\:{d}_{\mathrm{2}} ,{d}_{\mathrm{3}} ,…,{d}_{{n}} :\:\mathrm{1}+{x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} +…+{x}^{\mathrm{9}} \\ $$$${for}\:{d}_{\mathrm{1}} +{d}_{\mathrm{2}} +{d}_{\mathrm{3}} +…+{d}_{{n}} \:{it}\:{is}\:{then} \\ $$$$\left({x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} +…+{x}^{\mathrm{9}} \right)\left(\mathrm{1}+{x}+{x}^{\mathrm{2}} +{x}^{\mathrm{3}} +…+{x}^{\mathrm{9}} \right)^{{n}−\mathrm{1}} \\ $$$$=\frac{{x}\left(\mathrm{1}−{x}^{\mathrm{9}} \right)\left(\mathrm{1}−{x}^{\mathrm{10}} \right)^{{n}−\mathrm{1}} }{\left(\mathrm{1}−{x}\right)^{{n}} } \\ $$$$={x}\left(\mathrm{1}−{x}^{\mathrm{9}} \right)\left(\mathrm{1}−{x}^{\mathrm{10}} \right)^{{n}−\mathrm{1}} \underset{{k}=\mathrm{0}} {\overset{\infty} {\sum}}{C}_{{n}−\mathrm{1}} ^{{k}+{n}−\mathrm{1}} {x}^{{k}} \\ $$$$={x}\left(\mathrm{1}−{x}^{\mathrm{9}} \right)\left[\underset{{r}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}\left(−\mathrm{1}\right)^{{r}} {C}_{{r}} ^{{n}−\mathrm{1}} {x}^{\mathrm{10}{r}} \right]\left[\underset{{k}=\mathrm{0}} {\overset{\infty} {\sum}}{C}_{{n}−\mathrm{1}} ^{{k}+{n}−\mathrm{1}} {x}^{{k}} \right] \\ $$$${the}\:{coefficient}\:{of}\:{the}\:{x}^{{m}} \:{term}\:{in}\:{this} \\ $$$${generating}\:{function}\:{represents}\:{the} \\ $$$${number}\:{of}\:{solutions}\:{of}\:{eqn}.\:\left({I}\right). \\ $$$$ \\ $$$${example}:\:{n}=\mathrm{6},\:{m}=\mathrm{13} \\ $$$${GF}={x}\left(\mathrm{1}−{x}^{\mathrm{9}} \right)\left(\mathrm{1}−\mathrm{5}{x}^{\mathrm{10}} +…\right)\underset{{k}=\mathrm{0}} {\overset{\infty} {\sum}}{C}_{\mathrm{5}} ^{{k}+\mathrm{5}} {x}^{{k}} \\ $$$$={x}\left(\mathrm{1}−{x}^{\mathrm{9}} −\mathrm{5}{x}^{\mathrm{10}} +…\right)\underset{{k}=\mathrm{0}} {\overset{\infty} {\sum}}{C}_{\mathrm{5}} ^{{k}+\mathrm{5}} {x}^{{k}} \\ $$$${coefficient}\:{of}\:{x}^{\mathrm{13}} \:{term}\:{is} \\ $$$$\left({for}\:{k}=\mathrm{12},\:\mathrm{3},\:\mathrm{2}\right) \\ $$$${C}_{\mathrm{5}} ^{\mathrm{17}} −{C}_{\mathrm{5}} ^{\mathrm{8}} −\mathrm{5}{C}_{\mathrm{5}} ^{\mathrm{7}} =\mathrm{6027} \\ $$

Commented by PRITHWISH SEN 2 last updated on 11/Jul/20

$$\mathrm{Thanks}\:\mathrm{sir} \\ $$

Answered by prakash jain last updated on 11/Jul/20

xxxxxxxxxxxxxxxxxx (18x) Replace any 5 of last 17 x by a bar count the number of xs between to bars to get a digit. Now this will include cases where where all 5 bars are included in 8 or less continous xs. Meaning digits has to be ≤9. # of ways to place 5 bars=^(17) C_5 one digits is 10=6×^5 C_3 +^7 C_4 +^6 C_4 =110 one digits is 11=5×^4 C_3 +^6 C_4 +^5 C_4 =55 one digits is 12=4×^3 C_3 +^5 C_4 +^4 C_4 =10 one digits is 13=1 valid outcomes =^(17) C_5 −161=6188−161=6027 count the number of x between 2 bars to get the digit. x∣10x∣5x to x6x∣10x xx∣xxx∣xxx∣∣xxx∣xx 233032 xx∣∣∣∣∣∣xxxxxxxxxxx

$${xxxxxxxxxxxxxxxxxx}\:\left(\mathrm{18}{x}\right) \\ $$$$\mathrm{Replace}\:\mathrm{any}\:\mathrm{5}\:\mathrm{of}\:\mathrm{last}\:\mathrm{17}\:{x}\:\mathrm{by}\:\mathrm{a}\:\mathrm{bar} \\ $$$$\mathrm{count}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:{xs}\:\mathrm{between} \\ $$$$\mathrm{to}\:\mathrm{bars}\:\mathrm{to}\:\mathrm{get}\:\mathrm{a}\:\mathrm{digit}. \\ $$$$\mathrm{Now}\:\mathrm{this}\:\mathrm{will}\:\mathrm{include}\:\mathrm{cases}\:\mathrm{where} \\ $$$$\mathrm{where}\:\mathrm{all}\:\mathrm{5}\:\mathrm{bars}\:\mathrm{are}\:\mathrm{included}\:\mathrm{in} \\ $$$$\mathrm{8}\:\mathrm{or}\:\mathrm{less}\:\mathrm{continous}\:{xs}.\:\mathrm{Meaning}\:\mathrm{digits} \\ $$$$\mathrm{has}\:\mathrm{to}\:\mathrm{be}\:\leqslant\mathrm{9}. \\ $$$$#\:\mathrm{of}\:\mathrm{ways}\:\mathrm{to}\:\mathrm{place}\:\mathrm{5}\:\mathrm{bars}=\:^{\mathrm{17}} {C}_{\mathrm{5}} \\ $$$$\mathrm{one}\:\mathrm{digits}\:\mathrm{is}\:\mathrm{10}=\mathrm{6}×\:^{\mathrm{5}} {C}_{\mathrm{3}} +\:^{\mathrm{7}} {C}_{\mathrm{4}} +\:^{\mathrm{6}} {C}_{\mathrm{4}} =\mathrm{110} \\ $$$$\mathrm{one}\:\mathrm{digits}\:\mathrm{is}\:\mathrm{11}=\mathrm{5}×\:^{\mathrm{4}} {C}_{\mathrm{3}} +\:^{\mathrm{6}} {C}_{\mathrm{4}} +\:^{\mathrm{5}} {C}_{\mathrm{4}} =\mathrm{55} \\ $$$$\mathrm{one}\:\mathrm{digits}\:\mathrm{is}\:\mathrm{12}=\mathrm{4}×\:^{\mathrm{3}} {C}_{\mathrm{3}} +\:^{\mathrm{5}} {C}_{\mathrm{4}} +^{\mathrm{4}} {C}_{\mathrm{4}} =\mathrm{10} \\ $$$$\mathrm{one}\:\mathrm{digits}\:\mathrm{is}\:\mathrm{13}=\mathrm{1} \\ $$$$\mathrm{valid}\:\mathrm{outcomes} \\ $$$$=^{\mathrm{17}} \mathrm{C}_{\mathrm{5}} −\mathrm{161}=\mathrm{6188}−\mathrm{161}=\mathrm{6027} \\ $$$$\mathrm{count}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:{x}\:\mathrm{between} \\ $$$$\mathrm{2}\:\mathrm{bars}\:\mathrm{to}\:\mathrm{get}\:\mathrm{the}\:\mathrm{digit}. \\ $$$${x}\mid\mathrm{10}{x}\mid\mathrm{5}{x}\:\mathrm{to}\:{x}\mathrm{6}{x}\mid\mathrm{10}{x} \\ $$$${xx}\mid{xxx}\mid{xxx}\mid\mid{xxx}\mid{xx} \\ $$$$\mathrm{233032} \\ $$$${xx}\mid\mid\mid\mid\mid\mid{xxxxxxxxxxx} \\ $$

Commented by Rasheed.Sindhi last updated on 11/Jul/20

$${Sir}\:{really}\:{useful}\:{method}!\:{I} \\ $$$${remember}\:{now}\:{that}\:{long}\:{ago}\:{I} \\ $$$${had}\:{learnt}\:{it}\:{from}\:{you}\:{but}\:{I} \\ $$$${forgot}! \\ $$

Commented by prakash jain last updated on 11/Jul/20

This method is commonly known as stars and bars. Very useful for dividing n items in m boxes. The above is a special cases where first box is not empty and other boxes can be empty but cannot contain more than 9 items.

$$\mathrm{This}\:\mathrm{method}\:\mathrm{is}\:\mathrm{commonly}\:\mathrm{known} \\ $$$$\mathrm{as}\:\mathrm{stars}\:\mathrm{and}\:\mathrm{bars}. \\ $$$$\mathrm{Very}\:\mathrm{useful}\:\mathrm{for}\:\mathrm{dividing}\:{n}\:\mathrm{items} \\ $$$$\mathrm{in}\:{m}\:\mathrm{boxes}. \\ $$$$\mathrm{The}\:\mathrm{above}\:\mathrm{is}\:\mathrm{a}\:\mathrm{special}\:\mathrm{cases}\:\mathrm{where} \\ $$$$\mathrm{first}\:\mathrm{box}\:\mathrm{is}\:\mathrm{not}\:\mathrm{empty}\:\mathrm{and}\:\mathrm{other} \\ $$$$\mathrm{boxes}\:\mathrm{can}\:\mathrm{be}\:\mathrm{empty}\:\mathrm{but}\:\mathrm{cannot} \\ $$$$\mathrm{contain}\:\mathrm{more}\:\mathrm{than}\:\mathrm{9}\:\mathrm{items}. \\ $$

Facebook Tweet Pin

How-many-6-digit-numbers-exist-whose-digits-have-exactly-the-sum-13-for-example-120505-is-such-a-number-

Leave a Reply Cancel reply