Русская Википедия:Субфакториал
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Субфакториал числа n (обозначение: !n) определяется как количество беспорядков порядка n, то есть перестановок порядка n без неподвижных точек. Название субфакториал происходит из аналогии с факториалом, определяющим общее количество перестановок.
В частности, !n есть число способов положить n пронумерованных писем в n пронумерованных конвертов (по одному в каждый), чтобы ни одно из писем не попало в конверт с соответствующим ему номером (так называемая «Задача о письмах»).
Явная формула
Субфакториал можно вычислить с помощью принципа включения-исключения:
- <math>!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!}</math>
Другие формулы
- <math>!n = \frac{\Gamma (n+1, -1)}{e}</math>, где <math>\Gamma</math> обозначает en (incomplete gamma function), а e — математическая константа;
- <math>!n = \left \lfloor \frac {n!}{e} \right \rceil</math>, где <math>\left\lfloor x\right\rceil</math> обозначает ближайшее к x целое число (округление).
- <math>!n = \left\lfloor \frac{n!+1}{e} \right\rfloor</math> (согласно Mehdi Hassani), где <math>\lfloor x \rfloor</math> обозначает целую часть числа.
- Справедливы формальные тождества: <math>Q^n = (P-1)^n</math> и <math>P^n = (Q+1)^n</math>, где <math>P^k</math> нужно понимать как <math>k!</math>, а <math>Q^k</math> — как <math>!k</math>.
Таблица значений
| Шаблон:Mvar | !Шаблон:Mvar[1] |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | Шаблон:Num1 |
| 5 | Шаблон:Num1 |
| 6 | Шаблон:Num1 |
| 7 | Шаблон:Num1 |
| 8 | Шаблон:Num1 |
| 9 | Шаблон:Num1 |
| 10 | Шаблон:Num1 |
| 11 | Шаблон:Num |
| 12 | Шаблон:Num |
| 13 | Шаблон:Num |
| 14 | Шаблон:Num |
| 15 | Шаблон:Num |
| 16 | Шаблон:Num |
| 17 | Шаблон:Num |
| 18 | Шаблон:Num |
| 19 | 44 750 731 559 645 104 |
| 20 | 895 014 631 192 902 121 |
Свойства
- <math>!n = {!(n-1)}\cdot n + (-1)^n</math>
- <math>!n = (n-1)\cdot ({!(n-1)}+{!(n-2)})</math> (таким же свойством обладает сам факториал)
- <math>!n = (n-1)\cdot a_{n-2},</math>
- где <math>\;a_0 = a_1 = 1</math> и <math>a_n = n\cdot a_{n-1} + (n-1)\cdot a_{n-2} = {!(n+1)}+{!n}</math>. Начальные члены последовательности <math>a_n</math>[2]:
- 1, Шаблон:Nums, …
- Число Шаблон:Num является субфакторионом, т.е. равно сумме субфакториалов своих цифр (аналог факториона):
- <math>148349 = {!1} + {!4} + {!8} + {!3} + {!4} + {!9}</math>
- (найдено J. S. Madachy, 1979)
- Субфакториал иногда допускается в математических играх типа получения различных результатов из определённых цифр (например, известна игра Четыре четвёрки, где равенство !4 = 9 может принести пользу).
Примечания
Шаблон:Примечания Шаблон:Последовательности и ряды
