рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИ?
рдХрд┐рд╕реА рдЛрдгреЗрддрд░ рдкреВрд░реНрдгрд╛рдВрдХ n рдХрд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓, рдЬрд┐рд╕реЗ n! рд▓рд┐рдЦрд╛ рдЬрд╛рддрд╛ рд╣реИ, 1 рд╕реЗ рд▓реЗрдХрд░ n рддрдХ рдХреЗ рд╣рд░ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рдЧреБрдгрдирдлрд▓ рд╣реЛрддрд╛ рд╣реИред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, \(5! = 1 \times 2 \times 3 \times 4 \times 5 = 120\)ред рдЧрдгрд┐рддреАрдп рдкрд░рдВрдкрд░рд╛ рдХреЗ рдЕрдиреБрд╕рд╛рд░ \(0! = 1\) рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИ (рд░рд┐рдХреНрдд рдЧреБрдгрдирдлрд▓)ред рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдмрд╣реБрдд рддреЗрдЬрд╝реА рд╕реЗ рдмрдврд╝рддреЗ рд╣реИрдВ тАФ 10! рдХрд╛ рдорд╛рди рд╣реА рддреАрд╕ рд▓рд╛рдЦ рд╕реЗ рдКрдкрд░ рдкрд╣реБрдБрдЪ рдЬрд╛рддрд╛ рд╣реИ тАФ рдЗрд╕рд▓рд┐рдП рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ 0 рд╕реЗ 170 рддрдХ рдХреЗ рдорд╛рдиреЛрдВ рдХрд╛ рд╕рдорд░реНрдерди рдХрд░рддрд╛ рд╣реИ, рдЬреЛ рдХрд┐рд╕реА рдорд╛рдирдХ рдбрдмрд▓-рдкреНрд░рд┐рд╕реАрдЬрд╝рди рд╕рдВрдЦреНрдпрд╛ рдореЗрдВ рд╕рдорд╛ рд╕рдХрдиреЗ рд╡рд╛рд▓рд╛ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рд╣реИред
рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдХрд╛ рдЙрдкрдпреЛрдЧ рдХреИрд╕реЗ рдХрд░реЗрдВ
0 рд╕реЗ 170 рдХреЗ рдмреАрдЪ рдХреЛрдИ рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ n рдбрд╛рд▓реЗрдВ рдФрд░ рдпрд╣ рдЯреВрд▓ рддреБрд░рдВрдд n! рдХрд╛ рдорд╛рди рджрд┐рдЦрд╛ рджреЗрдЧрд╛ред рдЗрд╕рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреБрдЫ рднреА рд╕реЗрдЯ рдХрд░рдиреЗ рдХреА рдЬрд╝рд░реВрд░рдд рдирд╣реАрдВ рд╣реИ: рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреЗрд╡рд▓ рдЛрдгреЗрддрд░ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЗ рд▓рд┐рдП рд╣реА рдкрд░рд┐рднрд╛рд╖рд┐рдд рд╣реЛрддрд╛ рд╣реИ, рдЗрд╕рд▓рд┐рдП рджрд╢рдорд▓рд╡ рдпрд╛ рдЛрдгрд╛рддреНрдордХ рд╕рдВрдЦреНрдпрд╛рдПрдБ рд╕реНрд╡реАрдХрд╛рд░ рдирд╣реАрдВ рдХреА рдЬрд╛рддреАрдВред рдкрд░рд┐рдгрд╛рдо рдкреИрдирд▓ рдореЗрдВ n! рдХрд╛ рдкреВрд░рд╛ рдЧрдгрдирд╛ рдХрд┐рдпрд╛ рд╣реБрдЖ рдорд╛рди рджрд┐рдЦрд╛рдИ рджреЗрддрд╛ рд╣реИред
рд╕реВрддреНрд░ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рдЧрдгрд┐рддреАрдп рд░реВрдк рд╕реЗ,
$$\text{n}! = \prod_{i=1}^{\text{n}} i = 1 \times 2 \times 3 \times \cdots \times \text{n}$$рдЗрд╕реЗ рдкреБрдирд░рд╛рд╡рд░реНрддреА (recursive) рд░реВрдк рдореЗрдВ рднреА рд▓рд┐рдЦ рд╕рдХрддреЗ рд╣реИрдВ: \(n! = n \times (n - 1)!\), рдЬрд╣рд╛рдБ рдЖрдзрд╛рд░ рд╕реНрдерд┐рддрд┐ \(0! = 1\) рд╣реЛрддреА рд╣реИред рд╣рд░ рдЪрд░рдг рдореЗрдВ рдЪрд▓ рд░рд╣реЗ рдЧреБрдгрдирдлрд▓ рдХреЛ рдЕрдЧрд▓реЗ рдкреВрд░реНрдгрд╛рдВрдХ рд╕реЗ рдЧреБрдгрд╛ рдХрд░ рджрд┐рдпрд╛ рдЬрд╛рддрд╛ рд╣реИред рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдпрд╣ рдЧрд┐рдирддрд╛ рд╣реИ рдХрд┐ n рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╡рд╕реНрддреБрдУрдВ рдХреЛ рдХреНрд░рдо рдореЗрдВ рдХрд┐рддрдиреЗ рддрд░реАрдХреЛрдВ рд╕реЗ рд╡реНрдпрд╡рд╕реНрдерд┐рдд рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ (рдХреНрд░рдордЪрдп/permutations), рдпрд╣реА рдХрд╛рд░рдг рд╣реИ рдХрд┐ рдпреЗ рдХреЙрдореНрдмрд┐рдиреЗрдЯрд░рд┐рдХреНрд╕, рдкреНрд░рд╛рдпрд┐рдХрддрд╛ рдФрд░ рд╢реНрд░реЗрдгреА рд╡рд┐рд╕реНрддрд╛рд░ рдореЗрдВ рд╣рд░ рдЬрдЧрд╣ рджрд┐рдЦрд╛рдИ рджреЗрддреЗ рд╣реИрдВред
рд╣рд▓ рдХрд┐рдпрд╛ рд╣реБрдЖ рдЙрджрд╛рд╣рд░рдг
6! рдирд┐рдХрд╛рд▓рдиреЗ рдХреЗ рд▓рд┐рдП рдЪрд░рдг-рджрд░-рдЪрд░рдг рдЧреБрдгрд╛ рдХрд░реЗрдВ: \(1 \times 2 = 2\), \(\times 3 = 6\), \(\times 4 = 24\), \(\times 5 = 120\), \(\times 6 = 720\)ред
$$6! = 720$$рдЗрд╕рдХрд╛ рдЕрд░реНрде рд╣реИ рдХрд┐ рдЫрд╣ рдЕрд▓рдЧ-рдЕрд▓рдЧ рд╡рд╕реНрддреБрдУрдВ рдХреЛ 720 рдЕрд▓рдЧ-рдЕрд▓рдЧ рддрд░реАрдХреЛрдВ рд╕реЗ рдХреНрд░рдо рдореЗрдВ рд▓рдЧрд╛рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред
0 рд╕реЗ 20 рддрдХ n рдХреЗ рд▓рд┐рдП рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдорд╛рди
рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ \(n!\) рд╕рднреА рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХрд╛ рдЧреБрдгрдирдлрд▓ рд╣реИ рдЬреЛ \(n\) рддрдХ рд╣реИрдВ, рдЬрд┐рд╕рдореЗрдВ рдкрд░рд┐рдкрд╛рдЯреА \(0! = 1\) рд╣реИред рдкреНрд░рддреНрдпреЗрдХ рдорд╛рди рдЕрдкрдиреЗ рдкрд┐рдЫрд▓реЗ рдорд╛рди рд╕реЗ рдкреНрд░рд╛рдкреНрдд рд╣реЛрддрд╛ рд╣реИ: \(n! = n \times (n-1)!\).
| n | n! |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5,040 |
| 8 | 40,320 |
| 9 | 362,880 |
| 10 | 3,628,800 |
| 11 | 39,916,800 |
| 12 | 479,001,600 |
| 13 | 6,227,020,800 |
| 14 | 87,178,291,200 |
| 15 | 1,307,674,368,000 |
| 16 | 20,922,789,888,000 |
| 17 | 355,687,428,096,000 |
| 18 | 6,402,373,705,728,000 |
| 19 | 121,645,100,408,832,000 |
| 20 | 2,432,902,008,176,640,000 |
рдмрдбрд╝реЗ рдореАрд▓ рдХреЗ рдкрддреНрдерд░ (рд▓рдЧрднрдЧ, рд╡реИрдЬреНрдЮрд╛рдирд┐рдХ рд╕рдВрдХреЗрддрди рдореЗрдВ)
| n | n! (рд▓рдЧрднрдЧ) |
|---|---|
| 25 | 1.551 ├Ч 1025 |
| 50 | 3.041 ├Ч 1064 |
| 100 | 9.333 ├Ч 10157 |
| 170 | 7.257 ├Ч 10306 |
170 рд╡рд╣ рд╕рдмрд╕реЗ рдмрдбрд╝реА рдкреВрд░реНрдг рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдЬрд┐рд╕рдХрд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдПрдХ рдорд╛рдирдХ 64-рдмрд┐рдЯ рдлреНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рд╕рдВрдЦреНрдпрд╛ рдореЗрдВ рд╕рдорд╛ рдЬрд╛рддрд╛ рд╣реИ (рдЕрдзрд┐рдХрддрдо рд▓рдЧрднрдЧ 1.8 ├Ч 10308); 171! рдЙрд╕ рд╕реАрдорд╛ рд╕реЗ рдЕрдзрд┐рдХ рд╣реИ, рдЗрд╕реАрд▓рд┐рдП рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ n рдХреЗ рд▓рд┐рдП 0 рд╕реЗ 170 рддрдХ рд╕реНрд╡реАрдХрд╛рд░ рдХрд░рддрд╛ рд╣реИред
рдмрдбрд╝реЗ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреА рд╡реНрдпрд╛рдЦреНрдпрд╛
рд╕рдЯреАрдХрддрд╛ рдФрд░ рдкреВрд░реНрдгрд╛рдВрдХрдиред рдорд╛рдирдХ рдбрдмрд▓-рдкреНрд░рд┐рд╕рд┐рдЬрди рдлреНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рд╕рдВрдЦреНрдпрд╛рдПрдБ рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рдХреЛ рдХреЗрд╡рд▓ \(2^{53} = 9{,}007{,}199{,}254{,}740{,}992 \approx 9.007 \times 10^{15}\) рддрдХ рд╣реА рд╕рдЯреАрдХ рд░реВрдк рд╕реЗ рд╕рдВрдЧреНрд░рд╣реАрдд рдХрд░рддреА рд╣реИрдВред рдЪреВрдБрдХрд┐ \(18! \approx 6.40 \times 10^{15}\) рдЕрдм рднреА рдЗрд╕ рд╕реАрдорд╛ рд╕реЗ рдиреАрдЪреЗ рд╣реИ рдФрд░ \(19! \approx 1.22 \times 10^{17}\) рдкрд╣рд▓рд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рд╣реИ рдЬреЛ рдЗрд╕рд╕реЗ рдКрдкрд░ рд╣реИ, 19! рд╕реЗ рдЖрдЧреЗ рдХреЗ рдкрд░рд┐рдгрд╛рдореЛрдВ рдореЗрдВ рд╕рд╛рдзрд╛рд░рдг рдлреНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рдореЗрдВ рдЧрдгрдирд╛ рдХрд░рдиреЗ рдкрд░ рдЕрдВрддрд┐рдо рдЕрдВрдХ рдкреВрд░реНрдгрд╛рдВрдХрд┐рдд рд╣реЛ рд╕рдХрддреЗ рд╣реИрдВред рдмрдбрд╝реЗ рдорд╛рдиреЛрдВ рдХреЛ, рд╡рд┐рд╢реЗрд╖рдХрд░ рд╡реИрдЬреНрдЮрд╛рдирд┐рдХ рд╕рдВрдХреЗрддрди рдореЗрдВ рджрд┐рдЦрд╛рдП рдЧрдП рдорд╛рдиреЛрдВ рдХреЛ, рд╡рд╛рд╕реНрддрд╡рд┐рдХ рдкреВрд░реНрдгрд╛рдВрдХ рдХреЗ рдЕрдиреБрдорд╛рди рдХреЗ рд░реВрдк рдореЗрдВ рд╕рдордЭреЗрдВред
рд╡реГрджреНрдзрд┐ред рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХрд┐рд╕реА рднреА рдШрд╛рддрд╛рдВрдХреАрдп рд╡реГрджреНрдзрд┐ рд╕реЗ рднреА рддреЗрдЬрд╝ рдмрдврд╝рддреЗ рд╣реИрдВред 20! рдореЗрдВ рдкрд╣рд▓реЗ рд╕реЗ 19 рдЕрдВрдХ рд╣реИрдВ, рдФрд░ 100! рдореЗрдВ 158 рдЕрдВрдХ рд╣реИрдВред \(n!\) рдХреЗ рдЕрдВрдХреЛрдВ рдХреА рд╕рдВрдЦреНрдпрд╛ \(\lfloor \log_{10}(n!) \rfloor + 1\) рд╣реЛрддреА рд╣реИред 170! рдореЗрдВ 307 рдЕрдВрдХ рд╣реИрдВ (рд▓рдЧрднрдЧ 7.26 ├Ч 10306)ред
рдХреНрд░рдордЪрдпред \(n!\) рдЙрди рддрд░реАрдХреЛрдВ рдХреА рдЧрд┐рдирддреА рдХрд░рддрд╛ рд╣реИ рдЬрд┐рдирд╕реЗ \(n\) рднрд┐рдиреНрди рд╡рд╕реНрддреБрдУрдВ рдХреЛ рдХреНрд░рдо рдореЗрдВ рд╡реНрдпрд╡рд╕реНрдерд┐рдд рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП, рдПрдХ рд╢реЗрд▓реНрдл рдкрд░ рд░рдЦреА 5 рдХрд┐рддрд╛рдмреЛрдВ рдХреЛ \(5! = 120\) рддрд░реАрдХреЛрдВ рд╕реЗ рдХреНрд░рдордмрджреНрдз рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИ, рдФрд░ 52 рдкрддреНрддреЛрдВ рдХреА рдПрдХ рддрд╛рд╢ рдХреА рдЧрдбреНрдбреА рдХреЛ \(52! \approx 8.07 \times 10^{67}\) рддрд░реАрдХреЛрдВ рд╕реЗ рдХреНрд░рдордмрджреНрдз рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред
рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд╕рдиреНрдирд┐рдХрдЯрди рдХреЗ рд╕рд╛рде рдЬрд╛рдБрдЪред рдмрдбрд╝реЗ \(n\) рдХреЗ рд▓рд┐рдП:
$$n! \approx \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^{n}$$
\(n = 10\) рдХреЗ рд▓рд┐рдП рдХрд╛рд░реНрдп рдХреА рдЬрд╛рдБрдЪ: \(\sqrt{2\pi \cdot 10} \approx 7.927\) рдФрд░ \((10/e)^{10} \approx 4.540 \times 10^{5}\), рдЗрд╕рд▓рд┐рдП \(10! \approx 7.927 \times 4.540 \times 10^{5} \approx 3.599 \times 10^{6}\)ред рд╕рдЯреАрдХ рдорд╛рди 3628800 рд╣реИ, so рд╕реНрдЯрд░реНрд▓рд┐рдВрдЧ рд▓рдЧрднрдЧ 0.8% рдХрдо рд╣реИред рдЬреИрд╕реЗ-рдЬреИрд╕реЗ \(n\) рдмрдврд╝рддрд╛ рд╣реИ, рд╕рд╛рдкреЗрдХреНрд╖ рддреНрд░реБрдЯрд┐ рдШрдЯрддреА рд╣реИ (рд▓рдЧрднрдЧ \(1/(12n)\)), рдЬрд┐рд╕рд╕реЗ рдпрд╣ рдмрдбрд╝реЗ рдкрд░рд┐рдгрд╛рдореЛрдВ рдХреЗ рд▓рд┐рдП рдкрд░рд┐рдорд╛рдг-рдХреНрд░рдо рдХреА рдПрдХ рдЙрдкрдпреЛрдЧреА рдЬрд╛рдБрдЪ рдмрди рдЬрд╛рддреА рд╣реИред
рдЕрдХреНрд╕рд░ рдкреВрдЫреЗ рдЬрд╛рдиреЗ рд╡рд╛рд▓реЗ рдкреНрд░рд╢реНрди
0! рдХрд╛ рдорд╛рди 1 рдХреНрдпреЛрдВ рд╣реЛрддрд╛ рд╣реИ? рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреНрд░рдордЪрдп (permutations) рдЧрд┐рдирддрд╛ рд╣реИ, рдФрд░ рд╢реВрдиреНрдп рд╡рд╕реНрддреБрдУрдВ рдХреЛ рд╡реНрдпрд╡рд╕реНрдерд┐рдд рдХрд░рдиреЗ рдХрд╛ рдареАрдХ рдПрдХ рд╣реА рддрд░реАрдХрд╛ рд╣реЛрддрд╛ рд╣реИ (рд░рд┐рдХреНрдд рд╡реНрдпрд╡рд╕реНрдерд╛)ред рд╕рд╛рде рд╣реА рдпрд╣ nCr рдЬреИрд╕реЗ рд╕реВрддреНрд░реЛрдВ рдХреЛ рднреА рд╕реБрд╕рдВрдЧрдд рдмрдирд╛рдП рд░рдЦрддрд╛ рд╣реИред
рдХреНрдпрд╛ рдореИрдВ рдХрд┐рд╕реА рджрд╢рдорд▓рд╡ рд╕рдВрдЦреНрдпрд╛ рдХрд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдирд┐рдХрд╛рд▓ рд╕рдХрддрд╛ рд╣реВрдБ? рд╕рд╛рдорд╛рдиреНрдп рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рд╕реЗ рдирд╣реАрдВред рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рдХреЛ рдЧреИрд░-рдкреВрд░реНрдгрд╛рдВрдХреЛрдВ рддрдХ рдмрдврд╝рд╛рдиреЗ рдХреЗ рд▓рд┐рдП рдЧрд╛рдорд╛ рдлрд▓рди (Gamma function) рдХреА рдЬрд╝рд░реВрд░рдд рд╣реЛрддреА рд╣реИ, рдЬреЛ рдпрд╣ рдХреИрд▓рдХреБрд▓реЗрдЯрд░ рдирд╣реАрдВ рдХрд░рддрд╛ред
170 рдкрд░ рд╣реА рдХреНрдпреЛрдВ рд░реБрдХрддреЗ рд╣реИрдВ? \(170! \approx 7.26 \times 10^{306}\) рд╣реИ, рдЬреЛ рдХрд┐рд╕реА рдбрдмрд▓-рдкреНрд░рд┐рд╕реАрдЬрд╝рди рдлрд╝реНрд▓реЛрдЯрд┐рдВрдЧ-рдкреЙрдЗрдВрдЯ рд╕рдВрдЦреНрдпрд╛ рдореЗрдВ рд╕рдорд╛ рд╕рдХрдиреЗ рд╡рд╛рд▓реЗ рдЕрдзрд┐рдХрддрдо рдорд╛рди рд╕реЗ рдиреАрдЪреЗ рдХрд╛ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдлреИрдХреНрдЯреЛрд░рд┐рдпрд▓ рд╣реИ; 171! рдУрд╡рд░рдлрд╝реНрд▓реЛ рд╣реЛрдХрд░ рдЕрдирдВрдд (infinity) рдмрди рдЬрд╛рддрд╛ рд╣реИред