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

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

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

Явная формулаПравить

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

 

Другие формулыПравить

  •  , где   обозначает неполную гамма-функцию (англ.), а e — математическая константа;
  •  , где   обозначает ближайшее к x целое число.
  •   (согласно Mehdi Hassani), где   обозначает целую часть числа.
  • Справедливы формальные тождества:   и  , где   нужно понимать как  , а   — как  .

Таблица значенийПравить

n !n[1]
1 0
2 1
3 2
4 9
5 44
6 265
7 1854
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 100
20 895 014 631 192 902 100

СвойстваПравить

  •  
  •   (таким же свойством обладает сам факториал)
  •  
где   и  . Начальные члены последовательности  [2]:
1, 1, 3, 11, 53, 309, 2119, …
 
(найдено J. S. Madachy, 1979)
  • Субфакториал иногда допускается в математических играх типа получения различных результатов из определённых цифр (например, известна игра Четыре четвёрки, где равенство !4 = 9 может принести пользу).

ПримечанияПравить

  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]