WikiDer > Полиномы Белла

Bell polynomials

В комбинаторный математика, то Полиномы Белла, названный в честь Эрик Темпл Белл, используются при изучении множества разделов. Они связаны с Стирлинг и Номера звонков. Они также встречаются во многих приложениях, например, в Формула Фаа ди Бруно.

Полиномы Белла

Экспоненциальные полиномы Белла

В частичный или же неполный экспоненциальные полиномы Белла являются треугольная решетка многочленов, заданных

где сумма берется по всем последовательностям j1, j2, j3, ..., jпk+1 неотрицательных целых чисел, при которых выполняются эти два условия:

Сумма

называется пth полный экспоненциальный полином Белла.

Обыкновенные полиномы Белла

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

где сумма пробегает все последовательности j1, j2, j3, ..., jпk+1 неотрицательных целых чисел, таких что

Обычные многочлены Белла могут быть выражены через экспоненциальные многочлены Белла:

В общем, многочлен Белла относится к экспоненциальному многочлену Белла, если явно не указано иное.

Комбинаторное значение

Экспоненциальный полином Белла кодирует информацию, относящуюся к способам разделения множества. Например, если мы рассмотрим набор {A, B, C}, его можно разделить на два непустых, неперекрывающихся подмножества, которые также называются частями или блоками, тремя разными способами:

{{A}, {B, C}}
{{B}, {A, C}}
{{C}, {B, A}}

Таким образом, мы можем закодировать информацию об этих разделах как

Здесь индексы B3,2 сообщает нам, что мы рассматриваем разбиение набора из 3 элементов на 2 блока. Нижний индекс каждого Икся указывает на наличие блока с я элементы (или блок размера я) в данном разделе. Так вот, Икс2 указывает на наличие блока с двумя элементами. По аналогии, Икс1 указывает на наличие блока с одним элементом. Показатель Иксяj указывает, что есть j такие блоки размера я в одном разделе. Здесь, поскольку оба Икс1 и Икс2 имеет экспоненту 1, это означает, что в данном разделе есть только один такой блок. Коэффициент одночлен указывает, сколько существует таких разделов. В нашем случае есть 3 раздела набора из 3 элементов на 2 блока, где в каждом разделе элементы разделены на два блока размером 1 и 2.

Поскольку любой набор можно разделить на единый блок только одним способом, приведенная выше интерпретация будет означать, что Bп,1 = Иксп. Точно так же, поскольку существует только один способ, которым набор с п элементы можно разделить на п синглтоны Bп,п = Икс1п.

В качестве более сложного примера рассмотрим

Это говорит нам о том, что если набор из 6 элементов разделен на 2 блока, то у нас может быть 6 разделов с блоками размера 1 и 5, 15 разделов с блоками размера 4 и 2 и 10 разделов с 2 блоками размера 3.

Сумма индексов в одночленах равна общему количеству элементов. Таким образом, количество одночленов, которые входят в частичный многочлен Белла, равно количеству способов, которыми целое число п можно выразить как сумму k положительные целые числа. Это то же самое, что и целочисленный раздел из п в k части. Например, в приведенных выше примерах целое число 3 можно разделить на две части только как 2 + 1. Таким образом, имеется только один моном в B3,2. Однако целое число 6 можно разделить на две части: 5 + 1, 4 + 2 и 3 + 3. Таким образом, есть три одночлена в B6,2. В самом деле, индексы переменных в одночлене такие же, как и в целочисленном разбиении, указывая размеры различных блоков. Общее количество одночленов, входящих в полный многочлен Белла Bп таким образом, равно общему количеству целых разбиенийп.

Также степень каждого монома, которая представляет собой сумму показателей каждой переменной в мономе, равна количеству блоков, на которые разделен набор. То есть, j1 + j2 + ... = k . Таким образом, для полного полинома Белла Bп, можно выделить частичный полином Белла Bп, к собрав все эти одночлены со степенью k.

Наконец, если не учитывать размеры блоков и поставить все Икся = Икс, то суммирование коэффициентов частичного полинома Белла Bп,k даст общее количество способов, которыми набор с п элементы можно разделить на k блоки, что совпадает с Числа Стирлинга второго рода. Кроме того, суммирование всех коэффициентов полного полинома Белла Bп даст нам общее количество способов, которыми набор с п элементы могут быть разделены на неперекрывающиеся подмножества, что совпадает с числом Белла.

В общем, если целое число п является разделенный в сумму, в которой фигурирует "1" j1 раз появляется "2" j2 раз и так далее, то количество перегородки набора размера п которые коллапсируют на этот раздел целого числа п когда члены множества становятся неразличимыми, это соответствующий коэффициент в полиноме.

Примеры

Например, у нас есть

потому что есть

6 способов разделить набор из 6 на 5 + 1,
15 способов разделить набор из 6 на 4 + 2 и
10 способов разделить набор из 6 на 3 + 3.

По аналогии,

потому что есть

15 способов разделить набор из 6 на 4 + 1 + 1,
60 способов разделить набор из 6 на 3 + 2 + 1, и
15 способов разделить набор из 6 на 2 + 2 + 2.

Характеристики

Производящая функция

Экспоненциальные частичные полиномы Белла могут быть определены двойным разложением его производящей функции в ряд:

Другими словами, то же самое - разложением в ряд k-я степень:

Полный экспоненциальный полином Белла определяется формулой , или другими словами:

Таким образом п-й полный полином Белла имеет вид

Точно так же обычный частичный многочлен Белла может быть определен производящей функцией

Или, что то же самое, разложением в ряд k-я степень:

Смотрите также преобразования производящей функции для полинома Белла производящей функции разложения композиций последовательности производящие функции и полномочия, логарифмы, и экспоненты производящей функции последовательности. Каждая из этих формул цитируется в соответствующих разделах Comtet.[1]

Повторяющиеся отношения

Полные полиномы Белла могут быть периодически определяется как

с начальным значением .

Частичные полиномы Белла также можно эффективно вычислить с помощью рекуррентного соотношения:

куда

Полные многочлены Белла также удовлетворяют следующей рекуррентной дифференциальной формуле:[2]

Детерминантные формы

Полный полином Белла может быть выражен как детерминанты:

и

Числа Стирлинга и числа Белла

Значение полинома Белла Bп,k(Икс1,Икс2, ...) на последовательности факториалы равно беззнаковому Число Стирлинга первого рода:

Значение полинома Белла Bп,k(Икс1,Икс2, ...) на последовательности единиц равно a Число Стирлинга второго рода:

Сумма этих значений дает значение полного полинома Белла от последовательности единиц:

какой пth Номер звонка.

Обратные отношения

Если мы определим

тогда у нас есть обратная зависимость

Полиномы Тушара

Многочлен Тушара может быть выражено как значение полного полинома Белла для всех аргументов Икс:

Свертка идентичности

Для последовательностей Иксп, уп, п = 1, 2, ..., определим свертка к:

Границы суммирования равны 1 и п - 1, а не 0 и п .

Позволять быть п-й член последовательности

потом[3]

Например, вычислим . У нас есть

и поэтому,

Другие личности

  • что дает Номер Ла.
  • что дает идемпотентное число.
  • и .
  • Полные полиномы Белла удовлетворяют соотношению биномиального типа:
Это исправляет пропуск фактора в книге Контета.[4]
  • Когда ,
  • Частные случаи частичных полиномов Белла:

Примеры

Первые несколько полных полиномов Белла:

Приложения

Формула Фаа ди Бруно

Формула Фаа ди Бруно можно сформулировать в терминах полиномов Белла следующим образом:

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

потом

В частности, полные многочлены Белла появляются в экспоненте формальный степенной ряд:

который также представляет экспоненциальная производящая функция полных многочленов Белла на фиксированной последовательности аргументов .

Реверс серии

Пусть две функции ж и грамм быть выраженным в формальных степенных рядах как

такой, что грамм композиционно инверсия ж определяется грамм(ж(ш)) = ш или же ж(грамм(z)) = z. Если ж0 = 0 и ж1 0, то явный вид коэффициентов обратного может быть задан в терминах полиномов Белла как[5]

с и - возрастающий факториал, и

Асимптотическое разложение интегралов типа Лапласа

Рассмотрим интеграл вида

куда (а,б) - действительный (конечный или бесконечный) интервал, λ - большой положительный параметр, а функции ж и грамм непрерывны. Позволять ж иметь единый минимум в [а,б], который происходит в Икс = а. Предположим, что при Икс → а+,

с α > 0, Re (β)> 0; и что расширение ж могут быть дифференцированы по срокам. Тогда теорема Лапласа – Эрдели утверждает, что асимптотическое разложение интеграла я(λ) дан кем-то

где коэффициенты cп выражаются в терминах ап и бп с использованием частичного обычный Полиномы Белла, заданные формулой Кэмпбелла – Фромана – Валлеса – Войдило:

Симметричные полиномы

В элементарный симметричный многочлен и симметричный полином степенной суммы могут быть связаны друг с другом с помощью полиномов Белла следующим образом:


Эти формулы позволяют выразить коэффициенты монических многочленов через многочлены Белла его нулей. Например, вместе с Теорема Кэли – Гамильтона они приводят к выражению определителя п × п квадратная матрица А по следам его полномочий:

Индекс цикла симметрических групп

В индекс цикла из симметричная группа может быть выражено через полные многочлены Белла следующим образом:

Моменты и кумулянты

Сумма

это пй сырой момент из распределение вероятностей чей первый п кумулянты находятся κ1, ..., κп. Другими словами, пй момент - это п-й полный многочлен Белла, вычисленный на первом п кумулянты. Точно так же пth кумулянт может быть задан в терминах моментов как

Полиномы Эрмита

Вероятностные Полиномы Эрмита можно выразить через полиномы Белла как

куда Икся = 0 для всех я > 2; таким образом позволяя комбинаторную интерпретацию коэффициентов многочленов Эрмита. В этом можно убедиться, сравнив производящую функцию многочленов Эрмита

с полиномами Белла.

Представление полиномиальных последовательностей биномиального типа

Для любой последовательности а1, а2, …, ап скаляров, пусть

Тогда эта полиномиальная последовательность имеет вид биномиальный тип, т.е. удовлетворяет биномиальному тождеству

Пример: За а1 = … = ап = 1, многочлены представлять Полиномы Тушара.

В общем, мы имеем такой результат:

Теорема: Все полиномиальные последовательности биномиального типа имеют этот вид.

Если мы определим формальный степенной ряд

тогда для всех п,

Программного обеспечения

Полиномы Белла реализованы в:

Смотрите также

Примечания

  1. ^ Контет 1974.
  2. ^ Алексеев, Пологова, Алексеев 2017, разд. 4.2.
  3. ^ Цвийович 2011.
  4. ^ Контет 1974, тождество [31] на стр. 136.
  5. ^ Хараламбидес 2002, п. 437, уравнение (11.43).

Рекомендации

  • Аббас, М .; Буруби, С. (2005). «О новых тождествах для полинома Белла». Дискретная математика. 293 (1–3): 5–10. Дои:10.1016 / j.disc.2004.08.023. МИСТЕР 2136048.CS1 maint: ref = harv (связь)
  • Алексеев, Н .; Пологова, А .; Алексеев, М.А. (2017). "Обобщенные числа Халтмана и циклические структуры графов точек останова". Журнал вычислительной биологии. 24 (2): 93–105. arXiv:1503.05285. Дои:10.1089 / cmb.2016.0190. PMID 28045556.CS1 maint: ref = harv (связь)
  • Эндрюс, Г. Э. (1998). Теория перегородок. Кембриджская математическая библиотека (1-е изд.). Издательство Кембриджского университета. С. 204–211. ISBN 0-521-63766-X.CS1 maint: ref = harv (связь)
  • Белл, Э. Т. (1927–1928). «Полиномы разбиения». Анналы математики. 29 (1/4): 38–46. Дои:10.2307/1967979. JSTOR 1967979. МИСТЕР 1502817.CS1 maint: ref = harv (связь)
  • Бояджиев, К. Н. (2009). «Экспоненциальные многочлены, числа Стирлинга и оценка некоторых гамма-интегралов». Аннотация и прикладной анализ. 2009: 1–18. arXiv:0909.0979. Bibcode:2009АбАпА2009 .... 1Б. Дои:10.1155/2009/168672.CS1 maint: ref = harv (связь) (содержит также элементарный обзор понятия полиномов Белла)
  • Хараламбидес, К. А. (2002). Перечислительная комбинаторика. Чепмен и Холл / CRC. п. 632. ISBN 9781584882909.CS1 maint: ref = harv (связь)
  • Контет, Л. (1974). Продвинутая комбинаторика: искусство конечных и бесконечных расширений. Дордрехт, Голландия / Бостон, США: издательство Reidel Publishing Company. В архиве из оригинала на 2017-06-01. Получено 2019-07-02.CS1 maint: ref = harv (связь)
  • Цвийович, Д. (2011). «Новые тождества для частичных многочленов Белла» (PDF). Письма по прикладной математике. 24 (9): 1544–1547. Дои:10.1016 / j.aml.2011.03.043. В архиве (PDF) из оригинала 2020-03-09. Получено 2020-06-05.CS1 maint: ref = harv (связь)
  • Гриффитс, М. (2012). «Семейства последовательностей из класса полиномиальных сумм». Журнал целочисленных последовательностей. 15: Статья 12.1.8. МИСТЕР 2872465. В архиве из оригинала 2014-05-02. Получено 2012-06-27.CS1 maint: ref = harv (связь)
  • Кручинин, В. В. (2011). «Вывод полиномов Белла второго рода». arXiv:1104.5065 [math.CO].CS1 maint: ref = harv (связь)
  • Noschese, S .; Риччи, П. Э. (2003). «Дифференцирование составных функций многих переменных и полиномов Белла». Журнал вычислительного анализа и приложений. 5 (3): 333–340. Дои:10.1023 / А: 1023227705558.CS1 maint: ref = harv (связь)
  • Роман, С. (2013). Темное исчисление. Dover Publications. п. 208. ISBN 9780486153421.CS1 maint: ref = harv (связь)
  • Воинов, В.Г .; Никулин, М. С. (1994). «О степенных рядах, многочленах Белла, проблеме Харди – Рамануджана – Радемахера и ее статистических приложениях». Кибернетика. 30 (3): 343–358. ISSN 0023-5954.CS1 maint: ref = harv (связь)