Реклама

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

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

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

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

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

Другие формулы

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

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

Свойства

где и . Начальные члены последовательности [2]:
1, 1, 3, 11, 53, 309, 2119, …
(найдено J. S. Madachy, 1979)

Примечания

  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]
Реклама