Субфакториалы в степени

В данной статье рассказывается про количество способов составления перестановок, которые являются попарными беспорядками, и беспорядком для последовательности {1,2,…,n} что является общим случаем для Субфакториала, для которого создаётся лишь одна такая перестановка.

Определение

!^kn — количество вариантов составить k перестановок из n чисел, так, что они являются попарными беспорядками, а также беспорядком для фиксированной перестановки n чисел.

Формула

Формула выводится рекуррентно, через формулу, которая находит количество способов составить перестановку для фиксированных k перестановок. В дальнейшем обозначим это число за fix^kn. Находя количество способов составить первую, вторую, …, k-тую перестановку мы найдём количество способов составить их все.

$\prod _{l=1}^{k}fix_{l}n$

$fix_{k}n=n!-k*n!+\sum _{i=2}^{n}(-1)^{i}*(C_{n}^{i}*k^{i}+\sum _{j=2}^{i}((-1)^{j+1}*n*C_{k}^{j}*C_{n-j}^{i-j}*k^{i-j}*(C_{j}^{j-1}-1)-\sum _{b=2}^{j}(num(t_{b})))*(n-i)!)$

Доказательство

Формула строится на Формуле включений-исключений. Нам нужно сначала найти все порядки для одного числа, потом порядки для 2 чисел, …, порядки для n чисел. Сложность заключается в том, что когда мы ищем порядки для нескольких чисел, мы можем закрепить 2 числа на одной позиции, что невозможно поэтому нам нужно найти число таких случаев. Введём понятие: i-пересечение (для множества чисел В) — i чисел из данного множества, которые находятся на одной позиции в разных перестановках. Тогда мы отнимем варианты выбора позиций, где есть 2-пересечения и посмотрим, какие варианты мы отняли несколько раз. Мы могли отнять несколько раз либо за случаи, где несколько 2-пересечений находятся в одном столбце, либо за случаи, где они находятся в разных. В случае с разными столбцами, это будет число num(t_i), в случае с одним мы снова прибавим варианты за все 3-пересечения, отнимем за 4-пересечения и так далее, что можно заметить снова образует Формулу включений-исключений.