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}$$ рдХреЗ рдмрд░рд╛рдмрд░ рд╣реЛрддрд╛ рд╣реИред
рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг (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$$
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓ (FAQ)
рдЯреЗрдмрд▓ рдореЗрдВ n+1 рдкрдВрдХреНрддрд┐рдпрд╛рдБ рдХреНрдпреЛрдВ рд╣реЛрддреА рд╣реИрдВ? рдХреНрдпреЛрдВрдХрд┐ r рдХрд╛ рдорд╛рди 0 рд╕реЗ n рддрдХ (рджреЛрдиреЛрдВ рд╕рд╣рд┐рдд) рдЪрд▓рддрд╛ рд╣реИ, рдЬрд┐рд╕рд╕реЗ рдЪреБрдирдиреЗ рдХреЗ n+1 рдЕрд▓рдЧ-рдЕрд▓рдЧ рдорд╛рди рдмрдирддреЗ рд╣реИрдВред
nC0 рдХрд╛ рдХреНрдпрд╛ рдорддрд▓рдм рд╣реИ? рдХреБрдЫ рднреА рди рдЪреБрдирдирд╛ тАФ рдРрд╕рд╛ рдХрд░рдиреЗ рдХрд╛ рдареАрдХ рдПрдХ рд╣реА рддрд░реАрдХрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП \(\binom{n}{0} = 1\), рдФрд░ рдЗрд╕реА рддрд░рд╣ \(\binom{n}{n} = 1\)ред
50 рд╕рд╛рд░реНрдердХ рдЕрдВрдХреЛрдВ рддрдХ рдХреА рдЕрдиреБрдорддрд┐ рдХреНрдпреЛрдВ? рдмрдбрд╝реЗ рдЧреБрдгрд╛рдВрдХреЛрдВ рдореЗрдВ рдмрд╣реБрдд рд╕рд╛рд░реЗ рдЕрдВрдХ рд╣реЛрддреЗ рд╣реИрдВ; рд╕рд╛рдорд╛рдиреНрдп double precision рд▓рдЧрднрдЧ 15-16 рдЕрдВрдХреЛрдВ рдХреЗ рдмрд╛рдж рд╕рдЯреАрдХрддрд╛ рдЦреЛ рджреЗрддреА рд╣реИ, рдЗрд╕рд▓рд┐рдП рдбрд┐рд╕реНрдкреНрд▓реЗ-рдкрд░рд┐рд╢реБрджреНрдзрддрд╛ рдЪрдпрдирдХрд░реНрддрд╛ рдЖрдкрдХреЛ рдмрд┐рдирд╛ рдХрд╛рдЯ-рдЫрд╛рдБрдЯ рдХреЗ рд╕рдЯреАрдХ рджрд┐рдЦрдиреЗ рд╡рд╛рд▓реЗ рдорд╛рди рджрд┐рдЦрд╛рдиреЗ рджреЗрддрд╛ рд╣реИред