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

Перейти к навигации Перейти к поиску

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

Одно из объяснений: $!n$ есть число способов положить $n$ пронумерованных писем в $n$ пронумерованных конвертов (по одному в каждый), чтобы ни одно из писем не попало в конверт с соответствующим ему номером («задача о письмах»). Термин введён Уильямом Уитвортом^[англ.] в конце XIX века, но неявно в комбинаторных задачах использовался и ранее.

Cубфакториалы всех чисел составляют последовательность A000166 в OEIS
n	!n
0	1
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 104
20	895 014 631 192 902 121
21	18 795 307 255 050 944 540
22	413 496 759 611 120 779 881
23	9 510 425 471 055 777 937 262

Свойства

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

!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!}}

Некоторые другие способы вычисления:

$!n={\frac {\Gamma (n+1,-1)}{e}}$ , где $\Gamma$ обозначает неполную гамма-функцию^?!, а $e$ — основание натурального логарифма;
$!n=\left\lfloor {\frac {n!}{e}}\right\rceil$ , где $\left\lfloor x\right\rceil$ обозначает ближайшее к $x$ целое число (округление);
$!n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor$ , где $\lfloor x\rfloor$ обозначает целую часть числа.

Некоторые рекуррентные формулы:

$!n={\begin{cases}1&n=0;\\{!(n-1)}\cdot n+(-1)^{n}&n>0.\end{cases}}$

$!n={\begin{cases}1&n=0;\\0&n=1;\\(n-1)\cdot ({!(n-1)}+{!(n-2)})&n>1.\end{cases}}$
$!n=(n-1)\cdot a_{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, 1, 3, 11, 53, 309, 2119, …;

Число 148 349 является субфакторионом, то есть равно сумме субфакториалов своих цифр (аналог факториона)^[2]:

148349={!1}+{!4}+{!8}+{!3}+{!4}+{!9}

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

Примечания

↑ Последовательность A000255 в OEIS = a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]
↑ J. S. Madachy, 1979

Литература

Р. Стенли. Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2.

Последовательности и ряды
Последовательности	Числовая последовательность Фундаментальная последовательность Линейная рекуррентная последовательность Числа Фибоначчи Фигурные числа Факториал (Праймориал * Символ Похгаммера * Субфакториал) Последовательность Баркера Последовательность де Брёйна
Ряды, основное	Сумма ряда Остаток ряда Условная сходимость Знакочередующийся ряд Мультисекция ряда
Числовые ряды (действия с числовыми рядами)	Гармонический ряд Ряд Лейбница Ряд обратных квадратов Ряд обратных простых чисел Ряд Дирихле Ряд Меркатора Ряд Гранди 1 − 2 + 3 − 4 + … 1 + 2 + 3 + 4 + …
Функциональные ряды	Ряд Тейлора Ряд Лорана Ряд Фурье Тригонометрический ряд Фурье Тригонометрический ряд Ряд Винера
Другие виды рядов	Ряд Неймана Ряд Пюизё

Похожие исследовательские статьи

Факториа́л — функция, определённая на множестве неотрицательных целых чисел. Название происходит от лат. factorialis — действующий, производящий, умножающий; обозначается $\text{[math]}$ , произносится эн факториа́л. Факториал натурального числа $\text{[math]}$ определяется как произведение всех натуральных чисел от 1 до $\text{[math]}$ включительно:

\text{[math]}

В математике, целая часть вещественного числа $\text{[math]}$ — округление $\text{[math]}$ до ближайшего целого в меньшую сторону. Целая часть числа также называется антье, или пол. Наряду с полом существует парная функция — потолок — округление $\text{[math]}$ до ближайшего целого в большую сторону.

Гамма-функция — математическая функция. Была введена Леонардом Эйлером, а своим обозначением гамма-функция обязана Лежандру.

Постулат Бертрана, теорема Бертрана — Чебышёва или теорема Чебышёва гласит, что для любого натурального $\text{[math]}$ найдётся простое число $\text{[math]}$ в интервале $\text{[math]}$

Функция Мёбиуса $\text{[math]}$ — мультипликативная арифметическая функция, применяемая в теории чисел и комбинаторике, названа в честь немецкого математика Мёбиуса, который впервые рассмотрел её в 1831 году.

Постоянная Э́йлера — Маскеро́ни или постоянная Эйлера — математическая константа, определяемая как предел разности между частичной суммой гармонического ряда и натуральным логарифмом числа:

\text{[math]}

Юлиа́нская да́та (JD) — астрономический способ измерения времени, при котором считается число суток, прошедших начиная с полудня понедельника, 1 января 4713 года до н. э. пролептического юлианского календаря или, что то же самое, 24 ноября 4714 года до н. э. пролептического григорианского календаря. Первый день имел номер 0. С тех пор по настоящее время прошло немногим менее 2,5 миллиона дней. Даты сменяются в полдень UT или TT. Для точного обозначения времени применяют дробную часть, например, JD = 2451545,25 соответствует 18 часам 1 января 2000 года; 3 часа дня 2 августа 1942 года — JD 2430574,125; 13,5 июня 1944 года — JD 2431255,0.

Распределе́ние Ве́йбулла в теории вероятностей — двухпараметрическое семейство абсолютно непрерывных распределений.

Гипергеометри́ческая фу́нкция — одна из специальных функций. Определяется внутри круга $\text{[math]}$ как сумма гипергеометрического ряда

\text{[math]}

Алгоритм Лемана детерминировано раскладывает данное натуральное число $\text{[math]}$ на множители за $\text{[math]}$ арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел, имеющим оценку меньшую, чем $\text{[math]}$ . В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.

Водородоподо́бный а́том или водородоподо́бный ио́н представляет собой любое атомное ядро, которое имеет один электрон и, следовательно, является изоэлектронным атому водорода. Эти ионы несут положительный заряд $\text{[math]}$ , где $\text{[math]}$ — зарядовое число ядра. Примерами водородоподобных ионов являются He⁺, Li²⁺, Be³⁺ и B⁴⁺. Поскольку водородоподобные ионы представляют собой двухчастичные системы, взаимодействие которых зависит только от расстояния между двумя частицами, их (нерелятивистское) уравнение Шредингера и (релятивистское) уравнение Дирака имеют решения в аналитической форме. Решения являются одноэлектронными функциями и называются водородоподобными атомными орбиталями.

G-функция Барнса — функция, которая расширяет понятие суперфакториала на поле комплексных чисел. Она связана с Гамма-функцией, K-функцией и постоянной Глейшера—Кинкелина. $\text{[math]}$ -функция названа в честь английского математика Эрнеста Уильяма Барнса.

Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти.

Метод Годунова — реализация схем сквозного счета, с помощью которых можно рассчитывать газодинамические течения с разрывами параметров внутри расчётной области. Эта схема предложена С. К. Годуновым в 1959 г. Метод Годунова — это вариант метода контрольного объёма. Потоки через боковые грани определяются из решения задачи о распаде произвольного разрыва. Поясним на примере.

Многочле́ны Гегенба́уэра или ультрасфери́ческие многочле́ны в математике — многочлены, ортогональные на отрезке [−1,1] с весовой функцией $\text{[math]}$ . Они могут быть явным образом представлены как

\text{[math]}

Теорема Евклида — основной элемент теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список.

Оценка Чернова даёт экспоненциально убывающие оценки вероятности больших отклонений сумм независимых случайных величин. Эти оценки являются более точными, чем оценки, полученные с использованием первых или вторых моментов, такие как неравенство Маркова или неравенство Чебышёва, которые дают лишь степенной закон убывания. Вместе с тем оценка Чернова требует, чтобы случайные величины были независимы в совокупности — условие, которое ни неравенство Маркова, ни неравенство Чебышёва не требуют, хотя неравенство Чебышёва требует попарную независимость случайных величин.

Качающийся факториал — функция, определённая на множестве неотрицательных целых чисел $\text{[math]}$ . Обозначается $\text{[math]}$ , произносится эн качающийся факториа́л.

Алгоритм Барретта — это алгоритм приведения, который в 1986 году предложил П. Д. Барретт. Обычный способ вычисления

\text{[math]}

В информатике метод Акра–Баззи, или теорема Акра–Баззи, используется для анализа асимптотического поведения математических рекуррент, которые появляются при анализе алгоритмов «разделяй и властвуй», где подзадачи имеют существенно разные размеры. Это обобщение основной теоремы для рекуррентных уравнений «разделяй и властвуй», которая предполагает, что подзадачи имеют одинаковый размер. Он наназван в честь математиков Мохамада Акры и Луая Баззи.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.