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

Материал из Википедии — свободной энциклопедии

Субфакториал числа 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!}$

Содержание

1 Другие формулы
2 Таблица значений
3 Свойства субфакториала
- 3.1 Основные
- 3.2 Другие свойства

[править] Другие формулы

$!n = \frac{\Gamma (n+1, -1)}{e}\!$ , где $Γ$ обозначает неполную гамма-функцию (англ.), а 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$ обозначает целую часть числа.

[править] Таблица значений

!1 = 0

!2 = 1

!3 = 2

!4 = 9

!5 = 44

!6 = 265

!7 = 1 854

!8 = 14 833

!9 = 133 496

!10 = 1 334 961

!11 = 14 684 570

!12 = 176 214 841

!13 = 2 290 792 932

!14 = 32 071 101 049

!15 = 481 066 515 734

!16 = 7 697 064 251 745

!17 = 130 850 092 279 664

!18 = 2 355 301 661 033 953

!19 = 44 750 731 559 645 106

!20 = 895 014 631 192 902 121

!21 = 18 795 307 255 050 944 540

последовательность A000166 в OEIS

[править] Свойства субфакториала

[править] Основные

$!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$ . Получаем последовательность 1, 1, 3, 11, 53, 309, 2119 … (последовательность A000255 в OEIS).

[править] Другие свойства

Число 148349 равно сумме субфакториалов своих цифр (аналог факториона):

$148349 = !1 + !4 + !8 + !3 + !4 + !9~$

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

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

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

Материал из Википедии — свободной энциклопедии

Содержание

[править] Другие формулы

[править] Таблица значений

[править] Свойства субфакториала

[править] Основные

[править] Другие свойства

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках