рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛ S(n,k) рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛ S(n,k) рдХреИрд▓рдХреБрд▓реЗрдЯрд░

рд▓реЛрдХрдкреНрд░рд┐рдп AI Skill PRO

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

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

S(n,k)=1k!тИСj=0k(тИТ1)j(kj)(kтИТj)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
рдЙрдкрдпреЛрдЧ рдЖрдБрдХрдбрд╝реЗ

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

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

рджреВрд╕рд░реА рддрд░рд╣ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛ S(5, 2)
15
рд▓реЗрдмрд▓ рд╡рд╛рд▓реЗ рддрддреНрд╡реЛрдВ рдХреЛ рдЧреИрд░-рд░рд┐рдХреНрдд рдЙрдкрд╕рдореБрдЪреНрдЪрдпреЛрдВ рдореЗрдВ рдмрд╛рдБрдЯрдиреЗ рдХреЗ рддрд░реАрдХреЗ (рддрддреНрд╡: 5 ┬╖ рдЙрдкрд╕рдореБрдЪреНрдЪрдп: 2)
n (рд╕рдореБрдЪреНрдЪрдп рдХрд╛ рдЖрдХрд╛рд░) 5
k (рдЙрдкрд╕рдореБрдЪреНрдЪрдп) 2
рд╕рдВрдХреЗрддрди S(n, k)

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

рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛ рдХреНрдпрд╛ рд╣реИ?

рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛, рдЬрд┐рд╕реЗ \(S(n,k)\) рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, рдпрд╣ рдЧрд┐рдирддреА рд╣реИ рдХрд┐ n рдЕрд▓рдЧ-рдЕрд▓рдЧ (рд▓реЗрдмрд▓ рд╡рд╛рд▓реЗ) рддрддреНрд╡реЛрдВ рдХреЗ рдПрдХ рд╕рдореБрдЪреНрдЪрдп рдХреЛ рдареАрдХ k рдЧреИрд░-рдЦрд╛рд▓реА, рдЕрд▓реЗрдмрд▓ рдЙрдкрд╕рдореБрдЪреНрдЪрдпреЛрдВ рдореЗрдВ рдХрд┐рддрдиреЗ рддрд░реАрдХреЛрдВ рд╕реЗ рдмрд╛рдБрдЯрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред рдпрд╣ рд╕рдВрдпреЛрдЬрдирд╢рд╛рд╕реНрддреНрд░ (combinatorics) рдХреА рдПрдХ рдмреБрдирд┐рдпрд╛рджреА рд░рд╛рд╢рд┐ рд╣реИ рдФрд░ рд╕рдореБрдЪреНрдЪрдп рд╡рд┐рднрд╛рдЬрди, рдЖрдЪреНрдЫрд╛рджрдХ рдлрд▓рди (surjections) рддрдерд╛ рдмреЗрд▓ рд╕рдВрдЦреНрдпрд╛рдУрдВ рд╕реЗ рдЬреБрдбрд╝реА рд╕рдорд╕реНрдпрд╛рдУрдВ рдореЗрдВ рд╕рд╛рдордиреЗ рдЖрддреА рд╣реИред рдпрд╣ рд╢реБрджреНрдз рдЧрдгрд┐рдд рдХрд╛ рдЙрдкрдХрд░рдг рд╣реИ, рдЬреЛ рд╣рд░ рдЬрдЧрд╣ рдПрдХ рд╣реА рддрд░рд╣ рдХрд╛рдо рдХрд░рддрд╛ рд╣реИред

рджреЛ рдмрд┐рдирд╛ рдирд╛рдо рд╡рд╛рд▓реЗ рдбрд┐рдмреНрдмреЛрдВ рдореЗрдВ рдмрдБрдЯреА рдЪрд╛рд░ рдирд╛рдорд╛рдВрдХрд┐рдд рдЧреЗрдВрджреЗрдВ, рдЬреЛ рдПрдХ рд╕рдореБрдЪреНрдЪрдп рд╡рд┐рднрд╛рдЬрди рджрд░реНрд╢рд╛рддреА рд╣реИрдВ
\(S(n,k)\) рдпрд╣ рдЧрд┐рдирддрд╛ рд╣реИ рдХрд┐ n рдирд╛рдорд╛рдВрдХрд┐рдд рд╡рд╕реНрддреБрдУрдВ рдХреЛ k рдЧреИрд░-рдЦрд╛рд▓реА рдмрд┐рдирд╛ рдирд╛рдо рд╡рд╛рд▓реЗ рд╕рдореВрд╣реЛрдВ рдореЗрдВ рдХрд┐рддрдиреЗ рддрд░реАрдХреЛрдВ рд╕реЗ рдмрд╛рдБрдЯрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред

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

рд╕рдореБрдЪреНрдЪрдп рдХрд╛ рдЖрдХрд╛рд░ \(n\) рдФрд░ рдЙрдкрд╕рдореБрдЪреНрдЪрдпреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ \(k\) рджрд░реНрдЬ рдХрд░реЗрдВред рджреЛрдиреЛрдВ рдЛрдгреЗрддрд░ рдкреВрд░реНрдгрд╛рдВрдХ (non-negative integers) рд╣реЛрдиреЗ рдЪрд╛рд╣рд┐рдПред \(S(n,k)\) тАФ рдпрд╛рдиреА рд╡рд┐рднрд╛рдЬрдиреЛрдВ рдХреА рд╕рдЯреАрдХ рдЧрд┐рдирддреА тАФ рдкрд╛рдиреЗ рдХреЗ рд▓рд┐рдП calculate рджрдмрд╛рдПрдБред рдпрджрд┐ k, n рд╕реЗ рдмрдбрд╝рд╛ рд╣реИ рддреЛ рдкрд░рд┐рдгрд╛рдо 0 рд╣реЛрдЧрд╛, рдХреНрдпреЛрдВрдХрд┐ рдЬрд┐рддрдиреЗ рддрддреНрд╡ рд╣реИрдВ рдЙрд╕рд╕реЗ рдЬрд╝реНрдпрд╛рджрд╛ рдЧреИрд░-рдЦрд╛рд▓реА рдЙрдкрд╕рдореБрдЪреНрдЪрдп рднрд░рдирд╛ рд╕рдВрднрд╡ рдирд╣реАрдВ рд╣реИред

рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛

рд╕реНрдкрд╖реНрдЯ рд░реВрдк рдЗрд╕ рдкреНрд░рдХрд╛рд░ рд╣реИ:

$$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$

рдЬрд╣рд╛рдБ \(C(k,j)\) рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ (binomial coefficient) рд╣реИред рдЗрд╕рдХрд╛ рдПрдХ рд╕рдорддреБрд▓реНрдп рдФрд░ рд╕рдВрдЦреНрдпрд╛рддреНрдордХ рд░реВрдк рд╕реЗ рдЕрдзрд┐рдХ рд╕реБрд░рдХреНрд╖рд┐рдд рддрд░реАрдХрд╛ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ рд╣реИ:

$$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$

рдЬрд┐рд╕рдХреЗ рдЖрдзрд╛рд░ рдорд╛рди рд╣реИрдВ \(S(0,0)=1\), \(n>0\) рдХреЗ рд▓рд┐рдП \(S(n,0)=0\), рдФрд░ \(k>0\) рдХреЗ рд▓рд┐рдП \(S(0,k)=0\)ред рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдлрд╝реНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рддреНрд░реБрдЯрд┐рдпреЛрдВ рд╕реЗ рдмрдЪрдиреЗ рдХреЗ рд▓рд┐рдП рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддрд╛ рд╣реИред рдХреБрдЫ рдЙрдкрдпреЛрдЧреА рд╡рд┐рд╢реЗрд╖ рд╕реНрдерд┐рддрд┐рдпрд╛рдБ: \(S(n,1)=1\), \(S(n,n)=1\), рдФрд░ \(S(n,2)=2^{n-1}-1\)ред

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

рд╣рд▓ рдХрд┐рдпрд╛ рдЧрдпрд╛ рдЙрджрд╛рд╣рд░рдг

\(n=5\) рдФрд░ \(k=2\) рдХреЗ рд▓рд┐рдП: рд╡рд┐рд╢реЗрд╖ рд╕реВрддреНрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХрд░рддреЗ рд╣реБрдП

$$S(5,2)=2^{5-1}-1=16-1=15$$

рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ рднреА рдЗрд╕рдХреА рдкреБрд╖реНрдЯрд┐ рдХрд░рддрд╛ рд╣реИ:

$$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$

рдпрд╛рдиреА 5 рддрддреНрд╡реЛрдВ рд╡рд╛рд▓реЗ рд╕рдореБрдЪреНрдЪрдп рдХреЛ рджреЛ рдЧреИрд░-рдЦрд╛рд▓реА рд╕рдореВрд╣реЛрдВ рдореЗрдВ рдмрд╛рдБрдЯрдиреЗ рдХреЗ 15 рддрд░реАрдХреЗ рд╣реИрдВред

рдЫреЛрдЯреЗ рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рддреНрд░рд┐рднреБрдЬрд╛рдХрд╛рд░ рдЧреНрд░рд┐рдб, рдкрд╛рд╕реНрдХрд▓ рддреНрд░рд┐рднреБрдЬ рдХреА рддрд░рд╣ рд╡реНрдпрд╡рд╕реНрдерд┐рдд
\(S(n,k)\) рдорд╛рдиреЛрдВ рдХрд╛ рдПрдХ рддреНрд░рд┐рднреБрдЬ, рд╣рд░ рдорд╛рди рдЕрдкрдиреЗ рдКрдкрд░ рдХреЗ рджреЛ рдорд╛рдиреЛрдВ рд╕реЗ рдмрдирд╛ рд╣реИред

рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛рдУрдВ S(n,k) рдХреА рддрд╛рд▓рд┐рдХрд╛, n = 0 рд╕реЗ 10 рддрдХ

рдкреНрд░рддреНрдпреЗрдХ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐ рдЙрди рддрд░реАрдХреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдЬрд┐рдирд╕реЗ n рдЕрдВрдХрд┐рдд (labeled) рддрддреНрд╡реЛрдВ рдХреЗ рд╕рдореБрдЪреНрдЪрдп рдХреЛ рдареАрдХ k рдЧреИрд░-рд░рд┐рдХреНрдд, рдмрд┐рдирд╛ рдЕрдВрдХрд┐рдд (unlabeled) рдЦрдВрдбреЛрдВ рдореЗрдВ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред рддрд╛рд▓рд┐рдХрд╛ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\) рд╕реЗ рдмрдирд╛рдИ рдЧрдИ рд╣реИ, рдЬрд┐рд╕рдореЗрдВ \(S(0,0)=1\) рдФрд░ \(n\ge 1\) рдХреЗ рд▓рд┐рдП \(S(n,0)=S(0,n)=0\) рд╣реИред рд░рд┐рдХреНрдд рдХреЛрд╖реНрда \(k>n\) рд╡рд╛рд▓реЗ рд╣реИрдВ, рдЬрд╣рд╛рдБ S(n,k)=0 рд╣реИред рдЕрдВрддрд┐рдо рд╕реНрддрдВрдн рдкрдВрдХреНрддрд┐ рдпреЛрдЧ рд╣реИ, рдЬреЛ рдмреЗрд▓ рд╕рдВрдЦреНрдпрд╛ B(n) рд╣реИред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, S(10,4) = 34105.

n \ k 0 1 2 3 4 5 6 7 8 9 10 рдкрдВрдХреНрддрд┐ рдпреЛрдЧ B(n)
0 1 1
1 0 1 1
2 0 1 1 2
3 0 1 3 1 5
4 0 1 7 6 1 15
5 0 1 15 25 10 1 52
6 0 1 31 90 65 15 1 203
7 0 1 63 301 350 140 21 1 877
8 0 1 127 966 1701 1050 266 28 1 4140
9 0 1 255 3025 7770 6951 2646 462 36 1 21147
10 0 1 511 9330 34105 42525 22827 5880 750 45 1 115975

рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реЗ рдПрдХ рдкреНрд░рд╡рд┐рд╖реНрдЯрд┐ рдХреА рдЬрд╛рдБрдЪ: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\)ред рд╣рдореЗрд╢рд╛ \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) рдФрд░ \(S(n,n)=1\) рд╣реЛрддрд╛ рд╣реИред

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

рдореБрдЦреНрдп рд╢рдмреНрдж рдФрд░ рд╕рдВрдХреЗрддрди

рд╕рдореБрдЪреНрдЪрдп рд╡рд┐рднрд╛рдЬрди
рдХрд┐рд╕реА рд╕рдореБрдЪреНрдЪрдп рдХреЛ рдЧреИрд░-рд░рд┐рдХреНрдд, рдкрд░рд╕реНрдкрд░ рдЕрд╕рдВрдпреБрдХреНрдд рдЙрдкрд╕рдореБрдЪреНрдЪрдпреЛрдВ (рдЦрдВрдбреЛрдВ) рдореЗрдВ рдмрд╛рдБрдЯрдиреЗ рдХрд╛ рддрд░реАрдХрд╛, рдЬрд┐рдирдХрд╛ рд╕рдВрдШ рдкреВрд░рд╛ рд╕рдореБрдЪреНрдЪрдп рд╣реЛред рдЦрдВрдбреЛрдВ рдХрд╛ рдХреНрд░рдо рдФрд░ рдХрд┐рд╕реА рдЦрдВрдб рдХреЗ рднреАрддрд░ рддрддреНрд╡реЛрдВ рдХрд╛ рдХреНрд░рдо рдорд╛рдпрдиреЗ рдирд╣реАрдВ рд░рдЦрддрд╛ред
рдЕрдВрдХрд┐рдд рдмрдирд╛рдо рдЕрдирдВрдХрд┐рдд
n рддрддреНрд╡ рдЕрдВрдХрд┐рдд (рдЕрд▓рдЧ-рдЕрд▓рдЧ рдкрд╣рдЪрд╛рдиреЗ рдЬрд╛ рд╕рдХрдиреЗ рд╡рд╛рд▓реЗ, рдЬреИрд╕реЗ 1, 2, тАж, n) рд╣реИрдВред k рдЙрдкрд╕рдореБрдЪреНрдЪрдп рдЕрдирдВрдХрд┐рдд рд╣реИрдВ: рджреЛ рдЦрдВрдбреЛрдВ рдХреА рдЕрджрд▓рд╛-рдмрджрд▓реА рд╕реЗ рд╡рд╣реА рд╡рд┐рднрд╛рдЬрди рдорд┐рд▓рддрд╛ рд╣реИред рдпрджрд┐ рдЦрдВрдб рдЕрдВрдХрд┐рдд рд╣реЛрддреЗ, рддреЛ рдЧрд┐рдирддреА k!┬╖S(n,k) рд╣реЛрддреАред
рдЧреИрд░-рд░рд┐рдХреНрдд рдЦрдВрдб
k рдореЗрдВ рд╕реЗ рдкреНрд░рддреНрдпреЗрдХ рдЙрдкрд╕рдореБрдЪреНрдЪрдп рдореЗрдВ рдХрдо рд╕реЗ рдХрдо рдПрдХ рддрддреНрд╡ рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред рдЗрд╕реА рдХрд╛рд░рдг n тЙе 1 рдХреЗ рд▓рд┐рдП S(n,0)=0 рд╣реИ рдФрд░ рдЬрдм k > n рд╣реЛ рддреЛ S(n,k)=0 рд╣реИред
рд╕рдВрдХреЗрддрди S(n,k)
рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛, рдЬрд┐рд╕реЗ \(\left\{ n \atop k \right\}\) рднреА рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИред рдЗрд╕рдХреА рдЧрдгрдирд╛ \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\) рд╕реЗ рд╣реЛрддреА рд╣реИред
рдмреЗрд▓ рд╕рдВрдЦреНрдпрд╛ B(n)
n-рддрддреНрд╡ рд╕рдореБрдЪреНрдЪрдп рдХреЗ рдХрд┐рд╕реА рднреА рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдЦрдВрдбреЛрдВ рдореЗрдВ рдХреБрд▓ рд╡рд┐рднрд╛рдЬрдиреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛: \(B(n)=\sum_{k=0}^{n}S(n,k)\)ред рдкрд╣рд▓реЗ рдорд╛рди 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 рд╣реИрдВред
рджреНрд╡рд┐рдкрдж рдЧреБрдгрд╛рдВрдХ
\(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), k рдореЗрдВ рд╕реЗ j рд╡рд╕реНрддреБрдПрдБ рдЪреБрдирдиреЗ рдХреЗ рддрд░реАрдХреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ред рдпрд╣ рдКрдкрд░ рдХреЗ рд╕рдорд╛рд╡реЗрд╢рдитАУрдЕрдкрд╡рд░реНрдЬрди рд╕реВрддреНрд░ рдореЗрдВ рдЖрддрд╛ рд╣реИред
рдЖрдЪреНрдЫрд╛рджрдХ рдлрд▓рди (Surjection)
n-рд╕рдореБрдЪреНрдЪрдп рд╕реЗ k-рд╕рдореБрдЪреНрдЪрдп рдкрд░ рдПрдХ рдлрд▓рди, рдЬрд┐рд╕рдореЗрдВ k-рд╕рдореБрдЪреНрдЪрдп рдХрд╛ рдкреНрд░рддреНрдпреЗрдХ рддрддреНрд╡ рдХрдо рд╕реЗ рдХрдо рдПрдХ рдмрд╛рд░ рдкреНрд░рднрд╛рд╡рд┐рдд рд╣реЛред рдРрд╕реЗ рдлрд▓рдиреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ \(k!\cdot S(n,k)\) рд╣реИ: рдкреНрд░рд╛рдВрдд рдХреЛ k рдЦрдВрдбреЛрдВ рдореЗрдВ рдмрд╛рдБрдЯреЛ, рдлрд┐рд░ рдЦрдВрдбреЛрдВ рдХреЛ k рд▓рдХреНрд╖реНрдпреЛрдВ рдХреЛ k! рддрд░реАрдХреЛрдВ рд╕реЗ рд╕реМрдВрдкреЛред

рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдмрдирд╛рдо рдкрд╣рд▓реЗ рдкреНрд░рдХрд╛рд░ред рджреВрд╕рд░реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдХрд┐рд╕реА рд╕рдореБрдЪреНрдЪрдп рдХреЗ k рдЦрдВрдбреЛрдВ рдореЗрдВ рд╡рд┐рднрд╛рдЬрдиреЛрдВ рдХреА рдЧрд┐рдирддреА рдХрд░рддреА рд╣реИрдВред рдкрд╣рд▓реЗ рдкреНрд░рдХрд╛рд░ рдХреА рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдВрдЦреНрдпрд╛рдПрдБ, рдЬреЛ \(c(n,k)\) рдпрд╛ \(\left[ n \atop k \right]\) (рдЕрдЪрд┐рд╣реНрдирд┐рдд) рд▓рд┐рдЦреА рдЬрд╛рддреА рд╣реИрдВ, n рддрддреНрд╡реЛрдВ рдХреЗ рдареАрдХ k рдЪрдХреНрд░реЛрдВ рд╡рд╛рд▓реЗ рдХреНрд░рдордЪрдпреЛрдВ (permutations) рдХреА рдЧрд┐рдирддреА рдХрд░рддреА рд╣реИрдВред рдЗрдирдХрд╛ рдкреБрдирд░рд╛рд╡реГрддреНрддрд┐ рд╕реВрддреНрд░ рдЕрд▓рдЧ рд╣реИ, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), рдФрд░ рдпреЗ (рдЪрд┐рд╣реНрдиреЛрдВ рд╕рд╣рд┐рдд) рдПрдХ-рджреВрд╕рд░реЗ рдХреЗ рд╡реНрдпреБрддреНрдХреНрд░рдо рдЖрд╡реНрдпреВрд╣ (inverse matrices) рд╣реИрдВред

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

\(S(0,0)=1\) рдХреНрдпреЛрдВ рд╣реЛрддрд╛ рд╣реИ? рдкрд░рдВрдкрд░рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░, рд░рд┐рдХреНрдд рд╕рдореБрдЪреНрдЪрдп (empty set) рдХрд╛ рд╢реВрдиреНрдп рднрд╛рдЧреЛрдВ рдореЗрдВ рдареАрдХ рдПрдХ рд╣реА рд╡рд┐рднрд╛рдЬрди рд╣реЛрддрд╛ рд╣реИ: рд░рд┐рдХреНрдд рд╡рд┐рднрд╛рдЬрдиред

рдЬрдм \(k > n\) рд╣реЛ рддреЛ рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ? рдкрд░рд┐рдгрд╛рдо 0 рд╣реЛрддрд╛ рд╣реИ, рдХреНрдпреЛрдВрдХрд┐ рд╣рд░ рдЙрдкрд╕рдореБрдЪреНрдЪрдп рдЧреИрд░-рдЦрд╛рд▓реА рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдП рдФрд░ рдЖрдкрдХреЗ рдкрд╛рд╕ рддрддреНрд╡ рдмрд╣реБрдд рдХрдо рд╣реИрдВред

рдЗрд╕рдХрд╛ рдмреЗрд▓ рд╕рдВрдЦреНрдпрд╛рдУрдВ рд╕реЗ рдХреНрдпрд╛ рд╕рдВрдмрдВрдз рд╣реИ? \(k=0\) рд╕реЗ \(n\) рддрдХ рд╕рднреА \(S(n,k)\) рдХрд╛ рдпреЛрдЧ рдХрд░рдиреЗ рдкрд░ рдмреЗрд▓ рд╕рдВрдЦреНрдпрд╛ \(B(n)\) рдорд┐рд▓рддреА рд╣реИ, рдЬреЛ n рддрддреНрд╡реЛрдВ рд╡рд╛рд▓реЗ рд╕рдореБрдЪреНрдЪрдп рдХреЗ рдХреБрд▓ рд╡рд┐рднрд╛рдЬрдиреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ рд╣реИред

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

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

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