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

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

Одно из объяснений: $!n$ есть число способов положить $n$ пронумерованных писем в $n$ пронумерованных конвертов (по одному в каждый), чтобы ни одно из писем не попало в конверт с соответствующим ему номером («задача о письмах»). Термин введён Уильямом Уитвортом в конце XIX века, но неявно в комбинаторных задачах использовался и ранее.

Свойства

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

$!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!}}$.

Некоторые другие способы вычисления:

• $!n={\frac {\Gamma (n+1,-1)}{e}}$, где $\Gamma$ обозначает неполную гамма-функцию, а $e$ — основание натурального логарифма;
• $!n=\left\lfloor {\frac {n!}{e}}\right\rceil$, где $\left\lfloor x\right\rceil$ обозначает ближайшее к $x$ целое число (округление);
• $!n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor$, где $\lfloor x\rfloor$ обозначает целую часть числа.

Некоторые рекуррентные формулы:

• $!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}$.

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

Первые значения

$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 104
20	895 014 631 192 902 121

Литература

• Р. Стенли. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.