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

Субфакторіал числа n (позначається як !n) — кількість інверсій порядку n, — перестановок порядку n без нерухомих точок. Назва субфакторіал походить від аналогії з факторіалом, який визначає загальну кількість перестановок.

Зокрема, !n є число способів покласти n листів в n конвертів (по одному в кожен) так, щоб жодний лист не потрапив у відповідний конверт (так звана «задача про листи»).

Явна формула

Субфакторіал можна обчислити за допомогою принципу включення-виключення: 

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

Інші формули

• $!n=\frac{\mathrm{\Gamma }(n+1,-1)}{e}$, де $\mathrm{\Gamma }$ позначає неповну гамма-функцію, a e — математична константа;
• $!n=\lfloor \frac{n!}{e}\rceil$, де $\lfloor x\rceil$ позначає найближче до x ціле число;
• $!n=\lfloor \frac{n!+1}{e}\rfloor$  де $\lfloor x\rfloor$ позначає цілу частину числа.
• Справедливі формальні тотожності: $Q^n=(P-1{)}^n$ та $P^n=(Q+1{)}^n$, де $P^k$ треба розуміти як $k!$, а $Q^k$ — як $!k$.

Таблиця значень

Кількість можливих перестановок і безладів n елементів. n! (N факторіал) — кількість n-перестановок; !N (n субфакторіал) — кількість безладів, де всі n елементів змінити свої початкові місця

!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

Властивості

• $!n=(n-1)\cdot (!(n-1)+!(n-2))$ (такі ж властивості притаманні і факторіалу): де $a_0=a_1=1$ і $a_n=n\cdot a_{n-1}+(n-1)\cdot a_{n-2}=!(n+1)+!n$. Початкові члени послідовності $a_n$:

1, 1, 3, 11, 53, 309, 2119, … (Шаблон:OEIS)

• Число 148349 є субфакторіоном, тобто дорівнює сумі субфакторіалів своїх цифр (аналог факторіона):

$148349=!1+!4+!8+!3+!4+!9$ (знайдене J. S. Madachy, 1979)

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

Посилання

• Шаблон:Вишенський.Перестюк.Комбінаторика
• John C. Baez. Let's get deranged!, December 14, 2003