Кіріспе

Аналитикалық комбинаторикадағы әдіс. Комбинаторикада символикалық әдіс – комбинаторлық объектілерді санау техникасы. Ол объектілердің ішкі құрылымын пайдаланып, олардың туынды функциялары үшін формулалар шығарады. Бұл әдіс көбінесе Филипп Флажолемен байланысты және оның Роберт Седжвикпен бірге жазған «Аналитикалық комбинаторика» кітабының А бөлімінде толық сипатталған. Ал кітаптың қалған бөлімі күрделі талдауды тиісті туынды функцияларға қатысты асимптотикалық және ықтималдық нәтижелер алу үшін қалай қолдану керектігін түсіндіреді. Екі ғасыр бойы туынды функциялар олардың коэффициенттеріндегі сәйкес рекурренциялар арқылы пайда болды (Бернулли, Эйлер, Артур Кейли, Шредер, Раманужан, Риордан, Кнут, Комте және т.б. еңбектерінде көрінеді). Кейіннен туынды функциялар бастапқы дискретті комбинаторлық объектілердің көптеген басқа жақтарын қамтитынын және мұны тікелей формальды жолмен жасауға болатыны біртіндеп түсінілді: кейбір комбинаторлық құрылымдардың рекурсивті сипаты белгілі бір изоморфизмдер арқылы сәйкес туынды функцияларындағы маңызды теңдіктерге ауысады. Поляның еңбектерінен кейін, 1970 жылдары осы бағытта комбинаторлық кластарды және олардың туынды функцияларын анықтау үшін тілдердің кеңінен қолданылуымен одан да ілгерілеулер жасалды. Фуата мен Шютценбергердің пермутациялар, Бендер мен Голдманның префабтар және Джойалдың комбинаторлық түрлер туралы еңбектерінде көрсетілгендей. Назарда болыңыз, санаудағы бұл символикалық әдіс «Блиссардтың символикалық әдісімен» байланысты емес, ол жай ғана көлеңкелі есептеудің тағы бір ескі атауы. Комбинаторикадағы символикалық әдіс комбинаторлық құрылымдарды талдаудың алғашқы қадамын құрайды, ол жылдам есептеу схемаларына, асимптотикалық қасиеттерге және лимит заңдарына, кездейсоқ генерацияға әкелуі мүмкін, олардың барлығы компьютерлік алгебра арқылы автоматтандыруға ыңғайлы.

Процедура

Әдетте, 0 өлшемді бір нысанды қамтитын бейтарап сыныптан (бейтарап нысан, көбінесе ∅ деп белгіленеді) және әрқайсысы 1 өлшемді бір нысанды қамтитын бір немесе бірнеше атомдық сыныптардан басталады. Содан кейін, әр түрлі қарапайым операцияларды қамтитын теориялық қатынастар, мысалы, ажыратылған одақтар, көбейтулер, жиынтықтар, тізбектер және көп жиынтықтар, бұрыннан анықталған сыныптар арқылы күрделі сыныптарды анықтайды. Бұл қатынастар рекурсивті болуы мүмкін. Символикалық комбинаториканың әдемілігі сол жерде, теориялық немесе символикалық қатынастар тікелей алгебралық қатынастарға, яғни туғызатын функцияларға ауысады. Осы мақалада біз комбинаторлық сыныптарды белгілеу үшін үлкен әріптерді, ал сәйкес туғызатын функцияларды – сол әріптердің кішкентай нұсқаларын қолдану туралы конвенцияны ұстанамыз (мысалы, сыныптың туғызатын функциясы ). Символикалық комбинаторикада екі түрлі туғызатын функция жиі қолданылады: белгісіз нысандардың комбинаторлық сыныптары үшін қолданылатын обыкновен туғызатын функциялар және белгіленген нысандардың сыныптары үшін қолданылатын экспоненциалды туғызатын функциялар. -ның (обыкновен немесе экспоненциалды) туғызатын функцияларының және сәйкесінше екенін көрсету оңай. Ажыратылған одақ та қарапайым: егер және ажыратылған жиынтықтар болса, онда . Басқа операцияларға сәйкес келетін қатынастар біз таңбаланған немесе таңбаланбаған құрылымдар (және обыкновен немесе экспоненциалды туғызатын функциялар) туралы сөйлеп отырмыз ба дегенге байланысты.

Комбинациялық жиынтық

Бірліктерді бір-бірімен қиылыспайтын бірліктерге шектеу маңызды; алайда, символикалық комбинаториканың формалды сипаттамасында қай жиындардың қиылыспайтынын қадағалау тым қиын. Оның орнына, біз қиылысудың болмауын қамтамасыз ететін құрылымды қолданамыз (бірақ сақ болыңыз, бұл операцияның мағынасына да әсер етеді). Екі жиынның – және – комбинаторлық қосындысын анықтағанда, әр жиынның элементтерін ерекше белгімен таңбалаймыз, мысалы, – жиынының элементтері үшін және – жиынының элементтері үшін. Комбинаторлық қосынды мынадай болады:

Бұл операция формальды түрде қосуға сәйкес келеді.

Белгісіз құрылымдар

Белгіленбеген құрылымдар үшін қарапайым генерациялау функциясы (OGF) пайдаланылады. Бір тізбектің OGF-ы былай анықталады:

Анықтама және анықталатын кластар

Жоғарыда аталған қарапайым құрылымдар спецификация ұғымын анықтауға мүмкіндік береді. Бұл спецификация бізге бірнеше комбинаторлық кластармен рекурсивті теңдеулер жиынтығын қолдануға мүмкіндік береді. Формальды түрде, комбинаторлық кластар жиынтығының спецификациясы – теңдеулер жиынтығы , мұндағы – өрнек, оның атомдары – және –тар, ал операторлары – жоғарыда тізілген қарапайым құрылымдар. Комбинаторлық құрылымдар класы, егер ол спецификацияға ие болса, құрастырылатын немесе спецификацияланатын деп аталады. Мысалы, жапырақтарының тереңдігі жұп (сәйкесінше, тақ) болатын ағаштар жиынтығын екі кластың көмегімен спецификациялауға болады және Бұл кластар теңдеулерді қанағаттандыруы керек және .

Белгіленген құрылымдар

Егер оның әрбір атомында теріс емес бүтін сан белгісі болса және осы белгілердің әрқайсысы өзгеше болса, онда объект әлсіз белгіленген болып саналады. Объект (күшті немесе жақсы) белгіленген, егер осы белгілер тізбектелген бүтін сандарды құраса. Ескерту: кейбір комбинаторлық сыныптар белгіленген құрылымдар немесе белгіленбеген құрылымдар ретінде жақсы анықталады, бірақ кейбіреулері екі сипаттаманы да оңай қабылдай алады. Белгіленген құрылымдардың жақсы мысалы – белгіленген графтар класы. Белгіленген құрылымдар үшін экспоненциалды генерациялау функциясы (EGF) қолданылады. Бір тізбектің EGF былай анықталады:

Құрастыру

Белгіленген құрылымдарда элементтер жиынтығы дәл бір реттілікке сәйкес келеді. Бұл белгіленбеген жағдайдан өзгеше, онда кейбір өзгерістер бірдей болуы мүмкін. Осылайша, үшін бізде

Цикл

Сонымен қатар, циклдар белгіленбеген жағдайға қарағанда жеңілдеу. Ұзындығы *n* болатын цикл *n* түрлі тізбекке сәйкес келеді. Осылайша, *n* үшін бізде:

Мысал

Кейли ағашының өсуі – таңбаланған, жазықтыққа жатпайтын және тамырланған ағаш, онда тамырдан басталатын кез келген тармақтағы таңбалар өсу тізбегін құрайды. Осылай болса, мұндай ағаштардың класын былай белгілейміз. Рекурсивті сипаттама енді…