У комбінаториці поліноми Белла, що названі на честь Еріка Темпла Белла, використовуються для вивчення заданих розділів. Вони пов'язані з числами Стірлінга та Белла. Вони також зустрічаються у багатьох програмах, наприклад у формулі Фаа ді Бруно.
Експоненційні поліноми Белла[ред. | ред. код]
Часткові або неповні експоненційні поліноми Белла — це трикутний масив поліномів, заданий
де сума береться за всіма послідовностями j1, j2, j3, ..., jn — k +1 невід’ємних цілих чисел, таким чином, що б виконувалися наступні дві умови :
Сума
називається n-м повним експоненційними полінонмоми Белла.
Звичайні поліноми Белла[ред. | ред. код]
Так само часткові звичайні поліноми Белла, на відміну від звичайного експоненціального многочлена Белла, визначений вище, задається формулою
де сума пробігає всі послідовності j1, j2, j3, ..., jn – k +1 невід'ємних цілих чисел, таких що
Звичайні поліноми Белла можна виразити в термінах експоненційних поліномів Белла:
Як правило, під поліномами Белла маються на увазі експоненційні поліноми Белла, якщо не зазначено іншого.
Експоненційні поліноми Белла безпосередньо стосується способів розбиття множин. Наприклад, якщо ми розглядаємо множину {A, B, C}, її можна розбити на два непусті, підмножини що не перетинаються, які також називають частинами або блоками, 3 різними способами:
- {{A}, {B, C}}
- {{B}, {A, C}}
- {{C}, {B, A}}
Таким чином, ми можемо закодувати інформацію щодо цих розбиттів як
Тут підписники B3,2 говорять нам, що ми розглядаємо поділ набору з 3-х елементів на 2 блоки. Підрядник кожного xi вказує на наявність блоку з елементами j (або блоку розміру i) в заданому розділі. Отже, x2 вказує на наявність блоку з двома елементами. Аналогічно, x1 вказує на наявність блоку з одним елементом. Експонент xij вказує на те, що в одному розбитті є j таких блоків розміром i. Тут, оскільки і x1, і x2 є експонент 1, це вказує, що в даному розділі є лише один такий блок. Коефіцієнт одночлена вказує, скільки таких перегородок є. У нашому випадку є 3 розділи набору з 3 елементами на 2 блоки, де в кожній секції елементи розділені на два блоки розмірами 1 і 2.
Оскільки будь-який набір може бути розділений на один блок лише одним способом, вищезгадане тлумачення означало б, що Bn,1 = xn. Аналогічно, оскільки існує лише один спосіб поділу множини з n елементами на n одиниць, Bn,n = x1n.
Як складніший приклад розглянемо
Це говорить нам про те, що якщо набір з 6 елементами розділений на 2 блоки, то ми можемо мати 6 розділів з блоками розміру 1 і 5, 15 розділів з блоками розміру 4 і 2, і 10 розділів з 2 блоками розміром 3.
Сума підписок у монометах дорівнює загальній кількості елементів. Таким чином, кількість одночленів, що з'являються в частковому многочлені Белла, дорівнює кількості способів, що ціле число n може бути виражене як підсумок k додатних цілих чисел. Це і є розбиття числа n на k частин. Наприклад, у вище наведених прикладах ціле число 3 можна розділити на дві частини лише як 2 + 1. Таким чином, у B3,2 містить лише один одночлен. Однак ціле число 6 можна розділити на дві частини як 5 + 1, 4 + 2 і 3 + 3. Таким чином, B6,2 містить три одночлени. Дійсно, індекси змінних у мономери такі самі, як ті, які задаються цілим розділом, що вказує на розміри різних блоків. Таким чином, загальна кількість одночленів, що з'являються в повному поліномі Белла Bn, дорівнює загальній кількості розбиттів числа n.
Також ступінь кожного одночлена, що є сумою експонентів кожної змінної в мономі, дорівнює кількості блоків, на які поділяється множина. Тобто j 1 + j 2 + ... = k. Таким чином, задавши повний многочлен Белла B n, ми можемо відокремити частковий многочлен Белла Bn,k, зібравши всі ці мономи зі ступенем k.
Нарешті, якщо знехтувати розмірами блоків і поставити всі xi = x, то підсумовування коефіцієнтів часткового многочлена Белла Bn, k дасть загальну кількість способів розподілу множини з n елементів k блоки, що те саме, що числа Стірлінга другого роду. Крім того, підсумовування всіх коефіцієнтів повного многочлена Белла Bn дасть нам загальну кількість способів поділити набір з п елементами на підмножини, що не перекриваються, що те саме, що і число Белла.
Загалом, якщо ціле число n розбиттів на суму, в якій «1» з'являється j1 раз, «2» з'являється j2 рази і так далі, то кількість розбиття множини розміром n, які згортаються до цього розділу цілого числа n, коли члени множини стають невідрізними, — це відповідний коефіцієнт у многочлени.
Нехай, ми маємо
оскільки є
- 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-го степеню:
Повні експоненційні поліноми Белла визначається за допомогою або інакше:
Таким чином, n -й повні поліноми Белла задається як
Так само звичайні часткові поліноми Белла можна визначити твірною функцією
Або, що еквівалентно, розкладом у ряд k-ї степеня:
Дивись також перетворення твірної функції для розкладу у ряд твірної функцій поліномів Белла що є композицією послідовностей твірних функцій та степенів, логаритмів та експоненційної функції, що послідовності твірних функцій. Кожна з цих формул можна знайти у відповідних розділах праці Комтета.
Рекурентні співвідношення[ред. | ред. код]
Повні поліноми Белла можна визначити за допомогою рекурентних співвідношень як
з початковим значенням .
Часткові поліноми Белла також можна ефективно обчислені рекурентним співвідношенням:
де
Повні поліноми Белла також задовольняють такій диференціальній рекурентній формулі:
Повні поліноми Белла можна виразити у вигляді визначника:
Числа Стірлінга та Белла[ред. | ред. код]
Значення поліномів Белла Bn,k (x1, x2, ...) для набору факторіалів дорівнює числу Стірлінга першого роду (без знаку):
Поліноми Белла Bn, k (x1, x2, ...) від набору одиниць дорівнює числам Стірлінга другого роду :
Сума цих значень дає значення повного полінома Белла від набору одиниць:
що є n-м числом Белла.
Зворотні співвідношення[ред. | ред. код]
Якщо ми визначимо
то ми маємо таке зворотне співвідношення
Поліноми Тушара може бути виражена як значення повного многочлена Белла від аргументів, що всі дорівнюють х:
Для послідовностей x n, y n, n = 1, 2, ..., визначте згортку по:
Межі підсумовування — 1 і n — 1, а не 0 і n.
Дозволяти — n-й член послідовності
Тоді [3]
Наприклад, давайте обчислити . Ми маємо
і, таким чином,
- що надає число Лаха.
- що повертає ідемпотентне число.
- Повний многочлен Белла задовольняє відношення типу двочлена:
Це виправляє опущення фактора у книзі Конта.
- Коли ,
- Особливі випадки часткових многочленів Белла:
Перші декілька повних многочленів Белла:
Формула Фаа ді Бруно може бути викладена з точки зору поліномів Белла наступним чином:
Аналогічно, версію формули Фаа ді Бруно можна подати з використанням многочленів Белла наступним чином. Припустимо
Тоді
Зокрема, повні поліноми Белла фігурують у розкладі експоненти формальний степеневий ряд:
що також представляє генератису для експоненти повних многочленів Белла на фіксованій послідовності аргументів .
Нехай дві функції f і g виражаються у формальних рядах потужностей як
такий, що g — композиційна інверсія f, визначена g(f (w)) = w або f (g(z)) = z. Якщо f0 = 0 і f1 ≠ 0, то явна форма коефіцієнтів оберненої може бути задана в терміні многочленів Белла як
з і — це фактор, що зростає, і
Симетричні многочлени[ред. | ред. код]
Елементарний симетричний многочлен і степеневий многочлен суми потужності можуть бути пов'язані один з одним за допомогою поліномів Белла як:
Ці формули дозволяють виразити коефіцієнти монічних поліноми через поліноми Белла з нульовими аргументами. Наприклад, разом із теоремою Кейлі — Гамільтона вони призводять до вираження детермінантної n × n квадратної матриці A через сліди її потужностей:
Індекс циклу симетричних груп[ред. | ред. код]
Індекс циклу симетричної групи можна виразити через повні многочлени Белла так:
Поліноми Ерміта імовірністів можна виразити через поліноми Белла як
де xi = 0 для всіх i > 2; що передбачає комбінаторну інтерпретацію коефіцієнтів поліномів Ерміта. Це можна побачити, порівнюючи генератрису поліномів Ерміта
з поліномами Белла.
Програмне забезпечення[ред. | ред. код]
Поліноми Белла реалізовані в: