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

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

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

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

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

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

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

n	!n[1]	n	!n
1	0	11	14 684 570
2	1	12	176 214 841
3	2	13	2 290 792 932
4	9	14	32 071 101 049
5	44	15	481 066 515 734
6	265	16	7 697 064 251 745
7	1854	17	130 850 092 279 664
8	14 833	18	2 355 301 661 033 953
9	133 496	19	44 750 731 559 645 106
10	1 334 961	20	895 014 631 192 902 121

Свойства

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

[2]:

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

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

148349={!1}+{!4}+{!8}+{!3}+{!4}+{!9}

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

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

Примечания

Последовательность A000166 в OEIS = Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points
Последовательность A000255 в OEIS = a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Последовательность A000166 в OEIS = Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points

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