В математике двойной факториал числа 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,... начинается как
Символическое представление результатов этой статьи значительно облегчается введением отдельного символа для произведения альтернативных множителей , если быть нечетным, или если быть нечетным [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] или убывающий факториал как
Приложения в перечислительной комбинаторике
Двойные факториалы мотивированы тем фактом, что они часто встречаются в перечислительной комбинаторике и других ситуациях. Например, n ‼ для нечетных значений n означает
Идеальные паросочетания полного графа K n + 1 для нечетного n . В таком графе любая вершина v имеет n возможных вариантов вершины, с которой она может быть сопоставлена, и как только этот выбор сделан, оставшаяся проблема заключается в выборе идеального паросочетания в полном графе с двумя вершинами меньше. Например, полный граф с четырьмя вершинами a , b , c , и d имеет три идеальных паросочетания: ab и cd , ac и bd , и ad и bc . [1] Идеальные паросочетания можно описать несколькими другими эквивалентными способами, включая инволюции без неподвижных точек на множестве из n + 1 элементов ( перестановки , в которых каждый цикл является парой) [1] или диаграммы хорд (наборы хорд множества из n + 1 точек, равномерно расположенных на окружности таким образом, что каждая точка является конечной точкой ровно одной хорды, также называемые диаграммами Брауэра ). [10] [12] [13] Числа совпадений в полных графах, без ограничения соответствия идеальными, вместо этого задаются телефонными номерами , которые могут быть выражены как сумма с использованием двойных факториалов. [14]
Перестановки Стерлинга , перестановки мультимножества чисел 1 , 1, 2, 2, ..., k , k, в которых каждая пара равных чисел разделена только большими числами, где k = н + 1/2 . Две копии k должны быть смежными; удаление их из перестановки оставляет перестановку, в которой максимальный элемент равен k − 1 , с n позициями, в которые может быть помещена смежная пара значений k . Из этой рекурсивной конструкции доказательство того, что перестановки Стирлинга подсчитываются двойными перестановками, следует по индукции. [1] В качестве альтернативы, вместо ограничения, что значения между парой могут быть больше, чем она, можно также рассмотреть перестановки этого мультимножества, в котором первые копии каждой пары появляются в отсортированном порядке; такая перестановка определяет соответствие на 2 k позициях перестановки, поэтому снова количество перестановок может быть подсчитано двойными перестановками. [10]
Heap-ordered trees , деревья с k + 1 узлами, помеченными 0, 1, 2, ... k , такие, что корень дерева имеет метку 0, каждый другой узел имеет большую метку, чем его родительский узел, и такие, что потомки каждого узла имеют фиксированный порядок. Эйлеров обход дерева (с двойными ребрами) дает перестановку Стирлинга, и каждая перестановка Стирлинга представляет дерево таким образом. [1] [15]
Некорневые бинарные деревья с н + 5/2 помеченные листья. Каждое такое дерево может быть сформировано из дерева с одним листом меньше, путем разделения одного из n ребер дерева и превращения новой вершины в родительскую для нового листа.
Корневые бинарные деревья с н + 3/2 помеченные листья. Этот случай похож на случай без корня, но количество ребер, которые могут быть разделены, четное, и в дополнение к разделению ребра можно добавить узел к дереву с одним листом меньше, добавив новый корень, двумя дочерними элементами которого являются меньшее дерево и новый лист. [1] [10]
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 ,
используя вместо этого расширение двойного факториала нечетных чисел до комплексных чисел, формула имеет вид
Двойные факториалы также можно использовать для вычисления интегралов более сложных тригонометрических полиномов. [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)! ( α ) , как
Различные полиномиальные разложения в предыдущих уравнениях фактически определяют α -факториальные произведения для нескольких различных случаев наименьших остатков x ≡ n 0 mod α для n 0 ∈ {0, 1, 2, ..., α − 1} .
Обобщенные α -факториальные полиномы, σ( α ) n( х ) где σ(1) н( x ) ≡ σ n ( x ) , которые обобщают полиномы свертки Стирлинга с однофакторного случая на многофакторный случай, определяются как
Другие комбинаторные свойства и расширения этих обобщенных α -факториальных треугольников и полиномиальных последовательностей рассматриваются в работе Шмидта (2010). [22]
Точные конечные суммы, включающие несколько факториальных функций
Предположим, что n ≥ 1 и α ≥ 2 являются целочисленными. Тогда мы можем разложить следующие отдельные конечные суммы, включающие многофакторные или α -факториальные функции, ( αn − 1)! ( α ) , в терминах символа Похгаммера и обобщенных рационально-значных биномиальных коэффициентов как
и более того, мы аналогично имеем двойные разложения суммы этих функций, заданные как
Первые две суммы выше по форме аналогичны известному некруглому комбинаторному тождеству для функции двойного факториала при α := 2, данному Калланом (2009).
Похожие тождества могут быть получены с помощью контекстно-свободных грамматик. [23] Дополнительные конечные суммовые разложения сравнений для α -факториальных функций, ( αn − d )! ( α ) , по модулю любого предписанного целого числа h ≥ 2 для любого 0 ≤ d < α даны Шмидтом (2018). [24]
Ссылки
^ abcdefghij Каллан, Дэвид (2009). «Комбинаторный обзор тождеств для двойного факториала». arXiv : 0906.1317 [math.CO].
^ Некоторые авторы определяют двойной факториал по-разному для четных чисел; см. Двойной факториал § комплексные аргументы ниже.
^ ab Weisstein, Eric W. "Double Factorial". mathworld.wolfram.com . Получено 10 сентября 2020 г. .
^ "Двойные факториалы и мультифакториалы | Brilliant Math & Science Wiki". brilliant.org . Получено 10.09.2020 .
^ Хендерсон, Дэниел Дж.; Парметер, Кристофер Ф. (2012). «Канонические ядра высшего порядка для оценки производной плотности». Statistics & Probability Letters . 82 (7): 1383–1387. doi :10.1016/j.spl.2012.03.013. MR 2929790.
^ Нильсен, Б. (1999). «Тест отношения правдоподобия для ранга в двумерном каноническом корреляционном анализе». Biometrika . 86 (2): 279–288. doi :10.1093/biomet/86.2.279. MR 1705359.
^ Кнут, Дональд Эрвин (2023). Искусство программирования. том 4B часть 2: Комбинаторные алгоритмы . Бостон Мюнхен: Addison-Wesley. ISBN978-0-201-03806-4.
^ Шустер, Артур (1902). «О некоторых определенных интегралах и новом методе сведения функции сферических координат к ряду сферических гармоник». Труды Лондонского королевского общества . 71 (467–476): 97–101. doi : 10.1098/rspl.1902.0068 . JSTOR 116355.См. в частности стр. 99.
^ ab Meserve, BE (1948). «Заметки в классе: Двойные факториалы». The American Mathematical Monthly . 55 (7): 425–426. doi :10.2307/2306136. JSTOR 2306136. MR 1527019.
^ abcd Дейл, MRT; Мун, JW (1993). «Пермутированные аналоги трех каталонских множеств». Журнал статистического планирования и вывода . 34 (1): 75–87. doi :10.1016/0378-3758(93)90035-5. MR 1209991.
^ Китаев, Сергей (2011). Паттерны в перестановках и словах. EATCS Monographs in Theoretical Computer Science. Springer. стр. 96. ISBN9783642173332.
^ Дейл, МРТ; Нараяна, ТВ (1986). «Разбиение каталонских переставленных последовательностей с приложениями». Журнал статистического планирования и вывода . 14 (2): 245–249. doi :10.1016/0378-3758(86)90161-8. MR 0852528.
^ Тичи, Роберт Ф.; Вагнер, Стефан (2005). «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) . Журнал вычислительной биологии . 12 (7): 1004–1013. doi :10.1089/cmb.2005.12.1004. PMID 16201918.
^ Mezey, Paul G. (2009). «Некоторые проблемы размерности в молекулярных базах данных». Журнал математической химии . 45 (1): 1–6. doi :10.1007/s10910-008-9365-8. S2CID 120103389.
^ Дассиос, Джордж ; Кириаки, Кириаки (1987). «Полезное применение теоремы Гаусса». Бюллетень математического общества Греции . 28 (А): 40–43. МР 0935868.
^ Шмидт, Макси Д. (2010). «Обобщенные j-факториальные функции, полиномы и приложения». J. Integer Seq . 13 .
^ Триана, Хуан; Де Кастро, Родриго (2019). «Формальный оператор производной и многофакторные числа». Revista Colombiana de Matematicas . 53 (2): 125–137. дои : 10.15446/recolma.v53n2.85522 . ISSN 0034-7426.
^ Шмидт, Макси Д. (2018). «Новые сравнения и уравнения конечных разностей для обобщенных факториальных функций» (PDF) . Целые числа . 18 : A78:1–A78:34. arXiv : 1701.04741 . MR 3862591.