Что такое субфакториал в математике
Субфакториал
Субфакториал числа n (обозначение: !n) определяется как количество беспорядков порядка n, то есть перестановок порядка n без неподвижных точек. Название субфакториал происходит из аналогии с факториалом, определяющим общее количество перестановок.
В частности, !n есть число способов положить n писем в n конвертов (по одному в каждый), чтобы ни одно не попало в соответствующий конверт (т. н. Задача о письмах).
Содержание
Явная формула
Субфакториал можно вычислить с помощью принципа включения-исключения:
Другие формулы
Таблица значений
Свойства
Полезное
Смотреть что такое «Субфакториал» в других словарях:
Факториал — числа n (лат. factorialis действующий, производящий умножающий; обозначается n!, произносится эн факториал) произведение всех натуральных чисел от 1 до n включительно … Википедия
Число Стирлинга первого рода — Числа Стирлинга первого рода количество перестановок из n предметов, имеющие ровно k циклов. Содержание 1 Определение 2 Рекуррентное соотношение 3 Пример 4 Свойст … Википедия
Числа Стирлинга первого рода — (без знака) количество перестановок порядка n с k циклами. Содержание 1 Определение 2 Рекуррентное соотношение 3 … Википедия
Четыре четвёрки — Четыре четверки математическая головоломка по поиску простейшего математического выражения для каждого целого числа от 0 до некоторого максимума, используя лишь общие математические символы и цифры четыре (никакие другие цифры не допускаются).… … Википедия
Приветствую Вас, уважаемые Читатели! Сегодня хочу рассказать вам об одной математической операции, название которой кажется до боли знакомым, да и обозначение «!n» также никак не уводит в сторону от известного всем факториала n! = 1*2*3*…*n. Однако, у субфакториала есть свои особенности, да и смысл его использования в комбинаторике совсем другой. Посмотрим подробнее. Поехали!
Николай Ьернулли — именно он впервые рассмотрел субфакториал. Источник: https://famous-mathematicians.com/images/swiss-mathematicians/nicolaus-bernoulli.jpg
Итак, если факториал определяет количество перестановок, возможных в наборе из n объектов, то субфакториал характеризует количество беспорядков в таком же наборе. Проще всего понять, что такое факториал на жизненном примере. Возьмем некоторое количество писем и конвертов и пронумеруем их:
Теперь наша задача в том, чтобы создать максимальный беспорядок, а именно сделать так, чтобы каждое письмо оказалось не в том конверте, для которого предназначено. На рисунке я показал один из способов такого распределения.
Вы уже, наверное, догадались, что именно субфакториал определит количество таких возможных перестановок, в комбинаторике называемых смещениями.
Формула для вычисления субфакториала сложностью не отличается:
Формула была выведена Николаем Бернулли еще в 1713 году.
Значит, в наборе из 4 писем есть 9 вариантов навести тотальный хаос!
Еще одна интерпретация задачи: профессор дал тест 4 студентам – 1, 2, 3 и 4 – и хочет, чтобы они оценили тесты друг друга. Конечно, ни один студент не должен оценивать свой собственный тест. Сколько существует способов, чтобы никто не получил обратно свой собственный тест для проверки?
Видно, что таких случаев 9, как и должно быть по формуле.Источник: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f1/Derangement4.png/800px-Derangement4.png
Судя по формуле, субфакториал всегда меньше факториала, ведь в скобках величина всегда меньшая, чем 1/2 для n>3. Поразительно, но факториал и субфакторила лаконично связаны через постоянную Эйлера, и это действительно очень красиво:
Просто вычисляем ближайшее целое число к полученному результату
Ну и напоследок еще одно феноменальное совпадение — единственное известное математикам число-субфакторион:
Спасибо за внимание! Не переставайте узнавать новое и тянуться к знаниям, даже если в этом нет сиюминутной практической пользы.
Субфакториал в математике, понятие и применение кратко
субфакториал числа n (обозначение: !n) определяется как количество беспорядков порядка n, то есть перестановок порядка n без неподвижных точек. Название субфакториал происходит из аналогии с факториалом, определяющим общее количество перестановок.
В частности, !n есть число способов положить n писем в n конвертов (по одному в каждый), чтобы ни одно не попало в соответствующий конверт (т. н. Задача о письмах).
Явная формула
Субфакториал можно вычислить с помощью принципа включения-исключения:
Другие формулы
Таблица значений
!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
последовательность A000166 в OEIS
Свойства субфакториала
1, 1, 3, 11, 53, 309, 2119, … (последовательность A000255 в OEIS)
(найдено J. S. Madachy, 1979)
Применение субфакториала
Итак, если факториал определяет количество перестановок, возможных в наборе из n объектов, то субфакториал характеризует количество беспорядков в таком же наборе. Проще всего понять, что такое факториал на жизненном примере. Возьмем некоторое количество писем и конвертов и пронумеруем их:
Вы уже, наверное, догадались, что именно субфакториал определит количество таких возможных перестановок, в комбинаторике называемых смещениями.
Формула для вычисления субфакториала сложностью не отличается:
Формула была выведена Николаем Бернулли еще в 1713 году.
Еще одна интерпретация задачи: профессор дал тест 4 студентам – 1, 2, 3 и 4 – и хочет, чтобы они оценили тесты друг друга. Конечно, ни один студент не должен оценивать свой собственный тест. Сколько существует способов, чтобы никто не получил обратно свой собственный тест для проверки?
Видно, что таких случаев 9, как и должно быть по формуле.Источник: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f1/Derangement4.png/800px-Derangement4.png
Судя по формуле, субфакториал всегда меньше факториала, ведь в скобках величина всегда меньшая, чем 1/2 для n>3. Поразительно, но факториал и субфакторила лаконично связаны через постоянную Эйлера, и это действительно очень красиво:
Просто вычисляем ближайшее целое число к полученному результату
См. также
Из статьи мы узнали кратко, но емко про субфакториал
Факториал числа n – это произведение чисел от 1 до n. Определён только для целых неотрицательных чисел. Формула факториала:
Математическая формула представлена восклицательным знаком «!». Термин был введен в 1800 году, а обозначение появилось только в 1808. В формуле нужно умножить все целые числа от 1 до значения самого числа, стоящего под знаком факториала.
Это очень просто, вот пример:
Таблица факториалов
Свойства факториалов
Рекуррентная формула
Комбинаторная интерпретация
Функция n может интерпретироваться как количество перестановок. К примеру, для 3-х элементов есть 3! = 6 перестановки.
Формула Стирлинга
Позволяет не перемножать большие числа. Обычно необходим только главный член:
Расчет по предыдущему значению
Функцию легко вычислить из предыдущего значения:
А как вычислить факториал нуля? Если вернуться к определению, то видно, что применять его в случае «0» нет смысла. Положительных чисел до 0 нет, поэтому 0 x 0 = 0.
Однако было решено, что в случае 0 результат будет равен 1.
Некоторые очень большие значения
Онлайн калькулятор поможет сделать вычисление – всего лишь надо найти знак, похожий на «x!» или «n!». Нужно обратить внимание, что браузеры могут испытывать затруднения при попытке отобразить более крупные числа и может произойти сбой.
Некоторые браузеры могут не позволять копировать, поэтому необходимо будет загрузить большие результаты в виде текстового файла.
Примеры вычисления факториалов больших чисел:
70! приблизительно 1 19785716669969869891796072783721 x 10100, что немного больше, чем «гуголь» (1 и 100 нулей);
100! это примерно 9 33262154444944152681699238856 x 101576 x 10157;
200! это примерно 7 88657867867364479050355236321393 x 103743.
Как найти функцию в Паскаль? Вычисление легко реализуется на разных языках программирования. Можно выбрать два метода: итеративный, то есть он создает цикл, в котором временная переменная умножается на каждое натуральное число от 1 до n, или рекурсивный, в котором функция вызывает себя до достижения базового варианта 0! = 1.
Программа на языке Паскаль:
На языке Си вычисления делаются с помощью рекурсивной функции. Следует заметить, что если начать вычислять факториал отрицательного числа в неаккуратно написанной функции, то это приведет к зацикливанию.
Факториал
По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел.
Последовательность факториалов неотрицательных целых чисел начинается так:
1, 1, 2, 6, 24, 120, 720, 5040, 40 320, 362 880, 3 628 800, 39 916 800, 479 001 600, 6 227 020 800, 87 178 291 200, 1 307 674 368 000, 20 922 789 888 000, 355 687 428 096 000, 6 402 373 705 728 000, 121 645 100 408 832 000, 2 432 902 008 176 640 000, … (последовательность A000142 в OEIS)
Факториал является чрезвычайно быстро растущей функцией. Он растёт быстрее, чем многочлен любой степени, и быстрее, чем экспоненциальная функция (но медленнее, чем двойная экспоненциальная функция 
).
Содержание
Свойства
Рекуррентная формула
Комбинаторная интерпретация
В комбинаторике факториал натурального числа n интерпретируется как количество перестановок (упорядочиваний) множества из n элементов. Например, для множества <A,B,C,D> из 4-х элементов существует 4! = 24 перестановки:
Комбинаторная интерпретация факториала служит обоснованием тождества 0! = 1, т. к. пустое множество упорядочено единственным способом.
Связь с гамма-функцией
Факториал связан с гамма-функцией от целочисленного аргумента соотношением:
Таким образом, гамма-функцию рассматривают как обобщение факториала для положительных вещественных чисел.
Путём аналитического продолжения её также расширяют и на всю комплексную плоскость, исключая особые точки при 
Более непосредственным обобщением факториала на множество вещественных (и комплексных) чисел является пи-функция, определяемая как
Поскольку 
то пи-функция натурального числа совпадает с его факториалом: 
Как факториал, пи-функция удовлетворяет рекурсивному соотношению 
Формула Стирлинга
см. O-большое. Коэффициенты этого разложения дают последовательность A001163 в OEIS (числители) и последовательность A001164 в OEIS (знаменатели).
Во многих случаях для приближённого значения факториала достаточно рассматривать только главный член формулы Стирлинга:
При этом можно утверждать, что
Формула Стирлинга позволяет получить приближённые значения факториалов больших чисел без непосредственного перемножения последовательности натуральных чисел. Так, с помощью формулы Стирлинга легко подсчитать, что
Разложение на простые числа
Каждое простое число p входит в разложение n! на простые множители в степени
Другие свойства
Обобщения
Двойной факториал
По определению полагают 0!! = 1.
Последовательность значений n!! начинается так:
1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, 10 395, 46 080, 135 135, 645 120, 2 027 025, 10 321 920, 34 459 425, 185 794 560, 654 729 075, 3 715 891 200, 13 749 310 575, 81 749 606 400, 316 234 143 225, 1 961 990 553 600, 7 905 853 580 625, 51 011 754 393 600, … (последовательность A006882 в OEIS).
Кратный факториал
Пусть число n представимо в виде 
где 
Тогда [1]
Кратный факториал связан с гамма-функцией следующим соотношением [2] :
Убывающий факториал
Убывающим факториалом (или неполным факториалом) называется выражение
Возрастающий факториал
Возрастающим факториалом называется выражение
Праймориал или примориал
Праймориал или примориал (англ. primorial ) числа n обозначается n# и определяется как произведение всех простых чисел, не превышающих n. Например,
11# = 12# = 2 · 3 · 5 · 7 · 11 = 2310.
Последовательность праймориалов (включая 
) начинается так:
1, 2, 6, 30, 210, 2310, 30 030, 510 510, 9 699 690, 223 092 870, 6 469 693 230, 200 560 490 130, 7 420 738 134 810, 304 250 263 527 210, 13 082 761 331 670 030, 614 889 782 588 491 410, 32 589 158 477 190 044 730, 1 922 760 350 154 212 639 070, … (последовательность A002110 в OEIS).
Суперфакториалы
Нейл Слоан и Саймон Плоуф (англ.) в 1995 году определили суперфакториал как произведение первых n факториалов. Согласно этому определению, суперфакториал четырёх равен
(поскольку устоявшегося обозначения нет, используется функциональное).
Последовательность суперфакториалов чисел n⩾0 начинается так:
1, 1, 2, 12, 288, 34 560, 24 883 200, … (последовательность A000178 в OEIS).
Идея была обобщена в 2000 году Генри Боттомли (англ.), что привело к гиперфакториалам (англ. Superduperfactorial ), которые являются произведением первых n суперфакториалов. Последовательность гиперфакториалов чисел n⩾0 начинается так:
1, 1, 2, 24, 6912, 238 878 720, 5 944 066 965 504 000, 125 411 328 000, 5 056 584 744 960 000, 1 834 933 472 251 084 800 000, 6 658 606 584 104 736 522 240 000 000, 265 790 267 296 391 946 810 949 632 000 000 000, 127 313 963 299 399 416 749 559 771 247 411 200 000 000 000 … (последовательность A055462 в OEIS)
где 
для 
0″ border=»0″ /> и 
Субфакториал
Ссылки
См. также
Примечания
Полезное
Смотреть что такое «Факториал» в других словарях:
ФАКТОРИАЛ — [англ. factorial Словарь иностранных слов русского языка
ФАКТОРИАЛ — (обозначение «!»), число, получаемое в результате умножения данного числа на все целые числа меньше него. Например, факториал числа 6 равен 6!=6.5.4.3.2.1=720. Факториалом нуля считают 0!=1 … Научно-технический энциклопедический словарь
ФАКТОРИАЛ — (от латинского factor деятель, создатель, множитель), произведение натуральных чисел от единицы до какого либо данного натурального числа n, т.е. 1?2. n; обозначается n! … Современная энциклопедия
факториал — сущ., кол во синонимов: 1 • термин (18) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов
Факториал — (от латинского factor деятель, создатель, множитель), произведение натуральных чисел от единицы до какого либо данного натурального числа n, т.е. 1´2´. ´n; обозначается n!. … Иллюстрированный энциклопедический словарь
ФАКТОРИАЛ — произведение всех натуральных чисел от 1 до данного натурального числа n; обозначается n! = 1·2·3·. ·n; по определению, 0! = 1 … Большая политехническая энциклопедия
факториал — произведение натуральных чисел от единицы до какого либо данного натурального числа n, то есть 1·2·3·. ·n; обозначается: n!. Например, 5! = 1·2·3·4·5 = 120. * * * ФАКТОРИАЛ ФАКТОРИАЛ, произведение натуральных чисел от единицы до какого либо… … Энциклопедический словарь
факториал — faktorialas statusas T sritis fizika atitikmenys: angl. factorial vok. Faktorielle, f; Fakultät, f rus. факториал, m pranc. factorielle, f … Fizikos terminų žodynas