Combinations nCr рдЯреЗрдмрд▓ рдХреИрд▓рдХреБрд▓реЗрдЯрд░

Combinations nCr рдЯреЗрдмрд▓ рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рдмрдврд╝ рд░рд╣рд╛ AI Skill PRO

рдЧрдгрдирд╛ рджрд░реНрдЬ рдХрд░реЗрдВ

рд╕реВрддреНрд░ (рдлреЙрд░реНрдореВрд▓рд╛)

(nr)=n!r!(nтИТr)!,тИСr=0n(nr)=2n\binom{\text{n}}{r} = \frac{\text{n}!}{r!\,(\text{n}-r)!}, \qquad \sum_{r=0}^{\text{n}} \binom{\text{n}}{r} = 2^{\text{n}}
рдЙрдкрдпреЛрдЧ рдЖрдБрдХрдбрд╝реЗ

рд╡рд┐рдЬреНрдЮрд╛рдкрди

рдкрд░рд┐рдгрд╛рдо

рд╕рднреА рд╕рдВрдпреЛрдЬрдиреЛрдВ рдХрд╛ рдпреЛрдЧ (2n)
1073741824
рдХреБрд▓ (r = 0 тАж 30; рдкрдВрдХреНрддрд┐рдпрд╛рдБ: 31)
r nCr (рд╕рдВрдпреЛрдЬрдиреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛)
0 1
1 30
2 435
3 4060
4 27405
5 142506
6 593775
7 2035800
8 5852925
9 14307150
10 30045015
11 54627300
12 86493225
13 119759850
14 145422675
15 155117520
16 145422675
17 119759850
18 86493225
19 54627300
20 30045015
21 14307150
22 5852925
23 2035800
24 593775
25 142506
26 27405
27 4060
28 435
29 30
30 1

рдЗрд╕ рдкреЗрдЬ рдкрд░ рддреНрд░реБрдЯрд┐ рдХреА рд░рд┐рдкреЛрд░реНрдЯ рдХрд░реЗрдВ

Combinations nCr рдЯреЗрдмрд▓ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХреНрдпрд╛ рд╣реИ?

рдпрд╣ рдЯреВрд▓ рдмрд╛рдЗрдиреЛрдорд┐рдпрд▓ рдЧреБрдгрд╛рдВрдХ nCr рдХреА рдПрдХ рдкреВрд░реА рдЯреЗрдмрд▓ рдмрдирд╛рддрд╛ рд╣реИ тАФ рдпрд╛рдиреА n рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╡рд╕реНрддреБрдУрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рд╕реЗ r рд╡рд╕реНрддреБрдПрдБ рдЪреБрдирдиреЗ рдХреЗ рдХрд┐рддрдиреЗ рддрд░реАрдХреЗ рд╣реИрдВ, рдЬрдм рдЪреБрдирдиреЗ рдХрд╛ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛ред рдпрд╣ рдЧрдгрдирд╛ r рдХреЗ рд╣рд░ рдорд╛рди рдХреЗ рд▓рд┐рдП рд╣реЛрддреА рд╣реИ, 0 рд╕реЗ рд▓реЗрдХрд░ n рддрдХред рдЖрдк рдмрд╕ n рдХрд╛ рдПрдХ рдорд╛рди рджрд░реНрдЬ рдХрд░реЗрдВ рдФрд░ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ (n+1) рдкрдВрдХреНрддрд┐рдпреЛрдВ рд╡рд╛рд▓реА рдЯреЗрдмрд▓ рдмрдирд╛ рджреЗрддрд╛ рд╣реИ, рд╕рд╛рде рд╣реА рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХрд╛ рдХреБрд▓ рдпреЛрдЧ рднреА рджрд┐рдЦрд╛рддрд╛ рд╣реИ, рдЬреЛ рд╣рдореЗрд╢рд╛ 2 рдХреА рдШрд╛рдд n (\(2^n\)) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред рдпрд╣ arbitrary-precision (рдЕрд╕реАрдорд┐рдд рдкрд░рд┐рд╢реБрджреНрдзрддрд╛) рдЕрдВрдХрдЧрдгрд┐рдд рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рдХреЗ n рдХреЛ 300 рддрдХ рд╕рдВрднрд╛рд▓рддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП 300C150 (рд▓рдЧрднрдЧ 89 рдЕрдВрдХреЛрдВ рд╡рд╛рд▓реА рд╕рдВрдЦреНрдпрд╛) рдЬреИрд╕реЗ рдмреЗрд╣рдж рд╡рд┐рд╢рд╛рд▓ рдЧреБрдгрд╛рдВрдХ рднреА рдмрд┐рд▓реНрдХреБрд▓ рд╕рдЯреАрдХ рдирд┐рдХрд╛рд▓реЗ рдЬрд╛рддреЗ рд╣реИрдВред

рдЗрд╕рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ

рд╡рд╕реНрддреБрдУрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ n рджрд░реНрдЬ рдХрд░реЗрдВ (рдПрдХ рдЧреИрд░-рдЛрдгрд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ, рдЕрдзрд┐рдХрддрдо 300)ред рдпрджрд┐ рдЖрдк рдкрд░рд┐рдгрд╛рдо рдореЗрдВ рдмрд╣реБрдд рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдЫреЛрдЯрд╛ рдХрд░рдХреЗ рджрд┐рдЦрд╛рдирд╛ рдЪрд╛рд╣рддреЗ рд╣реИрдВ, рддреЛ рд╕рд╛рд░реНрдердХ рдЕрдВрдХреЛрдВ рдореЗрдВ рдбрд┐рд╕реНрдкреНрд▓реЗ рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ рдЪреБрдиреЗрдВ; рдЗрд╕рд╕реЗ рдХреЗрд╡рд▓ рдпрд╣ рдмрджрд▓рддрд╛ рд╣реИ рдХрд┐ рдмрдбрд╝реА рд╕рдВрдЦреНрдпрд╛рдПрдБ рдХреИрд╕реЗ рджрд┐рдЦрддреА рд╣реИрдВ тАФ рдореВрд▓ рдЧрдгрд┐рдд рдкрд░ рдХреЛрдИ рдЕрд╕рд░ рдирд╣реАрдВ рдкрдбрд╝рддрд╛ред рдлрд┐рд░ "calculate" рджрдмрд╛рдПрдБ рдФрд░ nCr рдорд╛рдиреЛрдВ рдХреА рдкреВрд░реА рдЯреЗрдмрд▓ рддрдерд╛ рд╕рднреА рдкрдВрдХреНрддрд┐рдпреЛрдВ рдХрд╛ \(2^n\) рдХреБрд▓ рдпреЛрдЧ рджреЗрдЦреЗрдВред

рдлрд╝реЙрд░реНрдореВрд▓рд╛ рд╕рдордЭреЗрдВ

рд╕рдВрдпреЛрдЬрди (combinations) рдХрд╛ рдлрд╝реЙрд░реНрдореВрд▓рд╛ рд╣реИ $$\binom{n}{r} = \frac{n!}{r!\,(n-r)!}$$ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреЛ рдУрд╡рд░рдлрд╝реНрд▓реЛ рд╣реЛрдиреЗ рд╕реЗ рдмрдЪрд╛рдиреЗ рдХреЗ рд▓рд┐рдП рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдПрдХ рдЧреБрдгрд╛рддреНрдордХ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ (multiplicative recurrence) рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИ: \(\binom{n}{0} = 1\) рдФрд░ \(\binom{n}{r} = \binom{n}{r-1} \cdot \frac{n - r + 1}{r}\)ред рд╣рд░ рдЪрд░рдг big-integer рдЧрдгрд┐рдд рд╕реЗ рдмрд┐рд▓реНрдХреБрд▓ рд╕рдЯреАрдХ рд░рд╣рддрд╛ рд╣реИред рд╕рдорд░реВрдкрддрд╛ (symmetry) рдХреЗ рдХрд╛рд░рдг \(\binom{n}{r}\) рдХрд╛ рдорд╛рди \(\binom{n}{n-r}\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИ, рдФрд░ рд╕рднреА r рдХреЗ рд▓рд┐рдП рдХреБрд▓ рдпреЛрдЧ рдкрд╛рд╡рд░ рд╕реЗрдЯ рдХреЗ рдЖрдХрд╛рд░ рдпрд╛рдиреА $$\sum_{r=0}^{n} \binom{n}{r} = 2^{n}$$ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред

рд╡рд┐рдЬреНрдЮрд╛рдкрди
рдкрд╛рд╕реНрдХрд▓ рддреНрд░рд┐рдХреЛрдг рдЬрд┐рд╕рдореЗрдВ рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХреЛрдВ рдХреА рдкрдВрдХреНрддрд┐рдпрд╛рдБ рджрд┐рдЦрд╛рдИ рдЧрдИ рд╣реИрдВ, рд╣рд░ рд╕рдВрдЦреНрдпрд╛ рдКрдкрд░ рдХреА рджреЛ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдЬреЛрдбрд╝рдХрд░ рдмрдирддреА рд╣реИ
рдкрд╛рд╕реНрдХрд▓ рддреНрд░рд┐рдХреЛрдг: рд╣рд░ nCr рдЙрд╕рдХреЗ рдКрдкрд░ рдХреЗ рджреЛ рдорд╛рдиреЛрдВ рдХрд╛ рдпреЛрдЧ рд╣реЛрддрд╛ рд╣реИред

рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг (n = 5)

\(\binom{5}{0} = 1\), \(\binom{5}{1} = 5\), \(\binom{5}{2} = 10\), \(\binom{5}{3} = 10\), \(\binom{5}{4} = 5\), \(\binom{5}{5} = 1\)ред рдкрдВрдХреНрддрд┐ рдХрд╛ рдпреЛрдЧ $$1 + 5 + 10 + 10 + 5 + 1 = 32$$ рд╣реИ, рдЬреЛ \(2^5\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИред рдЬрд╛рдБрдЪ рдХреЗ рддреМрд░ рдкрд░: $$\binom{6}{2} = \frac{6!}{2!\,\cdot 4!} = \frac{720}{2 \cdot 24} = 15$$

рдкрдВрдХреНрддрд┐ n=5 рдХреЗ рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ 1, 5, 10, 10, 5, 1 рдХрд╛ рдмрд╛рд░ рдЪрд╛рд░реНрдЯ рдЬреЛ рд╕рдордорд┐рдд рдШрдВрдЯреА рдЖрдХрд╛рд░ рдмрдирд╛рддрд╛ рд╣реИ
рдкрдВрдХреНрддрд┐ n = 5 (1, 5, 10, 10, 5, 1) рд╕рдордорд┐рдд рд╣реИ рдФрд░ рдЗрд╕рдХрд╛ рдпреЛрдЧ \(2^5 = 32\) рд╣реИред

рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓ (FAQ)

рдЯреЗрдмрд▓ рдореЗрдВ n+1 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдХреНрдпреЛрдВ рд╣реЛрддреА рд╣реИрдВ? рдХреНрдпреЛрдВрдХрд┐ r рдХрд╛ рдорд╛рди 0 рд╕реЗ n рддрдХ (рджреЛрдиреЛрдВ рд╕рд╣рд┐рдд) рдЪрд▓рддрд╛ рд╣реИ, рдЬрд┐рд╕рд╕реЗ рдЪреБрдирдиреЗ рдХреЗ n+1 рдЕрд▓рдЧ-рдЕрд▓рдЧ рдорд╛рди рдмрдирддреЗ рд╣реИрдВред

nC0 рдХрд╛ рдХреНрдпрд╛ рдорддрд▓рдм рд╣реИ? рдХреБрдЫ рднреА рди рдЪреБрдирдирд╛ тАФ рдРрд╕рд╛ рдХрд░рдиреЗ рдХрд╛ рдареАрдХ рдПрдХ рд╣реА рддрд░реАрдХрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\binom{n}{0} = 1\), рдФрд░ рдЗрд╕реА рддрд░рд╣ \(\binom{n}{n} = 1\)ред

50 рд╕рд╛рд░реНрдердХ рдЕрдВрдХреЛрдВ рддрдХ рдХреА рдЕрдиреБрдорддрд┐ рдХреНрдпреЛрдВ? рдмрдбрд╝реЗ рдЧреБрдгрд╛рдВрдХреЛрдВ рдореЗрдВ рдмрд╣реБрдд рд╕рд╛рд░реЗ рдЕрдВрдХ рд╣реЛрддреЗ рд╣реИрдВ; рд╕рд╛рдорд╛рдиреНрдп double precision рд▓рдЧрднрдЧ 15-16 рдЕрдВрдХреЛрдВ рдХреЗ рдмрд╛рдж рд╕рдЯреАрдХрддрд╛ рдЦреЛ рджреЗрддреА рд╣реИ, рдЗрд╕рд▓рд┐рдП рдбрд┐рд╕реНрдкреНрд▓реЗ-рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ рдЪрдпрдирдХрд░реНрддрд╛ рдЖрдкрдХреЛ рдмрд┐рдирд╛ рдХрд╛рдЯ-рдЫрд╛рдБрдЯ рдХреЗ рд╕рдЯреАрдХ рджрд┐рдЦрдиреЗ рд╡рд╛рд▓реЗ рдорд╛рди рджрд┐рдЦрд╛рдиреЗ рджреЗрддрд╛ рд╣реИред

рдЕрдВрддрд┐рдо рдЕрдкрдбреЗрдЯ:

рдЧрдгрд┐рдд рдФрд░ рд╕рд╛рдВрдЦреНрдпрд┐рдХреА рдореЗрдВ рд╕рдмрд╕реЗ рд▓реЛрдХрдкреНрд░рд┐рдп

рдЧрдгрд┐рдд рдФрд░ рд╕рд╛рдВрдЦреНрдпрд┐рдХреА рдХреЗ рд╕рднреА рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рджреЗрдЦреЗрдВ