Субфакториал

Субфакториал числа n (обозначение: !n) определяется как количество беспорядков порядка n, то есть перестановок порядка n без неподвижных точек. Название субфакториал происходит из аналогии с факториалом, определяющим общее количество перестановок.

В частности, !n есть число способов положить n писем в n конвертов (по одному в каждый), чтобы ни одно не попало в соответствующий конверт (так называемая «Задача о письмах»).

Явная формула

Субфакториал можно вычислить с помощью принципа включения-исключения:

$!n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1{)}^n\frac{1}{n!})=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$

Другие формулы

• $!n=\frac{\mathrm{\Gamma }(n+1,-1)}{e}$, где $\mathrm{\Gamma }$ обозначает неполную гамма-функцию, а e — математическая константа;
• $!n=\lfloor \frac{n!}{e}\rceil$, где $\lfloor x\rceil$ обозначает ближайшее к x целое число.
• $!n=\lfloor \frac{n!+1}{e}\rfloor$ (согласно Mehdi Hassani), где $\lfloor x\rfloor$ обозначает целую часть числа.
• Справедливы формальные тождества: $Q^n=(P-1{)}^n$ и $P^n=(Q+1{)}^n$, где $P^k$ нужно понимать как $k!$, а $Q^k$ — как $!k$.

Таблица значений

n	!n
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

Свойства

• $!n=!(n-1)\cdot n+(-1{)}^n$
• $!n=(n-1)\cdot (!(n-1)+!(n-2))$ (таким же свойством обладает сам факториал)
• $!n=(n-1)\cdot a_{n-2},$

где $a_0=a_1=1$ и $a_n=n\cdot a_{n-1}+(n-1)\cdot a_{n-2}=!(n+1)+!n$. Начальные члены последовательности $a_n$:

1, 1, 3, 11, 53, 309, 2119, …

• Число 148 349 является субфакторионом, т.е. равно сумме субфакториалов своих цифр (аналог факториона):

$148349=!1+!4+!8+!3+!4+!9$

(найдено J. S. Madachy, 1979)

• Субфакториал иногда допускается в математических играх типа получения различных результатов из определённых цифр (например, известна игра Четыре четвёрки, где равенство !4 = 9 может принести пользу).