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

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

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

Див. також

Посилання

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