Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

Question Number 21933 by Tinkutara last updated on 07/Oct/17

Let n_1 < n_2 < n_3 < n_4 < n_5 be positive integers such that n_1 + n_2 + n_3 + n_4 + n_5 = 20. Then the number of such distinct arrangements (n_1 , n_2 , n_3 , n_4 , n_5 ) is

$$\mathrm{Let}\:{n}_{\mathrm{1}} \:<\:{n}_{\mathrm{2}} \:<\:{n}_{\mathrm{3}} \:<\:{n}_{\mathrm{4}} \:<\:{n}_{\mathrm{5}} \:\mathrm{be}\:\mathrm{positive} \\ $$ $$\mathrm{integers}\:\mathrm{such}\:\mathrm{that}\:{n}_{\mathrm{1}} \:+\:{n}_{\mathrm{2}} \:+\:{n}_{\mathrm{3}} \:+\:{n}_{\mathrm{4}} \:+ \\ $$ $${n}_{\mathrm{5}} \:=\:\mathrm{20}.\:\mathrm{Then}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{such} \\ $$ $$\mathrm{distinct}\:\mathrm{arrangements}\:\left({n}_{\mathrm{1}} ,\:{n}_{\mathrm{2}} ,\:{n}_{\mathrm{3}} ,\:{n}_{\mathrm{4}} ,\:{n}_{\mathrm{5}} \right) \\ $$ $$\mathrm{is} \\ $$

Commented bymrW1 last updated on 08/Oct/17

7 ? 1 2 3 4 10 1 2 3 5 9 1 2 3 6 8 1 2 4 5 8 1 2 4 6 7 1 2 4 5 6 ⇒ should be 1 3 4 5 7 2 3 4 5 6

$$\mathrm{7}\:? \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{3}\:\:\mathrm{4}\:\:\mathrm{10} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{3}\:\:\mathrm{5}\:\:\mathrm{9} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{3}\:\:\mathrm{6}\:\:\mathrm{8} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{8} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{4}\:\:\mathrm{6}\:\:\mathrm{7} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{6}\:\:\Rightarrow\:\mathrm{should}\:\mathrm{be}\:\mathrm{1}\:\:\mathrm{3}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{7} \\ $$ $$\mathrm{2}\:\:\mathrm{3}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{6} \\ $$

Commented byRasheed.Sindhi last updated on 08/Oct/17

1+3+4+5+7

$$\mathrm{1}+\mathrm{3}+\mathrm{4}+\mathrm{5}+\mathrm{7} \\ $$

Commented byRasheed.Sindhi last updated on 08/Oct/17

line number last but one 1 2 4 5 6 1 + 2 + 4 + 5 + 6 =18? If this line is replaced by 1 3 4 5 7 the answer is 7 yet

$$\mathrm{line}\:\mathrm{number}\:\mathrm{last}\:\mathrm{but}\:\mathrm{one} \\ $$ $$\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{6} \\ $$ $$\mathrm{1}\:+\:\mathrm{2}\:+\:\mathrm{4}\:+\:\mathrm{5}\:+\:\mathrm{6}\:=\mathrm{18}? \\ $$ $$\mathrm{If}\:\mathrm{this}\:\mathrm{line}\:\mathrm{is}\:\mathrm{replaced}\:\mathrm{by} \\ $$ $$\mathrm{1}\:\:\mathrm{3}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{7} \\ $$ $$\mathrm{the}\:\mathrm{answer}\:\mathrm{is}\:\mathrm{7}\:\mathrm{yet} \\ $$

Commented byTinkutara last updated on 08/Oct/17

mrW1, why you don′t take 1+3+4+5+7? But your answer 7 is correct.

$$\mathrm{mrW1},\:\mathrm{why}\:\mathrm{you}\:\mathrm{don}'\mathrm{t}\:\mathrm{take}\:\mathrm{1}+\mathrm{3}+\mathrm{4}+\mathrm{5}+\mathrm{7}? \\ $$ $$\mathrm{But}\:\mathrm{your}\:\mathrm{answer}\:\mathrm{7}\:\mathrm{is}\:\mathrm{correct}. \\ $$

Commented bymrW1 last updated on 08/Oct/17

Thanks to you both! I made a mistake. 1 3 4 5 7 is correct, not 1 2 4 5 6.

$$\mathrm{Thanks}\:\mathrm{to}\:\mathrm{you}\:\mathrm{both}!\:\mathrm{I}\:\mathrm{made}\:\mathrm{a}\:\mathrm{mistake}. \\ $$ $$\mathrm{1}\:\:\mathrm{3}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{7}\:\:\mathrm{is}\:\mathrm{correct},\:\mathrm{not}\:\mathrm{1}\:\:\mathrm{2}\:\:\mathrm{4}\:\:\mathrm{5}\:\:\mathrm{6}. \\ $$

Commented bymrW1 last updated on 09/Oct/17

Certainly we don′t need to list all the concrete solutions if we only need to know how many solutions exist. Besides for large numbers, for example 100 instead of 20, it′s not easy to list all the possible solutions. We need to know the number of solutions for n_1 +n_2 +n_3 +n_4 +n_5 =20 under the condition 1≤n_1 <n_2 <n_3 <n_4 <n_5 if we replace n_1 =a_1 +1 n_2 =a_2 +2 n_3 =a_3 +3 n_4 =a_4 +4 n_5 =a_5 +5 then the equation n_1 +n_2 +n_3 +n_4 +n_5 =20 will change to a_1 +a_2 +a_3 +a_4 +a_5 =5 and the condiction 1≤n_1 <n_2 <n_3 <n_4 <n_5 will change to 0≤a_1 ≤a_2 ≤a_3 ≤a_4 ≤a_5 but the number of solutions of a_1 +a_2 +a_3 +a_4 +a_5 =5 under the condition 0≤a_1 ≤a_2 ≤a_3 ≤a_4 ≤a_5 means the number of partitions of the integer 5 which is denoted by P(5). P(5)=7 ⇒ number of solutions is 7. the 7 partitions of the integer 5 are: a_1 + a_2 + a_3 + a_4 + a_5 ⇒ n_1 n_2 n_3 n_4 n_5 0 0 0 0 5 1 2 3 4 10 0 0 0 1 4 1 2 3 5 9 0 0 0 2 3 1 2 3 6 8 0 0 1 1 3 1 2 4 5 8 0 0 1 2 2 1 2 4 6 7 0 1 1 1 2 1 3 4 5 7 1 1 1 1 1 2 3 4 5 6

$$\mathrm{Certainly}\:\mathrm{we}\:\mathrm{don}'\mathrm{t}\:\mathrm{need}\:\mathrm{to}\:\mathrm{list}\:\mathrm{all}\:\mathrm{the} \\ $$ $$\mathrm{concrete}\:\mathrm{solutions}\:\mathrm{if}\:\mathrm{we}\:\mathrm{only}\:\mathrm{need}\:\mathrm{to} \\ $$ $$\mathrm{know}\:\mathrm{how}\:\mathrm{many}\:\mathrm{solutions}\:\mathrm{exist}.\:\mathrm{Besides} \\ $$ $$\mathrm{for}\:\mathrm{large}\:\mathrm{numbers},\:\mathrm{for}\:\mathrm{example}\:\mathrm{100}\:\mathrm{instead} \\ $$ $$\mathrm{of}\:\mathrm{20},\:\mathrm{it}'\mathrm{s}\:\mathrm{not}\:\mathrm{easy}\:\mathrm{to}\:\mathrm{list}\:\mathrm{all}\:\mathrm{the}\:\mathrm{possible} \\ $$ $$\mathrm{solutions}. \\ $$ $$ \\ $$ $$\mathrm{We}\:\mathrm{need}\:\mathrm{to}\:\mathrm{know}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{solutions}\:\mathrm{for} \\ $$ $$\mathrm{n}_{\mathrm{1}} +\mathrm{n}_{\mathrm{2}} +\mathrm{n}_{\mathrm{3}} +\mathrm{n}_{\mathrm{4}} +\mathrm{n}_{\mathrm{5}} =\mathrm{20} \\ $$ $$\mathrm{under}\:\mathrm{the}\:\mathrm{condition} \\ $$ $$\mathrm{1}\leqslant\mathrm{n}_{\mathrm{1}} <\mathrm{n}_{\mathrm{2}} <\mathrm{n}_{\mathrm{3}} <\mathrm{n}_{\mathrm{4}} <\mathrm{n}_{\mathrm{5}} \\ $$ $$ \\ $$ $$\mathrm{if}\:\mathrm{we}\:\mathrm{replace} \\ $$ $$\mathrm{n}_{\mathrm{1}} =\mathrm{a}_{\mathrm{1}} +\mathrm{1} \\ $$ $$\mathrm{n}_{\mathrm{2}} =\mathrm{a}_{\mathrm{2}} +\mathrm{2} \\ $$ $$\mathrm{n}_{\mathrm{3}} =\mathrm{a}_{\mathrm{3}} +\mathrm{3} \\ $$ $$\mathrm{n}_{\mathrm{4}} =\mathrm{a}_{\mathrm{4}} +\mathrm{4} \\ $$ $$\mathrm{n}_{\mathrm{5}} =\mathrm{a}_{\mathrm{5}} +\mathrm{5} \\ $$ $$\mathrm{then} \\ $$ $$\mathrm{the}\:\mathrm{equation}\:\mathrm{n}_{\mathrm{1}} +\mathrm{n}_{\mathrm{2}} +\mathrm{n}_{\mathrm{3}} +\mathrm{n}_{\mathrm{4}} +\mathrm{n}_{\mathrm{5}} =\mathrm{20} \\ $$ $$\mathrm{will}\:\mathrm{change}\:\mathrm{to}\:\mathrm{a}_{\mathrm{1}} +\mathrm{a}_{\mathrm{2}} +\mathrm{a}_{\mathrm{3}} +\mathrm{a}_{\mathrm{4}} +\mathrm{a}_{\mathrm{5}} =\mathrm{5} \\ $$ $$\mathrm{and} \\ $$ $$\mathrm{the}\:\mathrm{condiction}\:\mathrm{1}\leqslant\mathrm{n}_{\mathrm{1}} <\mathrm{n}_{\mathrm{2}} <\mathrm{n}_{\mathrm{3}} <\mathrm{n}_{\mathrm{4}} <\mathrm{n}_{\mathrm{5}} \\ $$ $$\mathrm{will}\:\mathrm{change}\:\mathrm{to}\:\mathrm{0}\leqslant\mathrm{a}_{\mathrm{1}} \leqslant\mathrm{a}_{\mathrm{2}} \leqslant\mathrm{a}_{\mathrm{3}} \leqslant\mathrm{a}_{\mathrm{4}} \leqslant\mathrm{a}_{\mathrm{5}} \\ $$ $$ \\ $$ $$\mathrm{but} \\ $$ $$\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{solutions}\:\mathrm{of} \\ $$ $$\mathrm{a}_{\mathrm{1}} +\mathrm{a}_{\mathrm{2}} +\mathrm{a}_{\mathrm{3}} +\mathrm{a}_{\mathrm{4}} +\mathrm{a}_{\mathrm{5}} =\mathrm{5} \\ $$ $$\mathrm{under}\:\mathrm{the}\:\mathrm{condition} \\ $$ $$\mathrm{0}\leqslant\mathrm{a}_{\mathrm{1}} \leqslant\mathrm{a}_{\mathrm{2}} \leqslant\mathrm{a}_{\mathrm{3}} \leqslant\mathrm{a}_{\mathrm{4}} \leqslant\mathrm{a}_{\mathrm{5}} \\ $$ $$\mathrm{means}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{partitions}\:\mathrm{of} \\ $$ $$\mathrm{the}\:\mathrm{integer}\:\mathrm{5}\:\mathrm{which}\:\mathrm{is}\:\mathrm{denoted}\:\mathrm{by} \\ $$ $$\mathrm{P}\left(\mathrm{5}\right). \\ $$ $$ \\ $$ $$\mathrm{P}\left(\mathrm{5}\right)=\mathrm{7}\:\Rightarrow\:\mathrm{number}\:\mathrm{of}\:\mathrm{solutions}\:\mathrm{is}\:\mathrm{7}. \\ $$ $$ \\ $$ $$\mathrm{the}\:\mathrm{7}\:\mathrm{partitions}\:\mathrm{of}\:\mathrm{the}\:\mathrm{integer}\:\mathrm{5}\:\mathrm{are}: \\ $$ $$\mathrm{a}_{\mathrm{1}} +\:\mathrm{a}_{\mathrm{2}} \:+\:\mathrm{a}_{\mathrm{3}} \:+\:\mathrm{a}_{\mathrm{4}} \:+\:\mathrm{a}_{\mathrm{5}} \:\:\:\:\Rightarrow\:\:\:\mathrm{n}_{\mathrm{1}} \:\:\:\:\mathrm{n}_{\mathrm{2}} \:\:\:\mathrm{n}_{\mathrm{3}} \:\:\:\mathrm{n}_{\mathrm{4}} \:\:\:\:\mathrm{n}_{\mathrm{5}} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{5}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\mathrm{3}\:\:\:\:\:\mathrm{4}\:\:\:\:\:\mathrm{10} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{4}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\mathrm{3}\:\:\:\:\:\mathrm{5}\:\:\:\:\:\mathrm{9} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\:\:\:\mathrm{3}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\mathrm{3}\:\:\:\:\:\mathrm{6}\:\:\:\:\:\mathrm{8} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{3}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\mathrm{4}\:\:\:\:\:\mathrm{5}\:\:\:\:\:\mathrm{8} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{0}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\mathrm{4}\:\:\:\:\:\mathrm{6}\:\:\:\:\:\mathrm{7} \\ $$ $$\mathrm{0}\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\mathrm{3}\:\:\:\:\:\mathrm{4}\:\:\:\:\:\mathrm{5}\:\:\:\:\:\mathrm{7} \\ $$ $$\mathrm{1}\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\mathrm{1}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{2}\:\:\:\:\:\:\:\mathrm{3}\:\:\:\:\:\mathrm{4}\:\:\:\:\:\mathrm{5}\:\:\:\:\:\mathrm{6} \\ $$

Commented byTinkutara last updated on 08/Oct/17

Is there any formula for partitions? How to list P(85)?

$$\mathrm{Is}\:\mathrm{there}\:\mathrm{any}\:\mathrm{formula}\:\mathrm{for}\:\mathrm{partitions}? \\ $$ $$\mathrm{How}\:\mathrm{to}\:\mathrm{list}\:\mathrm{P}\left(\mathrm{85}\right)? \\ $$

Commented bymrW1 last updated on 09/Oct/17

there is no formula to calculate the integer partitions directly. usually we use generating functions.

$$\mathrm{there}\:\mathrm{is}\:\mathrm{no}\:\mathrm{formula}\:\mathrm{to}\:\mathrm{calculate}\:\mathrm{the} \\ $$ $$\mathrm{integer}\:\mathrm{partitions}\:\mathrm{directly}.\:\mathrm{usually}\:\mathrm{we} \\ $$ $$\mathrm{use}\:\mathrm{generating}\:\mathrm{functions}. \\ $$

Commented byTinkutara last updated on 09/Oct/17

Got it.

$$\mathrm{Got}\:\mathrm{it}. \\ $$

Commented bymrW1 last updated on 09/Oct/17

mr. ajfour had an example in Q21802 for using generating function to find number of integer solutions. it is not really a function but a method.

$$\mathrm{mr}.\:\mathrm{ajfour}\:\mathrm{had}\:\mathrm{an}\:\mathrm{example}\:\mathrm{in}\:\mathrm{Q21802} \\ $$ $$\mathrm{for}\:\mathrm{using}\:\mathrm{generating}\:\mathrm{function}\:\mathrm{to}\:\mathrm{find} \\ $$ $$\mathrm{number}\:\mathrm{of}\:\mathrm{integer}\:\mathrm{solutions}.\:\mathrm{it}\:\mathrm{is}\:\mathrm{not} \\ $$ $$\mathrm{really}\:\mathrm{a}\:\mathrm{function}\:\mathrm{but}\:\mathrm{a}\:\mathrm{method}. \\ $$

Commented bymrW1 last updated on 09/Oct/17

see also Q21800

$$\mathrm{see}\:\mathrm{also}\:\mathrm{Q21800} \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com