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

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

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

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

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

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

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

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

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

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

Об'єднання

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

Пари

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

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

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

{\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

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

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

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

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

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

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

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

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

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

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

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

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

{\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.

Див. також

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

Посилання

Зейлберер, Д., PDF Перерахувальна та алгебраїчна Комбінаторика^{[недоступне посилання з липня 2019]}
Йонер, А. і Стенлі, р. П., форматі PDF "Комбінаторна альманаху"^{[недоступне посилання з липня 2019]}
Грехем р. л., Grötschel М., Ловас л., ЕЦП. (1996). "Довідник Комбінаторика", Томи 1 і 2. Ельзевір (Північна Голландія), Амстердам, і mit Press, cambridge, маса. ИСБН 0-262-07169-Х.
Шаблон:Цитують книгу
Лоер, Микола А. (2011). Биективных Комбінаторика Архівовано 23 жовтня 2015 у wayback.archive-it.org. CRC прес. ISBN У 143984884X, ИСБН 978-1439848845.
Стенлі, Річард П. (1997, 1999). "Перерахувальна Комбінаторика", Томи 1 і 2^{[недоступне посилання з липня 2019]}. Кембриджський Університет. ISBN У 0-521-55309-1, ИСБН 0-521-56069-1.
Комбінаторний Аналіз http://encyclopedia.jrank.org/CLI_COM/COMBINATORIAL_ANALYSIS.html – стаття у Брітаніки одинадцятому виданні
Ріордан, Джон (1958). "Введення в Комбінаторний Аналіз", Уайлі і сини, Нью-Йорку (перевиданий).
Ріордан, Джон (1968). "Комбінаторні тотожності", Уайлі і сини, Нью-Йорку (перевиданий).
В. А. Бызов, Перечислительные задачи, связанные с преобразованием Донахью, Вестник российских университетов. Математика, 2019, том 24, выпуск 125, 5–25.
Шаблон:Цитують книгу

Young P.R. - Toward a theory of enumerations.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Young P.R. - Toward a theory of enumerations.