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

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

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

Часто, складні закриті формули дають мало інформації про поведінку функції обліку, бо кількість підрахованих об'єктів зростає. У таких випадках краще використовувати асимптотичний аналіз. Функція р(N) являє собою асимптотичне наближення до ${\displaystyle f(n)}$, якщо ${\displaystyle f(n)/g(n)\rightarrow 1}$ коли ${\displaystyle n\rightarrow \infty }$. У цьому випадку пишемо ${\displaystyle f(n)\sim g(n).\,}$

Нехай ${\displaystyle \eta }$ - нумерація. Множина ${\displaystyle P\subseteq \mathbb {N} }$ - властивість множин (відносно нумерації ${\displaystyle \eta }$), якщо з ${\displaystyle x\in P}$ та ${\displaystyle \eta _{x}=\eta _{y}}$ слідує ${\displaystyle y\in P.}$ Нехай тепер ${\displaystyle P_{0}}$ та ${\displaystyle P_{1}}$ - дві непересічних властивості множин, і нехай знайдуться точки ${\displaystyle x_{0}\in P_{0}}$ та ${\displaystyle x_{1}\in P_{1},}$ для яких ${\displaystyle \eta _{x_{0}}\subseteq \eta _{x_{1}}.}$ Тоді не існує рекурсивно нумераційної множини, об'ємлючої властивість ${\displaystyle P_{0}}$ та яка не перетинається із ${\displaystyle P_{1}.}$ ^[1]

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

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

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}}$

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

${\displaystyle F(x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}$

Об'єднання

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

Пари

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

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

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

${\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\times {\mathcal {F}}\ \cup \cdots }$

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

${\displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}}$

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

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

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

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

${\displaystyle {\mathcal {P}}=\{\bullet \}\times {\mbox{Seq}}({\mathcal {P}})}$

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

${\displaystyle P(x)=x{\frac {1}{1-P(x)}}}$

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

${\displaystyle P(x)={\frac {1-{\sqrt {1-4x}}}{2}}}$

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

${\displaystyle {\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}}$

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

Див. також

• Комбінаторні принципи
• Алгебраїчна комбінаторика
• Асимптотична комбінаторика
• Комбінаторний вибух
• Принцип включення-виключення
• Метод відрізнювання елементів
• Комбінаторні види
• Теорія решето
• Теорема Редфілда — Пойа
• Лема Бернсайда