Что такое двойной факториал

В комбинаторике факториал определяется как количество перестановок множества из n элементов. Например, элементы множества <A,B,C,D> можно линейно упорядочить 4!=24 способами:

Связь с гамма-функцией

Факториал связан с гамма-функцией от целочисленного аргумента соотношением:

Таким образом, гамма-функцию рассматривают как обобщение факториала для положительных вещественных чисел. Путём аналитического продолжения её также расширяют и на всю комплексную плоскость, исключая особые точки при .

Формула Стирлинга

Формула Стирлинга — асимптотическая формула для вычисления факториала:

см. O-большое. Коэффициенты этого разложения дают последовательность A001163 в OEIS (числители) и последовательность A001164 в OEIS (знаменатели).

Во многих случаях для приближенного значения факториала достаточно рассматривать только главный член формулы Стирлинга:

При этом можно утверждать, что

Разложение на простые числа

Каждое простое число p входит в разложение n! на простые в степени

,

где произведение берется по всем простым числам.

Другие свойства

• x! 2 >xx >x! > = x , при x>1

Обобщения

Двойной факториал

Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n. Таким образом,

По определению полагают 0!! = 1 .

Убывающий факториал

Убывающим факториалом (или неполным факториалом) называется выражение

Убывающий факториал дает число размещений из n по k.

Возрастающий факториал

Возрастающим факториалом называется выражение

Праймориал или примориал

Примориал (англ. Primorial ) числа n обозначается n# и определяется как произведение простых чисел, не превышающих n. Например,

Последовательность праймориалов начинается так:

2, 6, 30, 210, 2310, 30030, 510510, 9699690, … (последовательность A002110 в OEIS)

Суперфакториалы

Нейл Слоан и Саймон Плоуф (англ.) в 1995 году определили суперфакториал как произведение первых n факториалов. Согласно этому определению суперфакториал четырёх равен (поскольку устоявшегося обозначения нет, используется функциональное)

Последовательность суперфакториалов начинается (с n = 0 ) с

1, 1, 2, 12, 288, 34560, 24883200, … (последовательность A000178 в OEIS)

Идея была обобщена в 2000 Генри Боттомли (англ.), что привело к гиперфакториалам (англ. Super-duper-factorial ), которые являются произведением первых n суперфакториалов. Первые члены (с n = 0 ) равны:

1, 1, 2, 24, 6912, 238878720, 5944066965504000, … (последовательность A055462 в OEIS)

Продолжая рекуррентно, можно определить факториал кратного уровня, где m-уровневый факториал n — произведение первых n (m − 1) -уровневых факториалов, то есть

где для n > 0 и .

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

Субфакториал определяется как количество беспорядков порядка , то есть перестановок -элементного множества без неподвижных точек.

Ссылки

См. также

Wikimedia Foundation . 2010 .

Смотреть что такое "Двойной факториал" в других словарях:

Факториал — числа n (лат. factorialis действующий, производящий умножающий; обозначается n!, произносится эн факториал) произведение всех натуральных чисел от 1 до n включительно … Википедия

Двойной крестик — Одинарный и двойной крестики разными шрифтами Типографский крестик (†, в Юникоде U+2020, в dagger;), иногда его называют «кинжалом», «обелиском», «даггером», типографический знак. Двойной крестик (‡, в Юникоде U+2021, в Dagger;) вариант «кинжала… … Википедия

Праймориал — Факториал числа n (обозначается n!, произносится эн факториал) произведение всех натуральных чисел до n включительно: . По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел. Эта функция часто используется в… … Википедия

Примориал — Факториал числа n (обозначается n!, произносится эн факториал) произведение всех натуральных чисел до n включительно: . По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел. Эта функция часто используется в… … Википедия

Восклицательный знак — ! Именно так должен выглядеть этот символ Юникод U+00 … Википедия

Список интегралов от экспоненциальных функций — Ниже приведён список интегралов (первообразных функций) от экспоненциальной функции. Для более полного списка интегралов смотрите таблицу интегралов и другие списки интегралов. Заметим, что везде опущена аддитивная константа интегрирования. для … Википедия

Гиперсфера — Стереографическая проекция поверхности 3 сферы на трёхмерное пространство. На рисунке изображены три координатных направления на 3 сфере: параллели (красный), меридианы (синий) и гипермеридианы (зелёный). В исход … Википедия

Эллиптический интеграл — В интегральном исчислении, эллиптический интеграл появился в связи с задачей вычисления длины дуги эллипса и был впервые исследован Джулио Фаньяно и Леонардом Эйлером. В современном представлении, эллиптический интеграл это некоторая… … Википедия

Tcl — Запрос «TCL» перенаправляется сюда; о минидистрибутиве Linux см. Tiny Core Linux. Tcl Семантика: императивный … Википедия

TCL — Семантика: императивный, скриптовый Тип исполнения: интерпретатор Появился в: 1988 г. Автор(ы): Джон Остераут Последняя версия: 8.5.7 / 15 апреля 2009 … Википедия

Двойной факториал неотрицательного целого числа n является произведением всех целых чисел от 1 до n, имеющих одинаковую четность (нечетную или четную) с n. Это также называется полуфакториалом числа и обозначается как !! , Например, двойной факториал 9 равен 9 * 7 * 5 * 3 * 1, что составляет 945. Обратите внимание, что следствием этого определения является 0 !! = 1

Примеры:

Для четного n двойной факториал равен:

Для нечетного n двойной факториал равен:

Рекомендуется: Пожалуйста, сначала попробуйте подход , прежде чем переходить к решению.

Рекурсивное решение:
Двойной факториал можно рассчитать по следующей рекурсивной формуле.

Ниже приводится реализация двойного факториала.

ссылка на сайт
brightness_4
= "edit-on- > код

Джава

ссылка на сайт
brightness_4
код

python3

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

Итеративное решение:
Двойной факториал также может быть вычислен итеративно, поскольку рекурсия может быть дорогостоящей для больших чисел.

ссылка на сайт
brightness_4
код

Джава

ссылка на сайт
brightness_4
код

python3

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

ссылка на сайт
brightness_4
код

Временная сложность указанных решений составляет O (n).

Важные моменты :

1. Двойной факториал и факториал связаны с использованием приведенной ниже формулы.
2. Двойной факториал часто используется в комбинаторике. Обратитесь к вики для получения списка приложений. Примером приложения является подсчет совершенных совпадений полного графа K _{n + 1} для нечетного n.

Эта статья предоставлена Рахул Агравал . Если вы хотите GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел до n включительно:

.

По определению полагают . Факториал определён только для целых неотрицательных чисел.

Последовательность факториалов неотрицательных целых чисел начинается так:

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, … (последовательность A000142 в OEIS)

Содержание

Свойства

Рекуррентная формула

Комбинаторная интерпретация

В комбинаторике факториал натурального числа n интерпретируется как количество перестановок (упорядочиваний) множества из n элементов. Например, для множества <A,B,C,D> из 4-х элементов существует 4! = 24 перестановки:

Комбинаторная интерпретация факториала служит обоснованием тождества 0! = 1, т. к. пустое множество упорядочено единственным способом.

Связь с гамма-функцией

Факториал связан с гамма-функцией от целочисленного аргумента соотношением:

Таким образом, гамма-функцию рассматривают как обобщение факториала для положительных вещественных чисел.

Путём аналитического продолжения её также расширяют и на всю комплексную плоскость, исключая особые точки при .

Формула Стирлинга

см. O-большое. Коэффициенты этого разложения дают последовательность A001163 в OEIS (числители) и последовательность A001164 в OEIS (знаменатели).

Во многих случаях для приближённого значения факториала достаточно рассматривать только главный член формулы Стирлинга:

При этом можно утверждать, что

Разложение на простые числа

Каждое простое число p входит в разложение на простые множители в степени

где произведение берётся по всем простым числам. Нетрудно видеть, что для всякого простого p большего n соответствующий множитель в произведении равен 1, а потому произведение можно брать лишь по простым p, не превосходящим n.

Другие свойства

• Для натурального числа n

Обобщения

Двойной факториал

Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n. Таким образом,

По определению полагают .

Последовательность значений n!! начинается так:

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, … (последовательность A006882 в OEIS)

Кратный факториал

m-кратный факториал числа n обозначается и определяется следующим образом:

Пусть число n представимо в виде , где , . Тогда [1]

Двойной факториал является частным случаем m-кратного факториала для m = 2.

Связь с гамма-функцией

Убывающий факториал

Убывающим факториалом (или неполным факториалом) называется выражение

Убывающий факториал даёт число размещений из n по k.

Возрастающий факториал

Возрастающим факториалом называется выражение

Праймориал или примориал

Праймориал или примориал (англ. primorial ) числа n обозначается n# и определяется как произведение простых чисел, не превышающих n. Например,

Последовательность праймориалов (включая ) начинается так:

1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, … (последовательность A002110 в OEIS)

Суперфакториалы

Нейл Слоан и Саймон Плоуф (англ.) в 1995 году определили суперфакториал как произведение первых факториалов. Согласно этому определению суперфакториал четырёх равен (поскольку устоявшегося обозначения нет, используется функциональное)

Последовательность суперфакториалов чисел n⩾0 начинается так:

1, 1, 2, 12, 288, 34560, 24883200, … (последовательность A000178 в OEIS)

Идея была обобщена в 2000 году Генри Боттомли (англ.), что привело к гиперфакториалам (англ. Super-duper-factorial ), которые являются произведением первых n суперфакториалов. Последовательность гиперфакториалов чисел n⩾0 начинается так:

1, 1, 2, 24, 6912, 238878720, 5944066965504000, … (последовательность A055462 в OEIS)

Продолжая рекуррентно, можно определить факториал кратного уровня, где m-уровневый факториал числа n как произведение первых n (m-1)-уровневых факториалов, то есть

где для 0" src="http://bin.sensegates.com/s/3/a/1/3a17f57d9af78403b7ac2dd5f82c2d3c.png" /> и .

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

Субфакториал определяется как количество беспорядков порядка , то есть перестановок -элементного множества без неподвижных точек.