WikiSort.ru - Не сортированное

Субфакториал числа 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 }$ обозначает неполную гамма-функцию (англ.), а 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+1}$ . Начальные члены последовательности ${\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 может принести пользу).

Примечания