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

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

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

Явна формула

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

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

Інші формули

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

Властивості

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

1, 1, 3, 11, 53, 309, 2119, … (послідовність A000255 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

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

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

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

Посилання

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — .(укр.)
• John C. Baez. Let's get deranged!, December 14, 2003