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

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

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

Cубфакториалы всех чисел составляют последовательность A000166 в OEIS

n	!n
0	1
1	0
2	1
3	2
4	9
5	44
6	265
7	1 854
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
21	18 795 307 255 050 944 540
22	413 496 759 611 120 779 881
23	9 510 425 471 055 777 937 262

Свойства

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

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

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

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

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

• ${\displaystyle !n={\begin{cases}1&n=0;\\{!(n-1)}\cdot n+(-1)^{n}&n>0.\end{cases}}}$

• ${\displaystyle !n={\begin{cases}1&n=0;\\0&n=1;\\(n-1)\cdot ({!(n-1)}+{!(n-2)})&n>1.\end{cases}}}$
• ${\displaystyle !n=(n-1)\cdot a_{n-2}}$, где ${\displaystyle \;a_{0}=a_{1}=1}$ и ${\displaystyle a_{n}=n\cdot a_{n-1}+(n-1)\cdot a_{n-2}={!(n+1)}+{!n}}$ (начальные члены последовательности ${\displaystyle a_{n}}$^[1] — 1, 1, 3, 11, 53, 309, 2119, …;

Число 148 349 является субфакторионом, то есть равно сумме субфакториалов своих цифр (аналог факториона)^[2]:

${\displaystyle 148349={!1}+{!4}+{!8}+{!3}+{!4}+{!9}}$.

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

Примечания

1. Последовательность A000255 в OEIS = a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]
2. J. S. Madachy, 1979

Литература

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