Нумераційна комбінаторика — Вікіпедія

Нумераційна комбінаторика - це область комбінаторики, яка взаємодіє з кількістю способів формування деяких множин. Наприклад, це може бути підрахунок комбінацій або перестановок. Загальна задача така. Задано нескінченну множину скінченних множин 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.

Див. також[ред. | ред. код]

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

Посилання[ред. | ред. код]

• Зейлберер, Д., 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.
• Шаблон:Цитують книгу

п о р Розділи математики огляд[en] переліки тем Галузі Алгебра елементарна лінійна полілінійна абстрактна Теорія груп геометрична комбінаторна обчислювальна Алгоритми Арифметика / Теорія чисел адитивна алгебрична аналітична Геометрія дискретна алгебрична біраціональна диференціальна синтетична скінченна Диференціальні рівняння / Динамічні системи Комбінаторика адитивна алгебрична арифметична геометрична многогранників нумераційна топологічна Математика та мистецтво Математична логіка Математична статистика Математична фізика Обчислення / Аналіз Оптимізація Опуклий аналіз Рекреаційна математика Статистика Теорія графів алгебрична екстремальна спектральна Теорія ігор Теорія інформації Теорія ймовірності Теорія категорій Теорія керування Теорія Лі Теорія множин Теорія порядку Теорія представлень Топологія загальна алгебрична диференціальна Тригонометрія Функціональний аналіз Чисельний аналіз Підрозділи Чиста Прикладна Дискретна Обчислювальна Експериментальна   Категорія   Портал

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