Кіріспе
Комбинаторлық математикада комбинаторлық түрлер теориясы – дискретті құрылымдардың генерациялық функцияларын шығарудың абстрактілі, жүйелі әдісі, бұл осы құрылымдарды ғана есептеуге емес, сонымен қатар оларға қатысты биективті дәлелдер беруге мүмкіндік береді. Комбинаторлық түрлердің мысалдары – (шекті) графтар, пермутациялар, ағаштар және т.б.; олардың әрқайсысы белгілі бір өлшемдегі құрылымдардың санын есептейтін байланысты генерациялық функцияға ие. Түрлер теориясының мақсаты – күрделі құрылымдарды қарапайым құрылымдардың түрлендірулері мен комбинациялары арқылы сипаттап, талдау жасау. Бұл операциялар генерациялық функциялардың эквивалентті манипуляцияларына сәйкес келеді, сондықтан күрделі құрылымдар үшін мұндай функцияларды шығару басқа әдістерге қарағанда әлдеқайда оңай. Теория Андре Жуайалдың айналасындағы канадалық зерттеушілер тарапынан енгізіліп, жан-жақты жетілдіріліп, қолданылды. Теорияның күші оның абстракция деңгейінен туындайды. Құрылымның "беретін форматы" (мысалы, графтар үшін жабылас тізім мен жабылас матрица) маңызды емес, өйткені түрлер таза алгебралық. Категория теориясы мұнда туындайтын ұғымдар үшін пайдалы тіл қамтамасыз етеді, бірақ түрлермен жұмыс істеу үшін категорияларды түсінудің қажеті жоқ. Түрлер категориясы шекті жиындардағы симметриялық тізбектер категориясына эквивалентті.
Түрлерді есептеу
Өрлеу функцияларының арифметикасы түрлердегі белгілі бір "табиғи" операцияларға сәйкес келеді. Негізгі операциялар – қосу, көбейту, композиция және дифференциалдау; сонымен қатар түрлердегі теңдікті анықтау қажет. Категория теориясы екі функтордың эквивалентті екенін сипаттаудың бір жолын ұсынады: табиғи изоморфизм. Бұл контексте, әрбір А үшін А-дағы F құрылымдары мен А-дағы G құрылымдары арасында биекция бар екенін білдіреді, бұл биекция тасымалдаумен өзара әрекеттесуде "жақсы қасиеттерге" ие. Бірдей өрлеу функциясы бар түрлер изоморфты болмауы мүмкін, бірақ изоморфты түрлер әрқашан бірдей өрлеу функциясына ие болады.
Қосу
Түрлерді қосу жиынтықтардың ажыратылған одағы арқылы анықталады және құрылымдар арасында таңдау жасауға сәйкес келеді. F және G түрлері үшін (F + G)[A] анықтамасы F[A] және G[A] жиындарының ажыратылған одағы (сонымен қатар "+" символымен белгіленеді) болып табылады. Осыдан (F + G)(x) = F(x) + G(x) теңдігі шығады. Мысал ретінде, E+ түрін бос емес жиындардың түрі деп қарастырайық, оның тудыру функциясы E+(x) = ex − 1, ал 1 түрін – бос жиынның түрі деп қарастырайық, оның тудыру функциясы 1(x) = 1. Осыдан екі түрдің қосындысы E = 1 + E+ теңдігі келеді: яғни, "жинақ бос немесе бос емес". Мұндай теңдеулерді жекелеген құрылымға, сондай-ақ құрылымдардың барлық жиынтығына сілтеме ретінде қарастыруға болады.
Көбейту
Түрлерді көбейту сәл қиынрақ. Деректер жиынының Декарт көбейтіндісін анықтама ретінде қабылдауға болады, бірақ оның комбинаторлық интерпретациясы толыққанды дұрыс емес. (Осы көбейтіндінің қолданылуы туралы төменде қараңыз.) Бір жиынның екі байланыссыз құрылымын біріктірудің орнына, көбейту операторы жиынды екі компонентке бөлу идеясын пайдаланады, бірінде F құрылымын, екіншісінде G құрылымын жасайды. Бұл А жиынының барлық мүмкін бинарлық бөліністерінің ажыратылған қосындысы болып табылады. Көбейтудің ассоциативті және коммутативті (изоморфизмге дейін) екенін, сондай-ақ қосуға қатысты үлестірімді екенін көрсету оңай. Генерациялық қатарларға келсек, (F · G)(x) = F(x)G(x). Төмендегі диаграммада бес элементі бар жиынға (F · G) құрылымының бір мүмкін нұсқасы көрсетілген. F құрылымы (қызыл) негізгі жиынның үш элементін таңдайды, ал G құрылымы (ашық көк) қалғандарын иеленеді. Басқа құрылымдарда F және G жиынды басқаша бөлуі мүмкін. A негізгі жиынындағы (F · G)[A] жиыны – мұндай құрылымдардың барлығының ажыратылған қосындысы. Түрлерді қосу және көбейту – сандық есептеудің қосынды және көбейту ережелерінің ең толыққанды көрінісі.
Құрамы
Композиция, сонымен қатар ауыстыру деп аталады, тағы да күрделірек. Негізгі идея – F компоненттерін G құрылымдарымен алмастыру, (F∘G) құру. Көбейту сияқты, бұл кіріс жиынтығы A-ны бөлу арқылы жасалады; G құрылымдарын жасау үшін G-ге бөлінген кіші жиынтықтар беріледі, ал G құрылымдарын байланыстыратын F құрылымын жасау үшін F-ке кіші жиынтықтар жиынтығы беріледі. Композиция жұмыс істеуі үшін G-нің бос жиынтықты өзіне бейімдеуі қажет. Формалды анықтама:
Here, P is the species of partitions, so P[A] is the set of all partitions of A. This definition says that an element of (F ∘ G)[A] is made up of an F structure on some partition of A, and a G structure on each component of the partition. The generating series is
One such structure is shown below. Three G structures (light blue) divide up the five element base set between them; then, an F structure (red) is built to connect the G structures. These last two operations may be illustrated by the example of trees. First, define X to be the species "singleton" whose generating series is X(x) = x. Then the species Ar of rooted trees (from the French "arborescence") is defined recursively by Ar = X · E(Ar). This equation says that a tree consists of a single root and a set of (sub )trees. The recursion does not need an explicit base case: it only generates trees in the context of being applied to some finite set. One way to think about this is that the Ar functor is being applied repeatedly to a "supply" of elements from the set — each time, one element is taken by X, and the others distributed by E among the Ar subtrees, until there are no more elements to give to E. This shows that algebraic descriptions of species are quite different from type specifications in programming languages like Haskell. Likewise, the species P can be characterised as P = E(E+): "a partition is a pairwise disjoint set of nonempty sets (using up all the elements of the input set)". The exponential generating series for P is , which is the series for the Bell numbers.
Мұнда P – бөлшектердің түрі, сондықтан P[A] – A жиынының барлық бөлшектерінің жиыны. Бұл анықтама (F∘G)[A] элементі A-ның бір бөлігінде F құрылымынан және бөліктің әрбір компонентінде G құрылымынан тұрады дейді. Генерациялық қатар:
Here, P is the species of partitions, so P[A] is the set of all partitions of A. This definition says that an element of (F ∘ G)[A] is made up of an F structure on some partition of A, and a G structure on each component of the partition. The generating series is
One such structure is shown below. Three G structures (light blue) divide up the five element base set between them; then, an F structure (red) is built to connect the G structures. These last two operations may be illustrated by the example of trees. First, define X to be the species "singleton" whose generating series is X(x) = x. Then the species Ar of rooted trees (from the French "arborescence") is defined recursively by Ar = X · E(Ar). This equation says that a tree consists of a single root and a set of (sub )trees. The recursion does not need an explicit base case: it only generates trees in the context of being applied to some finite set. One way to think about this is that the Ar functor is being applied repeatedly to a "supply" of elements from the set — each time, one element is taken by X, and the others distributed by E among the Ar subtrees, until there are no more elements to give to E. This shows that algebraic descriptions of species are quite different from type specifications in programming languages like Haskell. Likewise, the species P can be characterised as P = E(E+): "a partition is a pairwise disjoint set of nonempty sets (using up all the elements of the input set)". The exponential generating series for P is , which is the series for the Bell numbers.
Мұндай құрылымның мысалы төменде көрсетілген. Үш G құрылымы (ашық көк түс) бес элементтен тұратын негізгі жиынтықты олардың арасында бөледі; содан кейін G құрылымдарын байланыстыру үшін F құрылымы (қызыл) құрылады. Соңғы екі операцияны ағаштар мысалымен түсіндіруге болады. Біріншіден, X-ті «бір элементтік» түрі деп анықтайық, оның генерациялық қатары X(x) = x. Содан кейін тамырлы ағаштардың Ar түрі (француз тілінен «ағаш тәрізді») рекурсивті түрде Ar = X · E(Ar) арқылы анықталады. Бұл теңдеу ағаштың бір тамырынан және (кіші) ағаштар жиынтығынан тұратынын көрсетеді. Рекурсияға нақты базалық жағдайдың қажеті жоқ: ол тек белгілі бір шекті жиынтыққа қолданылғанда ғана ағаштарды жасайды. Бұл туралы ойлаудың бір жолы – Ar функторы жиынтықтан элементтердің «жеткізіліміне» қайта-қайта қолданылады, әр жолы бір элементті X алады, ал қалғандарын E Ar кіші ағаштары арасында бөледі, E-ге беруге элементтер қалмайынша. Бұл түрлердің алгебралық сипаттамалары Хаскелл сияқты бағдарламалау тілдеріндегі типтік сипаттамалардан мүлдем өзгеше екенін көрсетеді. Сол сияқты, P түрін P = E(E+) деп сипаттауға болады: «бөлік – бос емес жиынтықтардың жұптық жазылмаған жиынтығы (кіріс жиынтығының барлық элементтерін пайдалана отырып)». P үшін экспоненциалды генерациялық қатар – , бұл Белл сандарының қатары.
Here, P is the species of partitions, so P[A] is the set of all partitions of A. This definition says that an element of (F ∘ G)[A] is made up of an F structure on some partition of A, and a G structure on each component of the partition. The generating series is
One such structure is shown below. Three G structures (light blue) divide up the five element base set between them; then, an F structure (red) is built to connect the G structures. These last two operations may be illustrated by the example of trees. First, define X to be the species "singleton" whose generating series is X(x) = x. Then the species Ar of rooted trees (from the French "arborescence") is defined recursively by Ar = X · E(Ar). This equation says that a tree consists of a single root and a set of (sub )trees. The recursion does not need an explicit base case: it only generates trees in the context of being applied to some finite set. One way to think about this is that the Ar functor is being applied repeatedly to a "supply" of elements from the set — each time, one element is taken by X, and the others distributed by E among the Ar subtrees, until there are no more elements to give to E. This shows that algebraic descriptions of species are quite different from type specifications in programming languages like Haskell. Likewise, the species P can be characterised as P = E(E+): "a partition is a pairwise disjoint set of nonempty sets (using up all the elements of the input set)". The exponential generating series for P is , which is the series for the Bell numbers.