Previous in Permutation and Combination Next in Permutation and Combination
Question Number 188362 by mr W last updated on 28/Feb/23
$${find}\:{the}\:{number}\:{of}\:\mathrm{5}\:{digit}\:{natural} \\ $$$${numbers}\:{with}\:{strictly}\:{ascending}\: \\ $$$${digits}\:{whose}\:{sum}\:{is}\:\mathrm{20}. \\ $$$${example}:\:\mathrm{12458}\:{is}\:{such}\:{a}\:{number} \\ $$
Answered by ARUNG_Brandon_MBU last updated on 28/Feb/23
$$\mathrm{6} \\ $$
Commented by ARUNG_Brandon_MBU last updated on 28/Feb/23
#include <iostream> using namespace std; int main(void) { for (int i0, i1, i2, i3, i4, i=10000; i<100000; i++) { i0 = i/10000; i1 = i%10000/1000; i2 = i%1000/100; i3 = i%100/10; i4 = i%10; if (i0<i1 && i1<i2 && i2<i3 && i3<i4) if ((i0+i1+i2+i3+i4) == 20) cout << i <<", "; } return 0; }
Commented by ARUNG_Brandon_MBU last updated on 28/Feb/23
$$\mathrm{Output}:\:\mathrm{12359},\:\mathrm{12368},\:\mathrm{12458}, \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{12467},\:\mathrm{13457},\:\mathrm{23456}, \\ $$
Commented by mr W last updated on 28/Feb/23
$${yes}! \\ $$
Commented by ARUNG_Brandon_MBU last updated on 28/Feb/23
��
Commented by mr W last updated on 01/Mar/23
$${in}\:{this}\:{case},\:{i}\:{mean}\:{when}\:{the}\:{sum}\:{of}\: \\ $$$${digits}\:{is}\:\leqslant\mathrm{20},\:{we}\:{can}\:{still}\:{have}\:{a}\: \\ $$$${smart}\:{solution},\:{which}\:{gives}\:{us}\:{the} \\ $$$${answer}\:\mathrm{7}−\mathrm{1}=\mathrm{6}. \\ $$$$\mathrm{7}\:{is}\:{the}\:{coef}.\:{of}\:{term}\:{x}^{\mathrm{20}} \:{in}\:{the} \\ $$$${expansion}\:\underset{{k}=\mathrm{1}} {\overset{\mathrm{5}} {\prod}}\frac{{x}^{{k}} }{\mathrm{1}−{x}^{{k}} }.\:{but}\:{it}\:{includes} \\ $$$${also}\:{the}\:{case}\:{that}\:{a}\:{digit}\:{is}\:\mathrm{10},\:{which} \\ $$$${is}\:{certainly}\:{not}\:{true},\:{therefore}\:{the} \\ $$$${correct}\:{answer}\:{is}\:\mathrm{7}−\mathrm{1}=\mathrm{6}. \\ $$$${if}\:{the}\:{sum}\:{of}\:{digits}\:{is}\:>\mathrm{20},\:{i}\:{think} \\ $$$${we}\:{can}\:{only}\:{enumerate}\:{all}\:{possible} \\ $$$${possibilities}\:{as}\:{your}\:{program}\:{does}. \\ $$$${there}\:{is}\:{no}\:{smarter}\:{approach}. \\ $$
Commented by ARUNG_Brandon_MBU last updated on 28/Feb/23
����
Commented by mr W last updated on 04/Mar/23
$${i}\:{found}\:{a}\:{new}\:{way}\:{even}\:{for}\:{n}>\mathrm{20}, \\ $$$${see}\:{below}.\:{can}\:{you}\:{please}\:{check}\:{with} \\ $$$${your}\:{program}? \\ $$
Commented by ARUNG_Brandon_MBU last updated on 07/Mar/23
// for n > 20 #include <iostream> using namespace std; int main(void) { for(int i0,i1,i2,i3,i4,i=10000;i<100000;i++) { i0 = i/10000; i1 = i%10000/1000; i2 = i%1000/100; i3 = i%100/10; i4 = i%10; if (i0<i1 && i1<i2 && i2<i3 && i3<i4) if (i0+i1+i2+i3+i4 > 20) cout << i <<" "; } return 0; }
Commented by ARUNG_Brandon_MBU last updated on 07/Mar/23
Commented by ARUNG_Brandon_MBU last updated on 07/Mar/23
$$\mathrm{We}\:\mathrm{have}\:\mathrm{108}\:\mathrm{5}-\mathrm{digit}\:\mathrm{numbers}\:\mathrm{such}\:\mathrm{that} \\ $$$$\mathrm{the}\:\mathrm{digits}\:\mathrm{are}\:\mathrm{different}\:\mathrm{and}\:\mathrm{their}\:\mathrm{sum}\:>\:\mathrm{20} \\ $$
Commented by mr W last updated on 07/Mar/23
$${yes},\:{that}'{s}\:{correct}! \\ $$$${as}\:{we}\:{can}\:{see}\:{below}\:{there}\:{are} \\ $$$$\mathrm{8}\:{numbers}\:{with}\:{sum}\:\mathrm{21}, \\ $$$$\mathrm{9}\:{numbers}\:{with}\:{sum}\:\mathrm{22}, \\ $$$$\mathrm{11}\:{numbers}\:{with}\:{sum}\:\mathrm{23}, \\ $$$$... \\ $$$$\mathrm{2}\:{numbers}\:{with}\:{sum}\:\mathrm{33}, \\ $$$$\mathrm{1}\:{number}\:{with}\:{sum}\:\mathrm{34}, \\ $$$$\mathrm{1}\:{number}\:{with}\:{sum}\:\mathrm{35}. \\ $$$${so}\:{totally}\:\mathrm{108}\:{numbers}\:{with}\:{sum}>\mathrm{20}. \\ $$
Answered by mr W last updated on 04/Mar/23
$${a}\:{new}\:{try} \\ $$$${say}\:{the}\:{number}\:{is}\:{d}_{\mathrm{1}} {d}_{\mathrm{2}} {d}_{\mathrm{3}} {d}_{\mathrm{4}} {d}_{\mathrm{5}} \:{with} \\ $$$${d}_{\mathrm{1}} +{d}_{\mathrm{2}} +{d}_{\mathrm{3}} +{d}_{\mathrm{4}} +{d}_{\mathrm{5}} ={n}\:{and} \\ $$$$\mathrm{1}\leqslant{d}_{\mathrm{1}} <{d}_{\mathrm{2}} <{d}_{\mathrm{3}} <{d}_{\mathrm{4}} <{d}_{\mathrm{5}} \leqslant\mathrm{9} \\ $$$${let}\: \\ $$$${d}_{\mathrm{1}} =\mathrm{1}+{k}_{\mathrm{1}} \:{with}\:\mathrm{0}\leqslant{k}_{\mathrm{1}} \leqslant\mathrm{8} \\ $$$${d}_{\mathrm{2}} ={d}_{\mathrm{1}} +\mathrm{1}+{k}_{\mathrm{2}} =\mathrm{2}+{k}_{\mathrm{1}} +{k}_{\mathrm{2}} \:{with}\:\mathrm{0}\leqslant{k}_{\mathrm{2}} \leqslant\mathrm{7} \\ $$$${d}_{\mathrm{3}} ={d}_{\mathrm{2}} +\mathrm{1}+{k}_{\mathrm{3}} =\mathrm{3}+{k}_{\mathrm{1}} +{k}_{\mathrm{2}} +{k}_{\mathrm{3}} \:{with}\:\mathrm{0}\leqslant{k}_{\mathrm{3}} \leqslant\mathrm{6} \\ $$$$...... \\ $$$${d}_{\mathrm{5}} ={d}_{\mathrm{4}} +\mathrm{1}+{k}_{\mathrm{4}} =\mathrm{5}+{k}_{\mathrm{1}} +{k}_{\mathrm{2}} +{k}_{\mathrm{3}} +...+{k}_{\mathrm{5}} \:{with}\:\mathrm{0}\leqslant{k}_{\mathrm{3}} \leqslant\mathrm{4} \\ $$$$\left(\mathrm{1}+\mathrm{2}+\mathrm{3}+...+\mathrm{5}\right)+\mathrm{5}{k}_{\mathrm{1}} +\mathrm{4}{k}_{\mathrm{2}} +\mathrm{3}{k}_{\mathrm{3}} +\mathrm{2}{k}_{\mathrm{4}} +{k}_{\mathrm{5}} ={n} \\ $$$${number}\:{of}\:{solutions}\:{is}\:{the}\:{coef}.\:{of} \\ $$$${term}\:{x}^{{n}} \:{in}\:{the}\:{expansion}\:{of} \\ $$$${x}^{\mathrm{15}} \underset{{r}=\mathrm{1}} {\overset{\mathrm{5}} {\prod}}\frac{\mathrm{1}−{x}^{\mathrm{10}−{r}} }{\mathrm{1}−{x}^{{r}} } \\ $$$${for}\:{n}=\mathrm{20}\:{we}\:{have}\:\mathrm{6}\:{numbers}\:{and} \\ $$$${for}\:{n}=\mathrm{25}\:{we}\:{have}\:\mathrm{12}\:{numbers}\:{etc}. \\ $$
Commented by mr W last updated on 04/Mar/23
Commented by mr W last updated on 04/Mar/23
$${in}\:{case}\:{of}\:\mathrm{6}\:{digit}\:{numbers}\:{we}\:{need} \\ $$$${to}\:{find}\:{the}\:{coef}.\:{of}\:{term}\:{x}^{{n}} \:{in} \\ $$$${x}^{\mathrm{21}} \underset{{r}=\mathrm{1}} {\overset{\mathrm{6}} {\prod}}\frac{\mathrm{1}−{x}^{\mathrm{10}−{r}} }{\mathrm{1}−{x}^{{r}} } \\ $$$${for}\:{n}=\mathrm{25}\:{we}\:{have}\:\mathrm{4}\:{numbers}\:{and} \\ $$$${for}\:{n}=\mathrm{30}\:{we}\:{have}\:\mathrm{8}\:{numbers}\:{etc}. \\ $$
Commented by mr W last updated on 04/Mar/23
