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

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

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

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

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

${\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 }$ обозначает неполную гамма-функцию^[en], а e — математическая константа;
• ${\displaystyle !n=\left\lfloor {\frac {n!}{e}}\right\rceil }$, где ${\displaystyle \left\lfloor x\right\rceil }$ обозначает ближайшее к x целое число (округление).
• ${\displaystyle !n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor }$ (согласно Mehdi Hassani), где ${\displaystyle \lfloor x\rfloor }$ обозначает целую часть числа.
• Справедливы формальные тождества: ${\displaystyle Q^{n}=(P-1)^{n}}$ и ${\displaystyle P^{n}=(Q+1)^{n}}$, где ${\displaystyle P^{k}}$ нужно понимать как ${\displaystyle k!}$, а ${\displaystyle Q^{k}}$ — как ${\displaystyle !k}$.

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

Свойства

• ${\displaystyle !n={!(n-1)}\cdot n+(-1)^{n}}$
• ${\displaystyle !n=(n-1)\cdot ({!(n-1)}+{!(n-2)})}$ (таким же свойством обладает сам факториал)
• ${\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}}$^[2]:

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

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

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

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

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

Примечания

Эта страница в последний раз была отредактирована 9 февраля 2024 в 17:44.