stringtranslate.com

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

Пятнадцать различных диаграмм хорд на шести точках, или, что эквивалентно, пятнадцать различных совершенных паросочетаний на шестивершинном полном графе . Они подсчитываются двойным факториалом 15 = (6 − 1) ‼.

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

Перефразируя это, это означает, что для четных n двойной факториал [2] равен , а для нечетных n равен Например, 9‼ = 9 × 7 × 5 × 3 × 1 = 945 . Нулевой двойной факториал 0‼ = 1 как пустое произведение . [3] [4]

Последовательность двойных факториалов для четных n = 0, 2, 4, 6, 8,... начинается как

1, 2, 8, 48, 384, 3840, 46080, 645120, ... (последовательность A000165 в OEIS )

Последовательность двойных факториалов для нечетных n = 1, 3, 5, 7, 9,... начинается как

1, 3, 15, 105, 945, 10395, 135135, ... (последовательность A001147 в OEIS )

Термин нечетный факториал иногда используется для обозначения двойного факториала нечетного числа. [5] [6]

Термин «полуфакториал» также используется Кнутом как синоним двойного факториала. [7]

История и использование

В статье 1902 года физик Артур Шустер писал: [8]

Символическое представление результатов этой статьи значительно облегчается введением отдельного символа для произведения альтернативных множителей , если быть нечетным, или если быть нечетным [sic]. Я предлагаю писать для таких произведений, и если для произведения потребуется название, называть его «альтернативный факториал» или «двойной факториал».

Месерв (1948) [9] утверждает, что двойной факториал был первоначально введен для упрощения выражения некоторых тригонометрических интегралов , которые возникают при выводе произведения Уоллиса . Двойные факториалы также возникают при выражении объема гипершара и площади поверхности гиперсферы , и они имеют множество применений в перечислительной комбинаторике . [1] [10] Они встречаются в t -распределении Стьюдента (1908), хотя Госсет не использовал обозначение с двумя восклицательными знаками.

Отношение к факториалу

Поскольку двойной факториал включает в себя только около половины множителей обычного факториала , его значение ненамного больше квадратного корня факториала n !, и оно намного меньше, чем итерированный факториал ( n !) !.

Факториал положительного числа n можно записать как произведение двух двойных факториалов: [3] и, следовательно , где знаменатель отменяет нежелательные множители в числителе. (Последняя форма применима также при n = 0. )

Для четного неотрицательного целого числа n = 2k , где k ≥ 0 , двойной факториал можно выразить как

Для нечетных n = 2k 1 с k ≥ 1 объединение двух предыдущих формул дает

Для нечетного положительного целого числа n = 2k 1 с k ≥ 1 двойной факториал может быть выражен через k -перестановки 2k [1] [11] или убывающий факториал как

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

Пятнадцать различных корневых бинарных деревьев (с неупорядоченными дочерними элементами) на наборе из четырех помеченных листьев, иллюстрирующих 15 = (2 × 4 − 3)‼ (см. текст статьи).

Двойные факториалы мотивированы тем фактом, что они часто встречаются в перечислительной комбинаторике и других ситуациях. Например, n для нечетных значений n означает

Callan (2009) и Dale & Moon (1993) перечисляют несколько дополнительных объектов с той же последовательностью подсчета , включая «трапециевидные слова» ( цифры в смешанной системе счисления с увеличивающимися нечетными основаниями), пути Дика с пометкой высоты , упорядоченные деревья с пометкой высоты, «нависающие пути» и некоторые векторы, описывающие листовой потомок с наименьшим номером каждого узла в корневом бинарном дереве. Для биективных доказательств того, что некоторые из этих объектов являются равночисленными, см. Rubey (2008) и Marsh & Martin (2011). [16] [17]

Четные двойные факториалы дают число элементов гипероктаэдрических групп (знаковых перестановок или симметрий гиперкуба ) .

Асимптотика

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

Расширения

Отрицательные аргументы

Обычный факториал, будучи расширен до гамма-функции , имеет полюс на каждом отрицательном целом числе, что не позволяет определить факториал на этих числах. Однако двойной факториал нечетных чисел может быть расширен до любого отрицательного нечетного целого аргумента путем инвертирования его рекуррентного соотношения , чтобы получить Используя эту инвертированную рекуррентность, (−1)!! = 1, (−3)!! = −1 и (−5)!! =  1/3 ; отрицательные нечетные числа с большей величиной имеют дробные двойные факториалы. [1] В частности, когда n — нечетное число, это дает

Сложные аргументы

Игнорируя приведенное выше определение n !! для четных значений  n , двойной факториал для нечетных целых чисел можно распространить на большинство действительных и комплексных чисел z, заметив, что когда z является положительным нечетным целым числом, то [18] [19]

где - гамма-функция .

Окончательное выражение определено для всех комплексных чисел, за исключением отрицательных четных целых чисел, и удовлетворяет условию ( z + 2)!! = ( z + 2) · z !! везде, где оно определено. Как и в случае с гамма-функцией, которая расширяет обычную факториальную функцию, эта двойная факториальная функция является логарифмически выпуклой в смысле теоремы Бора–Моллерупа . Асимптотически,

Обобщенная формула не согласуется с предыдущей формулой произведения для z !! для неотрицательных четных целых значений  z . Вместо этого эта обобщенная формула подразумевает следующую альтернативу: со значением для 0!! в этом случае

Используя эту обобщенную формулу в качестве определения, объем n - мерной гиперсферы радиуса R можно выразить как [ 20 ]

Дополнительные идентичности

Для целых значений n , используя вместо этого расширение двойного факториала нечетных чисел до комплексных чисел, формула имеет вид

Двойные факториалы также можно использовать для вычисления интегралов более сложных тригонометрических полиномов. [9] [21]

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

Некоторые дополнительные тождества, включающие двойные факториалы нечетных чисел: [1]

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

Обобщения

Определения

Точно так же, как двойной факториал обобщает понятие простого факториала , следующее определение целочисленных множественных факториальных функций (мультифакториалов), или α -факториальных функций, расширяет понятие функции двойного факториала для положительных целых чисел :

Альтернативное расширение многофакторного

В качестве альтернативы многофакториал z ! ( α ) можно распространить на большинство действительных и комплексных чисел z, заметив, что когда z на единицу больше положительного кратного положительного целого числа α , то

Это последнее выражение определено гораздо шире, чем исходное. Точно так же, как z ! не определено для отрицательных целых чисел, а z не определено для отрицательных четных целых чисел, z ! ( α ) не определено для отрицательных кратных α . Однако оно определено и удовлетворяет ( z + α )! ( α ) = ( z + αz ! ( α ) для всех других комплексных чисел  z . Это определение согласуется с более ранним определением только для тех целых чисел z, которые удовлетворяют  z ≡ 1 mod α .

В дополнение к расширению z ! ( α ) на большинство комплексных чисел  z , это определение имеет особенность работать для всех положительных действительных значений  α . Более того, когда α = 1 , это определение математически эквивалентно функции Π( z ) , описанной выше. Также, когда α = 2 , это определение математически эквивалентно альтернативному расширению двойного факториала.

Обобщенные числа Стерлинга, расширяющие многофакторные функции

Класс обобщенных чисел Стирлинга первого рода определяется при α > 0 следующим треугольным рекуррентным соотношением:

Эти обобщенные α -факториальные коэффициенты затем генерируют различные символические полиномиальные произведения, определяющие множественные факториальные или α -факториальные функции, ( x − 1)! ( α ) , как

Различные полиномиальные разложения в предыдущих уравнениях фактически определяют α -факториальные произведения для нескольких различных случаев наименьших остатков xn 0 mod α для n 0 ∈ {0, 1, 2, ..., α − 1} .

Обобщенные α -факториальные полиномы, σ( α )
n
( х )
где σ(1)
н
( x ) ≡ σ n ( x )
, которые обобщают полиномы свертки Стирлинга с однофакторного случая на многофакторный случай, определяются как

для 0 ≤ nx . Эти многочлены имеют особенно хорошую замкнутую форму обычной производящей функции, заданной как

Другие комбинаторные свойства и расширения этих обобщенных α -факториальных треугольников и полиномиальных последовательностей рассматриваются в работе Шмидта (2010). [22]

Точные конечные суммы, включающие несколько факториальных функций

Предположим, что n ≥ 1 и α ≥ 2 являются целочисленными. Тогда мы можем разложить следующие отдельные конечные суммы, включающие многофакторные или α -факториальные функции, ( αn − 1)! ( α ) , в терминах символа Похгаммера и обобщенных рационально-значных биномиальных коэффициентов как

и более того, мы аналогично имеем двойные разложения суммы этих функций, заданные как

Первые две суммы выше по форме аналогичны известному некруглому комбинаторному тождеству для функции двойного факториала при α  := 2, данному Калланом (2009).

Похожие тождества могут быть получены с помощью контекстно-свободных грамматик. [23] Дополнительные конечные суммовые разложения сравнений для α -факториальных функций, ( αnd )! ( α ) , по модулю любого предписанного целого числа h ≥ 2 для любого 0 ≤ d < α даны Шмидтом (2018). [24]

Ссылки

  1. ^ abcdefghij Каллан, Дэвид (2009). «Комбинаторный обзор тождеств для двойного факториала». arXiv : 0906.1317 [math.CO].
  2. ^ Некоторые авторы определяют двойной факториал по-разному для четных чисел; см. Двойной факториал § комплексные аргументы ниже.
  3. ^ ab Weisstein, Eric W. "Double Factorial". mathworld.wolfram.com . Получено 10 сентября 2020 г. .
  4. ^ "Двойные факториалы и мультифакториалы | Brilliant Math & Science Wiki". brilliant.org . Получено 10.09.2020 .
  5. ^ Хендерсон, Дэниел Дж.; Парметер, Кристофер Ф. (2012). «Канонические ядра высшего порядка для оценки производной плотности». Statistics & Probability Letters . 82 (7): 1383–1387. doi :10.1016/j.spl.2012.03.013. MR  2929790.
  6. ^ Нильсен, Б. (1999). «Тест отношения правдоподобия для ранга в двумерном каноническом корреляционном анализе». Biometrika . 86 (2): 279–288. doi :10.1093/biomet/86.2.279. MR  1705359.
  7. ^ Кнут, Дональд Эрвин (2023). Искусство программирования. том 4B часть 2: Комбинаторные алгоритмы . Бостон Мюнхен: Addison-Wesley. ISBN 978-0-201-03806-4.
  8. ^ Шустер, Артур (1902). «О некоторых определенных интегралах и новом методе сведения функции сферических координат к ряду сферических гармоник». Труды Лондонского королевского общества . 71 (467–476): 97–101. doi : 10.1098/rspl.1902.0068 . JSTOR  116355.См. в частности стр. 99.
  9. ^ ab Meserve, BE (1948). «Заметки в классе: Двойные факториалы». The American Mathematical Monthly . 55 (7): 425–426. doi :10.2307/2306136. JSTOR  2306136. MR  1527019.
  10. ^ abcd Дейл, MRT; Мун, JW (1993). «Пермутированные аналоги трех каталонских множеств». Журнал статистического планирования и вывода . 34 (1): 75–87. doi :10.1016/0378-3758(93)90035-5. MR  1209991.
  11. ^ Гулд, Генри; Куэйнтанс, Джоселин (2012). «Двойное веселье с двойными факториалами». Mathematics Magazine . 85 (3): 177–192. doi :10.4169/math.mag.85.3.177. MR  2924154. S2CID  117120280.
  12. ^ Китаев, Сергей (2011). Паттерны в перестановках и словах. EATCS Monographs in Theoretical Computer Science. Springer. стр. 96. ISBN 9783642173332.
  13. ^ Дейл, МРТ; Нараяна, ТВ (1986). «Разбиение каталонских переставленных последовательностей с приложениями». Журнал статистического планирования и вывода . 14 (2): 245–249. doi :10.1016/0378-3758(86)90161-8. MR  0852528.
  14. ^ Тичи, Роберт Ф.; Вагнер, Стефан (2005). «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) . Журнал вычислительной биологии . 12 (7): 1004–1013. doi :10.1089/cmb.2005.12.1004. PMID  16201918.
  15. ^ Janson, Svante (2008). "Plane recursive trees, Stirling permutations and an urn model". Пятый коллоквиум по математике и информатике . Discrete Math. Theor. Comput. Sci. Proc., AI. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. стр. 541–547. arXiv : 0803.1129 . Bibcode :2008arXiv0803.1129J. MR  2508813.
  16. ^ Руби, Мартин (2008). «Вложенности соответствий и перестановок и северные шаги в PDSAW». 20-я ежегодная международная конференция по формальным степенным рядам и алгебраической комбинаторике (FPSAC 2008) . Discrete Math. Theor. Comput. Sci. Proc., AJ. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. стр. 691–704. MR  2721495.
  17. ^ Марш, Роберт Дж.; Мартин, Пол (2011). «Разбиение биекций между путями и диаграммами Брауэра». Журнал алгебраической комбинаторики . 33 (3): 427–453. arXiv : 0906.0912 . doi :10.1007/s10801-010-0252-6. MR  2772541. S2CID  7264692.
  18. ^ Хассани, Садри (2000). Математические методы: для студентов физики и смежных дисциплин. Бакалаврские тексты по математике . Springer. стр. 266. ISBN 9780387989587.
  19. ^ "Двойной факториал: Конкретные значения (формула 06.02.03.0005)". Wolfram Research. 2001-10-29 . Получено 2013-03-23 .
  20. ^ Mezey, Paul G. (2009). «Некоторые проблемы размерности в молекулярных базах данных». Журнал математической химии . 45 (1): 1–6. doi :10.1007/s10910-008-9365-8. S2CID  120103389.
  21. ^ Дассиос, Джордж ; Кириаки, Кириаки (1987). «Полезное применение теоремы Гаусса». Бюллетень математического общества Греции . 28 (А): 40–43. МР  0935868.
  22. ^ Шмидт, Макси Д. (2010). «Обобщенные j-факториальные функции, полиномы и приложения». J. Integer Seq . 13 .
  23. ^ Триана, Хуан; Де Кастро, Родриго (2019). «Формальный оператор производной и многофакторные числа». Revista Colombiana de Matematicas . 53 (2): 125–137. дои : 10.15446/recolma.v53n2.85522 . ISSN  0034-7426.
  24. ^ Шмидт, Макси Д. (2018). «Новые сравнения и уравнения конечных разностей для обобщенных факториальных функций» (PDF) . Целые числа . 18 : A78:1–A78:34. arXiv : 1701.04741 . MR  3862591.