Комбинаторлық класс – математикалық объектілер жиыны. Өлшем функциясы, сану тізбегі және изоморфизм ұғымдары есептеу комбинаторикасының негізгі тақырыптары.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикада комбинаторлық сынып — әрбір нысанды теріс емес бүтін санға бейнелейтін өлшем функциясымен бірге саналатын математикалық нысандар жиыны, мұнда әрбір өлшемде шекті санда ғана нысан болады.
In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non negative integer, such that there are finitely many objects of each size.
Тізбелерді санау және изоморфизм
Комбинаторлық кластың санау тізбегі – i = 0, 1, 2 үшін i өлшемдегі элементтер санының тізбегі; оны осы сандарды коэффициенттері ретінде қолданылатын туынды функция ретінде де сипаттауға болады. Комбинаторлық кластардың санау тізбектері – санау комбинаторикасының негізгі зерттеу нысаны болып табылады. Екі комбинаторлық класс, егер олардың әрбір өлшемдегі объектілер саны бірдей болса, немесе олардың санау тізбектері бірдей болса, изоморфты деп есептеледі. Көбінесе, екі комбинаторлық кластың изоморфты екені белгілі болғаннан кейін, осы эквиваленттіліктің биективті дәлелі ізделеді; мұндай дәлелді екі изоморфты кластағы объектілердің бір-біріне криптоморфты екенін көрсету ретінде қарастыруға болады. Мысалы, дұрыс көпбұрыштардың триангуляциясы (өлшемі көпбұрыштың қабырғаларының санымен беріледі және әрбір өлшем үшін триангуляциялауға арналған көпбұрыштың нақты таңдауы) және тамырсыз бинарлық жазық ағаштар жиыны (граф изоморфизміне дейін, жапырақтардың белгілі бір ретімен және жапырақтар санымен берілген өлшеммен) екеуі де Каталан сандарымен есептеледі, сондықтан олар изоморфты комбинаторлық кластарды құрайды. Бұл жағдайда биективті изоморфизм жазық графтың дуалдығы арқылы беріледі: триангуляцияны әрбір көпбұрыш қабырғасы үшін жапыраққа, әрбір үшбұрышқа ішкі түйінге және бір-біріне жақын жатқан екі (көпбұрыш қабырғасы?) немесе үшбұрыштар үшін қабырғаға айналдыруға болады.
The counting sequence of a combinatorial class is the sequence of the numbers of elements of size i for i = 0, 1, 2, ; it may also be described as a generating function that has these numbers as its coefficients. The counting sequences of combinatorial classes are the main subject of study of enumerative combinatorics. Two combinatorial classes are said to be isomorphic if they have the same numbers of objects of each size, or equivalently, if their counting sequences are the same. Frequently, once two combinatorial classes are known to be isomorphic, a bijective proof of this equivalence is sought; such a proof may be interpreted as showing that the objects in the two isomorphic classes are cryptomorphic to each other. For instance, the triangulations of regular polygons (with size given by the number of sides of the polygon, and a fixed choice of polygon to triangulate for each size) and the set of unrooted binary plane trees (up to graph isomorphism, with a fixed ordering of the leaves, and with size given by the number of leaves) are both counted by the Catalan numbers, so they form isomorphic combinatorial classes. A bijective isomorphism in this case is given by planar graph duality: a triangulation can be transformed bijectively into a tree with a leaf for each polygon edge, an internal node for each triangle, and an edge for each two (polygon edges?) or triangles that are adjacent to each other.
Аналитикалық комбинаторика
Комбинаторлық түрлер теориясы және оның аналитикалық комбинаторикаға қатысты кеңейтілуі, көптеген маңызды комбинаторлық класс(тар)ды сипаттауға, бұрын анықталған класс(тар)дың комбинацияларынан жаңа класс(тар) құруға және олардың сандық тізбектерін автоматты түрде шығаруға мүмкіндік беретін тілді ұсынады.
The theory of combinatorial species and its extension to analytic combinatorics provide a language for describing many important combinatorial classes, constructing new classes from combinations of previously defined ones, and automatically deriving their counting sequences.
Пермутация үлгілері
Пермутация үлгілерін зерттеуде, пермутация ұзындығы бойынша саналатын пермутация кластарының комбинаторлық класы Вильф класы деп аталады. Нақты пермутация кластарының санын есептеу, көрінетін ешқандай байланысы жоқ пермутация кластарының сану тізбектерінде күтпеген теңдіктерді көрсетті.
In the study of permutation patterns, a combinatorial class of permutation classes, enumerated by permutation length, is called a Wilf class. The study of enumerations of specific permutation classes has turned up unexpected equivalences in counting sequences of seemingly unrelated permutation classes.