Нумераційна комбінаторика

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Нумераційна комбінаторика - це область комбінаторики, яка взаємодіє з кількістю способів формування деяких множин. Наприклад, це може бути підрахунок комбінацій або перестановок. Загальна задача така. Задано нескінченну множину скінченних множин Si занумерованих натуральними числами, нумераційна комбінаторика прагне описати функцію підрахунку, яка підраховує кількість об'єктів в Sn для кожного n. Хоча підрахунок кількості елементів у множині є досить загальна математична задача, багато проблем, які виникають у додатках, мають відносно простий комбінаторний опис. Дванадцятикратний спосіб[en] забезпечує єдину основу для підрахунку перестановок, сполучень та розбиття множини.

Прикладом найпростішої такої функції є замкнена формула, яка може бути виражена композицією елементарних функцій, таких як факторіали, повноваження і так далі. Наприклад, як показано нижче, число різних можливих впорядкування колода з n карт f(n) = n!. Проблема пошуку замкненої формули називається алгебраїчним перерахуванням і часто включає в себе отримання рекурентного співвідношення або функції генерації та їх використання для отримання бажаного у закритому вигляді.

Часто, складні закриті формули дають мало інформації про поведінку функції обліку, бо кількість підрахованих об'єктів зростає. У таких випадках краще використовувати асимптотичний аналіз. Функція р(N) являє собою асимптотичне наближення до , якщо коли . У цьому випадку пишемо

Нехай - нумерація. Множина - властивість множин (відносно нумерації ), якщо з та слідує Нехай тепер та - дві непересічних властивості множин, і нехай знайдуться точки та для яких Тоді не існує рекурсивно нумераційної множини, об'ємлючої властивість та яка не перетинається із [1]

Твірна функція

[ред. | ред. код]

Твірні функції використовуються для опису сімейств комбінаторних об'єктів. Позначимо як множину об'єктів, і нехай F(х) - його генератриса. Тоді:

Де позначає число комбінаторних об'єктів розміром n. Тому число комбінаторних об'єктів розміром n визначається коефіцієнт . Деякі загальні роботи по множинам комбінаторних об'єктів та його впливу на генеруючі функції тепер будуть розвиватися. Іноді також використовується експоненційна твірна функція. У цьому випадку вона буде мати вигляд:

Об'єднання

[ред. | ред. код]

Дано дві комбінаторні множини, і з похідними функціями F(x) та G(x) відповідно, непересічним об'єднанням двох сімей ( ) є твірна функція F(x) + G(x).

Дві комбінаторні множини, вище Декартового добутка (пари) з двох множин () мають похідну функція F(x)G(x).

Послідовності

[ред. | ред. код]

Послідовність узагальнює ідею пари, як позначено вище. Послідовністю є довільний Декартів добуток комбінаторного об'єкта на самого себе. Формально:

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

Комбінаторні конструкції

[ред. | ред. код]

Усі вищевказані операції можуть бути використані для перерахування загальних комбінаторних об'єктів, включаючи дерева (бінарні і плоскі), числа Каталана і циклів. Комбінаторна структура складається з атомів. Наприклад, з дерев атоми створюють вузли. Атоми, з яких складається об'єкт, можуть бути позначені або підписані. Немічені атоми відрізняються один від одного, в той час як мічених атомів є різними. Тому, комбінаторний об'єкт, що складається з мічених атомів нового об'єкта, може бути сформований шляхом простої заміни двох або більше атомів.

Бінарні і плоскі дерева

[ред. | ред. код]

Бінарні і плоскі дерева є прикладами неміченої комбінаторної структури. Дерева складаються з вузлів, з'єднаних по краях таким чином, що немає ніяких циклів. Взагалі вузол називається кореневим, який не має батьківського вузолу. У плоских деревах кожен вузол може мати довільне число дочірних вузлів. У бінарних деревах, особливий у плоских деревах, кожен вузол може мати два або взагалі не мати дочірних вузлів. Позначимо сімейство всіх плоских дерев. Тоді ця сім'я може бути рекурсивно визначена наступним чином:

У цьому випадку представляє сімейство об'єктів, що складається з одного вузла. Це породжує функція x. Позначимо функцію генерації P(x), поставивши опис: плоске дерево складається з вузла, до якого кріпиться довільне число піддерев, кожне з яких також є плоским деревом. За допомогою операції на множині комбінаторних конструкцій, розроблених раніше, це призводить до рекурсивної функції генерації:

Після рішення для P(x):

Подана формула для числа плоских дерев може бути визначена шляхом вилучення коефіцієнту при xn.

Примітка: позначення [xn] f(x) позначає коефіцієнт при xn в f(x). Розширення серії квадратного кореня засновано на теоремі Бінома Ньютона. Потрібно використати біноміальний коефіцієнт, щоб перейти з п'ятої у четверту лінію. Вислів в останньому рядку (n − 1)th рівен числу Каталана. Тому pn = cn−1.

Див. також

[ред. | ред. код]

Посилання

[ред. | ред. код]
  1. Young P.R. - Toward a theory of enumerations.