MCP рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рдХрдиреЗрдХреНрдЯ рдХрд░реЗрдВ тЖТ

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

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

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

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

Binomial Coefficient C(10, 3)
120
рд╕рдВрдпреЛрдЬрдиреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛
n (рдХреБрд▓ рд╡рд╕реНрддреБрдПрдБ) 10
k (рдЪреБрдиреА рдЧрдИ рд╡рд╕реНрддреБрдПрдБ) 3
рдЗрд╕ рд░реВрдк рдореЗрдВ рдкрдврд╝реЗрдВ "10 choose 3"

рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ?

рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ, рдЬрд┐рд╕реЗ C(n, k) рдпрд╛ "n рдореЗрдВ рд╕реЗ k рдЪреБрдиреЗрдВ" рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдпрд╣ рдмрддрд╛рддрд╛ рд╣реИ рдХрд┐ n рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╡рд╕реНрддреБрдУрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рд╕реЗ k рд╡рд╕реНрддреБрдПрдБ рдХрд┐рддрдиреЗ рддрд░реАрдХреЛрдВ рд╕реЗ рдЪреБрдиреА рдЬрд╛ рд╕рдХрддреА рд╣реИрдВ тАФ рдЬрдм рдЪреБрдирдиреЗ рдХрд╛ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛ред рдпрд╣ рд╕рдВрдпреЛрдЬрд┐рдХреА (combinatorics) рдФрд░ рдкреНрд░рд╛рдпрд┐рдХрддрд╛ (probability) рдХреА рд╕рдмрд╕реЗ рдмреБрдирд┐рдпрд╛рджреА рдорд╛рддреНрд░рд╛рдУрдВ рдореЗрдВ рд╕реЗ рдПрдХ рд╣реИ, рдЬреЛ рдкрд╛рд╕реНрдХрд▓ рддреНрд░рд┐рднреБрдЬ, рджреНрд╡рд┐рдкрдж рдкреНрд░рдореЗрдп рдФрд░ рдЧрд┐рдирддреА рдХреА рдЕрдирдЧрд┐рдирдд рд╕рдорд╕реНрдпрд╛рдУрдВ рдореЗрдВ рдирдЬрд╝рд░ рдЖрддреА рд╣реИред

5 рдмрд┐рдВрджреБрдУрдВ рдХреЗ рд╕рдореВрд╣ рдХреЛ рджрд┐рдЦрд╛рддрд╛ рдЖрд░реЗрдЦ рдЬрд┐рд╕рдореЗрдВ 2 рдЪреБрдиреЗ рдЧрдП рд╣реИрдВ, рдЬреЛ n рдореЗрдВ рд╕реЗ k рдЪреБрдирдиреЗ рдХреЛ рджрд░реНрд╢рд╛рддрд╛ рд╣реИ
рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ n рд╡рд╕реНрддреБрдУрдВ рдХреЗ рд╕рдореВрд╣ рдореЗрдВ рд╕реЗ k рд╡рд╕реНрддреБрдПрдБ рдЪреБрдирдиреЗ рдХреЗ рддрд░реАрдХреЛрдВ рдХреА рдЧрд┐рдирддреА рдХрд░рддрд╛ рд╣реИ, рдХреНрд░рдо рдХреА рдкрд░рд╡рд╛рд╣ рдХрд┐рдП рдмрд┐рдирд╛ред

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

рд╡рд╕реНрддреБрдУрдВ рдХреА рдХреБрд▓ рд╕рдВрдЦреНрдпрд╛ 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!\) рд╣реЛрддреА рд╣реИред

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