WikiSort.ru - Не сортированное

В комбинаторике беспорядком называется перестановка без неподвижных точек.

Примеры

   BADC, BCDA, BDAC,
   CADB, CDAB, CDBA,
   DABC, DCAB, DCBA.

Количество беспорядков

Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением

${\displaystyle !n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\dots +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}},}$

которое называется субфакториалом числа n.

Количество беспорядков ${\displaystyle !n=d(n)}$ удовлетворяет рекурсивным соотношениям

${\displaystyle d(n)=(n-1)[d(n-1)+d(n-2)]}$

и

${\displaystyle d(n)=nd(n-1)+(-1)^{n},}$

где ${\displaystyle d(1)=0}$ и ${\displaystyle d(2)=1}$ .

В виду того, что ${\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}}$ , значение ${\displaystyle !n}$ с ростом ${\displaystyle n}$ ведёт себя как ${\displaystyle {\frac {n!}{e}}}$ . Более того, при ${\displaystyle n>0}$ его можно представить как результат округления числа ${\displaystyle {\frac {n!}{e}}}$ .

См. также

• Парадокс дней рождения

Ссылки

• Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.