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

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

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

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

${\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 может принести пользу).

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