Субфакториал
Субфакториал числа n (обозначение: !n) определяется как количество беспорядков порядка n, то есть перестановок порядка n без неподвижных точек. Название субфакториал происходит из аналогии с факториалом, определяющим общее количество перестановок.
В частности, !n есть число способов положить n писем в n конвертов (по одному в каждый), чтобы ни одно не попало в соответствующий конверт (так называемая «Задача о письмах»).
Явная формула
Субфакториал можно вычислить с помощью принципа включения-исключения:
- [math]\displaystyle{ !n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+ ... +(-1)^n\frac{1}{n!}\right) = n!\sum_{k=0}^n\frac{(-1)^k}{k!} }[/math]
Другие формулы
- [math]\displaystyle{ !n = \frac{\Gamma (n+1, -1)}{e} }[/math], где [math]\displaystyle{ \Gamma }[/math] обозначает неполную гамма-функцию[англ.], а e — математическая константа;
- [math]\displaystyle{ !n = \left \lfloor \frac {n!}{e} \right \rceil }[/math], где [math]\displaystyle{ \left\lfloor x\right\rceil }[/math] обозначает ближайшее к x целое число.
- [math]\displaystyle{ !n = \left\lfloor \frac{n!+1}{e} \right\rfloor }[/math] (согласно Mehdi Hassani), где [math]\displaystyle{ \lfloor x \rfloor }[/math] обозначает целую часть числа.
- Справедливы формальные тождества: [math]\displaystyle{ Q^n = (P-1)^n }[/math] и [math]\displaystyle{ P^n = (Q+1)^n }[/math], где [math]\displaystyle{ P^k }[/math] нужно понимать как [math]\displaystyle{ k! }[/math], а [math]\displaystyle{ Q^k }[/math] — как [math]\displaystyle{ !k }[/math].
Таблица значений
| n | !n[1] |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 9 |
| 5 | 44 |
| 6 | 265 |
| 7 | 1854 |
| 8 | 14 833 |
| 9 | 133 496 |
| 10 | 1 334 961 |
| 11 | 14 684 570 |
| 12 | 176 214 841 |
| 13 | 2 290 792 932 |
| 14 | 32 071 101 049 |
| 15 | 481 066 515 734 |
| 16 | 7 697 064 251 745 |
| 17 | 130 850 092 279 664 |
| 18 | 2 355 301 661 033 953 |
| 19 | 44 750 731 559 645 100 |
| 20 | 895 014 631 192 902 100 |
Свойства
- [math]\displaystyle{ !n = {!(n-1)}\cdot n + (-1)^n }[/math]
- [math]\displaystyle{ !n = (n-1)\cdot ({!(n-1)}+{!(n-2)}) }[/math] (таким же свойством обладает сам факториал)
- [math]\displaystyle{ !n = (n-1)\cdot a_{n-2}, }[/math]
- где [math]\displaystyle{ \;a_0 = a_1 = 1 }[/math] и [math]\displaystyle{ a_n = n\cdot a_{n-1} + (n-1)\cdot a_{n-2} = {!(n+1)}+{!n} }[/math]. Начальные члены последовательности [math]\displaystyle{ a_n }[/math][2]:
- Число 148 349 является субфакторионом, т.е. равно сумме субфакториалов своих цифр (аналог факториона):
- [math]\displaystyle{ 148349 = {!1} + {!4} + {!8} + {!3} + {!4} + {!9} }[/math]
- (найдено J. S. Madachy, 1979)
- Субфакториал иногда допускается в математических играх типа получения различных результатов из определённых цифр (например, известна игра Четыре четвёрки, где равенство !4 = 9 может принести пользу).