рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ?
рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ, рдЬрд┐рд╕реЗ C(n, k) рдпрд╛ "n рдореЗрдВ рд╕реЗ k рдЪреБрдиреЗрдВ" рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдпрд╣ рдмрддрд╛рддрд╛ рд╣реИ рдХрд┐ n рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╡рд╕реНрддреБрдУрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рд╕реЗ k рд╡рд╕реНрддреБрдПрдБ рдХрд┐рддрдиреЗ рддрд░реАрдХреЛрдВ рд╕реЗ рдЪреБрдиреА рдЬрд╛ рд╕рдХрддреА рд╣реИрдВ тАФ рдЬрдм рдЪреБрдирдиреЗ рдХрд╛ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛ред рдпрд╣ рд╕рдВрдпреЛрдЬрд┐рдХреА (combinatorics) рдФрд░ рдкреНрд░рд╛рдпрд┐рдХрддрд╛ (probability) рдХреА рд╕рдмрд╕реЗ рдмреБрдирд┐рдпрд╛рджреА рдорд╛рддреНрд░рд╛рдУрдВ рдореЗрдВ рд╕реЗ рдПрдХ рд╣реИ, рдЬреЛ рдкрд╛рд╕реНрдХрд▓ рддреНрд░рд┐рднреБрдЬ, рджреНрд╡рд┐рдкрдж рдкреНрд░рдореЗрдп рдФрд░ рдЧрд┐рдирддреА рдХреА рдЕрдирдЧрд┐рдирдд рд╕рдорд╕реНрдпрд╛рдУрдВ рдореЗрдВ рдирдЬрд╝рд░ рдЖрддреА рд╣реИред
рдЗрд╕ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
рд╡рд╕реНрддреБрдУрдВ рдХреА рдХреБрд▓ рд╕рдВрдЦреНрдпрд╛ n рдФрд░ рдЬрд┐рддрдиреА рд╡рд╕реНрддреБрдПрдБ рдЖрдк рдЪреБрдирдирд╛ рдЪрд╛рд╣рддреЗ рд╣реИрдВ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ k рджрд░реНрдЬ рдХрд░реЗрдВред рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рд╕рдВрдпреЛрдЬрдиреЛрдВ рдХреА рд╕рдЯреАрдХ рд╕рдВрдЦреНрдпрд╛ рд▓реМрдЯрд╛ рджреЗрдЧрд╛ред рдЕрдЧрд░ k рдХрд╛ рдорд╛рди n рд╕реЗ рдмрдбрд╝рд╛ рд╣реИ, рддреЛ рдкрд░рд┐рдгрд╛рдо 0 рдЖрдПрдЧрд╛, рдХреНрдпреЛрдВрдХрд┐ рдореМрдЬреВрдж рд╡рд╕реНрддреБрдУрдВ рд╕реЗ рдЬрд╝реНрдпрд╛рджрд╛ рд╡рд╕реНрддреБрдПрдБ рдЪреБрдирдирд╛ рд╕рдВрднрд╡ рдирд╣реАрдВ рд╣реИред
рд╕реВрддреНрд░ рдХреА рд╕рдордЭ
рдЗрд╕рдХреА рдкрд╛рд░рдВрдкрд░рд┐рдХ рдкрд░рд┐рднрд╛рд╖рд╛ рдЗрд╕ рдкреНрд░рдХрд╛рд░ рд╣реИ:
$$\binom{n}{k} = \frac{n!}{k!\,\left(n - k\right)!}$$
рдЪреВрдБрдХрд┐ рдХреНрд░рдордЧреБрдгрд┐рдд (factorial) рдмрд╣реБрдд рддреЗрдЬрд╝реА рд╕реЗ рдмрдврд╝рддреЗ рд╣реИрдВ, рдЗрд╕рд▓рд┐рдП рдпрд╣ рдЯреВрд▓ рдЗрд╕рдХреЗ рд╕рдорддреБрд▓реНрдп рдЧреБрдгрд╛рддреНрдордХ рд░реВрдк рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИ тАФ рдпрд╣ (nтИТk+i)/i рдХреЛ i = 1тАжmin(k, nтИТk) рдХреЗ рд▓рд┐рдП рдЧреБрдгрд╛ рдХрд░рддрд╛ рд╣реИред рдЗрд╕рд╕реЗ рдмреАрдЪ рдХреЗ рдорд╛рди рдЫреЛрдЯреЗ рдмрдиреЗ рд░рд╣рддреЗ рд╣реИрдВ, рдУрд╡рд░рдлрд╝реНрд▓реЛ рдХреА рд╕рдорд╕реНрдпрд╛ рдирд╣реАрдВ рдЖрддреА рдФрд░ рдЙрддреНрддрд░ рд╡рд╣реА рдкреВрд░реНрдгрд╛рдВрдХ рдкреНрд░рд╛рдкреНрдд рд╣реЛрддрд╛ рд╣реИред
рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг
5 рддрд╛рд╢реЛрдВ рдХреЗ рдвреЗрд░ рдореЗрдВ рд╕реЗ 2-рддрд╛рд╢ рдХреЗ рдХрд┐рддрдиреЗ рд╣рд╛рде рдмрди рд╕рдХрддреЗ рд╣реИрдВ? $$\binom{5}{2} = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = \frac{120}{12} = 10$$ рдирд┐рдХрд╛рд▓реЗрдВред рдпрд╛рдиреА рдХреБрд▓ 10 рд╕рдВрднрд╛рд╡рд┐рдд рдЬреЛрдбрд╝реЗ рдмрдирддреЗ рд╣реИрдВред
рдкрд╛рд╕реНрдХрд▓ рдХрд╛ рддреНрд░рд┐рднреБрдЬ рд╕рдВрджрд░реНрдн (рдЫреЛрдЯреЗ n рдХреЗ рд▓рд┐рдП C(n,k))
рддрд╛рд▓рд┐рдХрд╛ рдореЗрдВ рдкреНрд░рддреНрдпреЗрдХ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐ рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ \(\binom{n}{k}\) рд╣реИ, рд╡реНрдпрд╡рд╕реНрдерд┐рдд рддрд╛рдХрд┐ рдкреНрд░рддреНрдпреЗрдХ рдкрдВрдХреНрддрд┐ \(n\) рдХреЗ рд▓рд┐рдП \(k = 0, 1, \dots, n\) рдХреЗ рдорд╛рди рджрд┐рдП рдЧрдП рд╣реЛрдВред рдпрд╣ рдкрд╛рд╕реНрдХрд▓ рдХрд╛ рддреНрд░рд┐рднреБрдЬ рдмрдирд╛рддрд╛ рд╣реИ, рдЬрд╣рд╛рдБ рдкреНрд░рддреНрдпреЗрдХ рдЖрдВрддрд░рд┐рдХ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐ рдЗрд╕рдХреЗ рдКрдкрд░ рд╡рд┐рдХрд░реНрдг рдореЗрдВ рджреЛ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐рдпреЛрдВ рдХреЗ рдпреЛрдЧ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИ: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)ред рдкреНрд░рддреНрдпреЗрдХ рдкрдВрдХреНрддрд┐ рдореЗрдВ рд╕рдорд░реВрдкрддрд╛ рдкрд░ рдзреНрдпрд╛рди рджреЗрдВ, рдХреНрдпреЛрдВрдХрд┐ \(\binom{n}{k} = \binom{n}{n-k}\)ред
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||||||
| 1 | 1 | 1 | |||||||||
| 2 | 1 | 2 | 1 | ||||||||
| 3 | 1 | 3 | 3 | 1 | |||||||
| 4 | 1 | 4 | 6 | 4 | 1 | ||||||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||
| 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | ||
| 9 | 1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | |
| 10 | 1 | 10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, \(\binom{10}{3} = \) 120, рдкрдВрдХреНрддрд┐ 10, рд╕реНрддрдВрдн \(k=3\) рдкрд░ рдкрд╛рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдкрдВрдХреНрддрд┐ \(n\) рдореЗрдВ рдкреНрд░рддреНрдпреЗрдХ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐ рдХрд╛ рдпреЛрдЧ \(2^n\) рдХреЗ рдмрд░рд╛рдмрд░ рд╣реИ (рдЬреИрд╕реЗ рдкрдВрдХреНрддрд┐ 4: \(1+4+6+4+1 = 16 = 2^4\))ред
рдЕрдзрд┐рдХ рд╣рд▓ рдХрд┐рдП рдЧрдП рдЙрджрд╛рд╣рд░рдг
рдирд┐рдореНрдирд▓рд┐рдЦрд┐рдд рдЙрджрд╛рд╣рд░рдг рд╕реВрддреНрд░ \(\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}\) рдХреЛ рд▓рд╛рдЧреВ рдХрд░рддреЗ рд╣реИрдВ, рдЧреБрдгрдирд╛рддреНрдордХ рд╢реЙрд░реНрдЯрдХрдЯ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддреЗ рд╣реБрдП \(\binom{n}{k} = \dfrac{n(n-1)\cdots(n-k+1)}{k!}\) рддрд╛рдХрд┐ рд╡рд┐рд╢рд╛рд▓ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХрд┐рд╕реА рднреА рдмрдбрд╝реА рдЧреБрдгрд╛ рд╕реЗ рдкрд╣рд▓реЗ рд░рджреНрдж рд╣реЛ рдЬрд╛рдПрдБред
рдЙрджрд╛рд╣рд░рдг 1: \(\binom{10}{3}\) тАФ 10 рд╕реЗ 3 рдЪреБрдирдирд╛
\(3!\) рдкрд░ \(10!\) рдХреА рдХреЗрд╡рд▓ рд╢реАрд░реНрд╖ 3 рдЧрд┐рд░рддреА рд╣реБрдИ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рд░рдЦреЗрдВ:
$$\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120$$рддреЛ 10 рдореЗрдВ рд╕реЗ 3 рд╡рд╕реНрддреБрдПрдВ рдЪреБрдирдиреЗ рдХреЗ 120 рддрд░реАрдХреЗ рд╣реИрдВ рдЬрдм рдХреНрд░рдо рдорд╣рддреНрд╡рдкреВрд░реНрдг рдирд╣реАрдВ рд╣реИред
рдЙрджрд╛рд╣рд░рдг 2: \(\binom{6}{6}\) тАФ рд╕рднреА рдХреЛ рдЪреБрдирдирд╛
рдЙрдкрд▓рдмреНрдз рдкреНрд░рддреНрдпреЗрдХ рд╡рд╕реНрддреБ рдХреЛ рдЪреБрдирдирд╛ рдмрд┐рд▓реНрдХреБрд▓ рдПрдХ рддрд░реАрдХреЗ рд╕реЗ рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред \(k = n\) рдХреЗ рд╕рд╛рде, \((n-k)!\) рдкрдж \(0! = 1\) рд╣реЛ рдЬрд╛рддрд╛ рд╣реИ:
$$\binom{6}{6} = \frac{6!}{6!\,(6-6)!} = \frac{720}{720 \cdot 1} = 1$$рдпрд╣ рдкрд╣рдЪрд╛рди рдХреА рдкреБрд╖реНрдЯрд┐ рдХрд░рддрд╛ рд╣реИ \(\binom{n}{n} = \binom{n}{0} = \) 1ред
рдЙрджрд╛рд╣рд░рдг 3: \(\binom{49}{6}\) тАФ рдПрдХ 6-рдореЗрдВ-49 рд▓реЙрдЯрд░реА
49 рдХреА рдкреВрд▓ рд╕реЗ 6 рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рд╡рд┐рд╢рд┐рд╖реНрдЯ рдЕрдХреНрд░рдорд┐рдХ рдЯрд┐рдХрдЯреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рдЫрдГ рд╕рдмрд╕реЗ рдмрдбрд╝реА рдЧрд┐рд░рддреА рд╣реБрдИ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреЗ рд╕рд╛рде рдЧреБрдгрдирд╛рддреНрдордХ рд╢реЙрд░реНрдЯрдХрдЯ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддреА рд╣реИ:
$$\binom{49}{6} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!}$$рдЕрдВрд╢ \(49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 = 10{,}068{,}347{,}520\) рд╣реИ, рдФрд░ рд╣рд░ \(6! = 720\) рд╣реИ:
$$\binom{49}{6} = \frac{10{,}068{,}347{,}520}{720} = 13{,}983{,}816$$рддреЛ рдПрдХ рдПрдХрд▓ рдЯрд┐рдХрдЯ рдХреЗ рд╕рднреА рдЫрдГ рд╕рдВрдЦреНрдпрд╛рдУрдВ рд╕реЗ рдореЗрд▓ рдЦрд╛рдиреЗ рдХрд╛ 1-рдореЗрдВ-13,983,816 рд╕рдВрднрд╛рд╡рдирд╛ рд╣реИред рдпрджрд┐ рдЖрдк рдЗрд╕рдХреЗ рдмрдЬрд╛рдп рдЕрдХреНрд░рдорд┐рдХ рд░реВрдк рд╕реЗ рдЦреАрдВрдЪрдирд╛ рдЪрд╛рд╣рддреЗ рд╣реИрдВ, рддреЛ рдЖрдк рдХреНрд░рдордЪрдп \(P(49,6) = \binom{49}{6}\cdot 6!\) рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░реЗрдВрдЧреЗ тАФ рд▓реЗрдХрд┐рди рдПрдХ рд╡рд┐рд╢рд┐рд╖реНрдЯ рд▓реЙрдЯрд░реА рдХреЗ рд▓рд┐рдП рдХреЗрд╡рд▓ рд╕рдВрдпреЛрдЬрди рдорд╣рддреНрд╡рдкреВрд░реНрдг рд╣реИред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓
\(C(n, 0)\) рдХрд╛ рдорд╛рди рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ? рд╣рдореЗрд╢рд╛ 1 тАФ рдХреБрдЫ рднреА рди рдЪреБрдирдиреЗ рдХрд╛ рдареАрдХ рдПрдХ рд╣реА рддрд░реАрдХрд╛ рд╣реЛрддрд╛ рд╣реИред
рдХреНрдпрд╛ \(C(n, k)\) рдФрд░ \(C(n, n-k)\) рдмрд░рд╛рдмрд░ рд╣реЛрддреЗ рд╣реИрдВ? рд╣рд╛рдБ, рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ рд╕рдордорд┐рдд рд╣реЛрддрд╛ рд╣реИ: k рд╡рд╕реНрддреБрдПрдБ рд░рдЦрдиреЗ рдХреЗ рд▓рд┐рдП рдЪреБрдирдирд╛ рдФрд░ nтИТk рд╡рд╕реНрддреБрдПрдБ рдЫреЛрдбрд╝рдиреЗ рдХреЗ рд▓рд┐рдП рдЪреБрдирдирд╛ рдПрдХ рд╣реА рдмрд╛рдд рд╣реИред
рд╕рдВрдпреЛрдЬрди (combinations) рдФрд░ рдХреНрд░рдордЪрдп (permutations) рдореЗрдВ рдХреНрдпрд╛ рдлрд░реНрдХ рд╣реИ? рд╕рдВрдпреЛрдЬрди рдореЗрдВ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛, рдЬрдмрдХрд┐ рдХреНрд░рдордЪрдп рдореЗрдВ рдХреНрд░рдо рдЧрд┐рдирд╛ рдЬрд╛рддрд╛ рд╣реИред рдХреНрд░рдордЪрдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ \(C(n, k) \times k!\) рд╣реЛрддреА рд╣реИред