Кіріспе
Комбинаторлық математикада циклдық индекс – бірнеше айнымалыдағы полином, ол жиынға пермутациялар тобының қалай әсер ететіні туралы ақпаратты коэффициенттер мен экспоненттер арқылы оңай оқуға мүмкіндік беретіндей құрылымдалған. Бұл ақпаратты алгебралық формада ықшам түрде сақтау әдісі комбинаторлық санауда жиі қолданылады. Объектілердің шекті жиынтығының әр пермутациясы π осы жиынды циклдарға бөледі; π циклдық индексінің мономиалы a1, a2, ... айнымалыларындағы мономиал болып табылады, ол осы бөліністің циклдық түрін сипаттайды: ai экспоненті – i өлшемді π циклдарының саны. Пермутация тобының циклдық индекс полиномы – оның элементтерінің циклдық индекс мономияларының орташа мәні. "Циклдық индикатор" термині кейде циклдық индекс орнына қолданылады. Пермутация тобының циклдық индекс полиномын білгенде, топтың әрекетіне байланысты эквиваленттілік кластарын санауға болады. Бұл Поляның санау теоремасының негізгі бөлігі. Осы полиномдарға формальды алгебралық және дифференциалдық операцияларды орындап, содан кейін нәтижелерді комбинаторлық тұрғыдан түсіндіру – түрлер теориясының негізгі мәселесі.
Пермутация топтары мен топтық іс-қимылдар
Кез келген жиын X-тен өзіне біржақты сәйкестік X-тің пермутациясы деп аталады, ал X-тің барлық пермутацияларының жиыны бейнелеулердің композициясы бойынша топты құрайды, бұл X-тің симметриялық тобы деп аталады және Sym(X) деп белгіленеді. Sym(X) тобының кез келген подтобы X дәрежесіндегі пермутациялық топ деп аталады. G абстрактілі тобы болсын, G-ден Sym(X)-ке дейінгі φ топтық гомоморфизмі болсын. Бейне φ(G) – пермутациялық топ. Топтық гомоморфизмді G тобының X жиынында "әрекет етуіне" мүмкіндік беретін құрал ретінде қарастыруға болады (G элементтерімен байланысты пермутацияларды қолдану арқылы). Мұндай топтық гомоморфизм формальды түрде топтық әрекет деп аталады, ал гомоморфизмнің бейнесі G-дің пермутациялық өрнегі болып табылады. Берілген топтың әртүрлі әрекеттерге сәйкес келетін көптеген әртүрлі пермутациялық өрнектері болуы мүмкін. G тобы X жиынында әрекет етеді деп есептейік (яғни, топтық әрекет бар). Комбинаторлық қолданыстарда қызығушылық X жиынына бағытталған; мысалы, X-тегі нысандарды санау және G-мен инвариантты болатын қандай құрылымдарды сақтауға болатынын білу. Мұндай жағдайда пермутациялық топтармен жұмыс істеу көп нәрсені жоғалтпайды, сондықтан осы қолданыстарда топ қарастырылғанда, ол топтың пермутациялық өрнегі болып табылады, сондықтан топтық әрекетті көрсету қажет. Алгебраистер, керісінше, топтардың өзіне көбірек қызығушылық танытады және топтық әрекеттердің ядроларымен көбірек айналысады, олар топтан оның пермутациялық өрнегіне өту кезінде қаншалықты жоғалатынын өлшейді.
Пермутациялардың дисконт циклінің бейнеленуі
Шекті пермутациялар көбінесе X = {1, 2, ..., n} жиынындағы топтық әрекеттер ретінде бейнеленеді. Бұл жағдайда пермутация екі жолды нотация арқылы көрсетілуі мүмкін. Мысалы,
corresponds to a bijection on X = {1, 2, 3, 4, 5} which sends 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 and 5 ↦ 1. This can be read off from the columns of the notation. When the top row is understood to be the elements of X in an appropriate order, only the second row need be written. In this one line notation, our example would be [2 3 4 5 1]. This example is known as a cyclic permutation because it "cycles" the numbers around, and a third notation for it would be (1 2 3 4 5). This cycle notation is to be read as: each element is sent to the element on its right, but the last element is sent to the first one (it "cycles" to the beginning). With cycle notation, it does not matter where a cycle starts, so (1 2 3 4 5) and (3 4 5 1 2) and (5 1 2 3 4) all represent the same permutation. The length of a cycle is the number of elements in the cycle. Not all permutations are cyclic permutations, but every permutation can be written as a product of disjoint (having no common element) cycles in essentially one way. As a permutation may have fixed points (elements that are unchanged by the permutation), these will be represented by cycles of length one. For example:
This permutation is the product of three cycles, one of length two, one of length three, and a fixed point. The elements in these cycles are disjoint subsets of X and form a partition of X. The cycle structure of a permutation can be coded as an algebraic monomial in several (dummy) variables in the following way: a variable is needed for each distinct cycle length of the cycles that appear in the cycle decomposition of the permutation. In the previous example there were three different cycle lengths, so we will use three variables, a1, a2 and a3 (in general, use the variable ak to correspond to length k cycles). The variable ai will be raised to the ji (g) power where ji (g) is the number of cycles of length i in the cycle decomposition of permutation g. We can then associate the cycle index monomial
to the permutation g. The cycle index monomial of our example would be a1a2a3, while the cycle index monomial of the permutation (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) would be a1a22a42.
X = {1, 2, 3, 4, 5} жиынындағы биекцияға сәйкес келеді, ол 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 және 5 ↦ 1 жібереді. Бұл нотацияның бағандарынан оқуға болады. Егер жоғарғы қатар X жиынының элементтерін тиісті ретпен көрсетсе, онда тек екінші қатарды жазу жеткілікті. Бір жолды нотацияда бұл мысал [2 3 4 5 1] болады. Бұл мысал циклдық пермутация деп аталады, себебі ол сандарды «циклмен» ауыстырады, ал үшінші жазу түрі (1 2 3 4 5) болады. Бұл циклдық нотацияны былай оқу керек: әрбір элемент оң жақтағы элементке жіберіледі, бірақ соңғы элемент біріншіге жіберіледі (ол «циклға» оралады). Циклдық нотацияда циклдің басталу орны маңызды емес, сондықтан (1 2 3 4 5), (3 4 5 1 2) және (5 1 2 3 4) – бәрі де бір пермутацияны көрсетеді. Циклдың ұзындығы – циклдегі элементтердің саны. Барлық пермутациялар циклдық пермутациялар емес, бірақ кез келген пермутацияны өзара байланыссыз (ортақ элементі жоқ) циклдердің көбейтіндісі түрінде жазуға болады. Пермутацияда өзгермейтін элементтер (тұрақты нүктелер) болуы мүмкін, олар бірлік ұзындығы бар циклдармен көрсетіледі. Мысалы:
corresponds to a bijection on X = {1, 2, 3, 4, 5} which sends 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 and 5 ↦ 1. This can be read off from the columns of the notation. When the top row is understood to be the elements of X in an appropriate order, only the second row need be written. In this one line notation, our example would be [2 3 4 5 1]. This example is known as a cyclic permutation because it "cycles" the numbers around, and a third notation for it would be (1 2 3 4 5). This cycle notation is to be read as: each element is sent to the element on its right, but the last element is sent to the first one (it "cycles" to the beginning). With cycle notation, it does not matter where a cycle starts, so (1 2 3 4 5) and (3 4 5 1 2) and (5 1 2 3 4) all represent the same permutation. The length of a cycle is the number of elements in the cycle. Not all permutations are cyclic permutations, but every permutation can be written as a product of disjoint (having no common element) cycles in essentially one way. As a permutation may have fixed points (elements that are unchanged by the permutation), these will be represented by cycles of length one. For example:
This permutation is the product of three cycles, one of length two, one of length three, and a fixed point. The elements in these cycles are disjoint subsets of X and form a partition of X. The cycle structure of a permutation can be coded as an algebraic monomial in several (dummy) variables in the following way: a variable is needed for each distinct cycle length of the cycles that appear in the cycle decomposition of the permutation. In the previous example there were three different cycle lengths, so we will use three variables, a1, a2 and a3 (in general, use the variable ak to correspond to length k cycles). The variable ai will be raised to the ji (g) power where ji (g) is the number of cycles of length i in the cycle decomposition of permutation g. We can then associate the cycle index monomial
to the permutation g. The cycle index monomial of our example would be a1a2a3, while the cycle index monomial of the permutation (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) would be a1a22a42.
Бұл пермутация үш циклдың көбейтіндісі болып табылады: біреуінің ұзындығы екі, біреуінің үш, ал үшіншісі тұрақты нүкте. Бұл циклдардағы элементтер X жиынының бөлек кіші жиындарын құрайды және X жиынының бөлінісін қалыптастырады. Пермутацияның циклдық құрылымын бірнеше (фиктивті) айнымалылардағы алгебралық мономиал ретінде келесідей кодтауға болады: пермутацияның циклдық жіктелуінде кездесетін әр түрлі цикл ұзындығы үшін бір айнымалы қажет. Алдыңғы мысалда үш түрлі цикл ұзындығы болды, сондықтан үш айнымалы қолданамыз: a1, a2 және a3 (жалпы жағдайда, k ұзындығы циклдарға сәйкес келетін ak айнымалысын қолданамыз). ai айнымалысы g пермутациясының циклдық жіктелуіндегі i ұзындығы циклдардың саны ji(g) дәрежесіне көтеріледі. Содан кейін циклдық индекс мономиалын g пермутациясымен байланыстыра аламыз. Мысалымыз үшін циклдық индекс мономиалы a1a2a3 болады, ал (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) пермутациясы үшін циклдық индекс мономиалы a1a22a42 болады.
corresponds to a bijection on X = {1, 2, 3, 4, 5} which sends 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 and 5 ↦ 1. This can be read off from the columns of the notation. When the top row is understood to be the elements of X in an appropriate order, only the second row need be written. In this one line notation, our example would be [2 3 4 5 1]. This example is known as a cyclic permutation because it "cycles" the numbers around, and a third notation for it would be (1 2 3 4 5). This cycle notation is to be read as: each element is sent to the element on its right, but the last element is sent to the first one (it "cycles" to the beginning). With cycle notation, it does not matter where a cycle starts, so (1 2 3 4 5) and (3 4 5 1 2) and (5 1 2 3 4) all represent the same permutation. The length of a cycle is the number of elements in the cycle. Not all permutations are cyclic permutations, but every permutation can be written as a product of disjoint (having no common element) cycles in essentially one way. As a permutation may have fixed points (elements that are unchanged by the permutation), these will be represented by cycles of length one. For example:
This permutation is the product of three cycles, one of length two, one of length three, and a fixed point. The elements in these cycles are disjoint subsets of X and form a partition of X. The cycle structure of a permutation can be coded as an algebraic monomial in several (dummy) variables in the following way: a variable is needed for each distinct cycle length of the cycles that appear in the cycle decomposition of the permutation. In the previous example there were three different cycle lengths, so we will use three variables, a1, a2 and a3 (in general, use the variable ak to correspond to length k cycles). The variable ai will be raised to the ji (g) power where ji (g) is the number of cycles of length i in the cycle decomposition of permutation g. We can then associate the cycle index monomial
to the permutation g. The cycle index monomial of our example would be a1a2a3, while the cycle index monomial of the permutation (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) would be a1a22a42.
Мысал
Евклид жазықтығындағы квадраттың айналу симметриясының G тобын қарастырайық. Оның элементтері тек қана квадраттың бұрыштарының бейнелерімен анықталады. Осы бұрыштарға 1, 2, 3 және 4 деп белгі қойып (мысалы, сағат тілі бойынша) G элементтерін X = {1,2,3,4} жиынының пермутациялары ретінде көрсетуге болады. G-дің пермутациялық бейнелеуі төрт пермутациядан тұрады: (1 4 3 2), (1 3)(2 4), (1 2 3 4) және e = (1)(2)(3)(4), олар сәйкесінше 90°, 180°, 270° және 360° сағат тілі бойынша айналымдарды көрсетеді. Ескеріңіз, e сәйкестік пермутациясы G-дің осы бейнелеуіндегі тұрақты нүктелері бар жалғыз пермутация болып табылады. Абстрактіл топ ретінде G циклдік топ C4 деп аталады, ал оның бұл пермутациялық бейнелеуі оның тұрақты бейнелеуі болып табылады. Цикл индексінің мономиалдары сәйкесінше a4, a22, a4 және a14 болып табылады. Осылайша, осы пермутация тобының цикл индексі:
C4 тобы X элементтерінің ретсіз жұптарына да табиғи түрде әсер етеді. Кез келген g пермутациясы {x,y} → {x g, y g} (мұнда x g – g пермутациясы астындағы x элементінің бейнесі) жібереді. X жиыны енді {A, B, C, D, E, F} болып табылады, мұнда A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3} және F = {2,4}. Бұл элементтерді квадраттың қабырғалары мен диагональдары ретінде немесе мүлдем басқа жағдайда толық K4 графигінің жиектері ретінде қарастыруға болады. Осы жаңа жиынтыққа әсер етіп, төрт топ элементтері (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F) және e = (A)(B)(C)(D)(E)(F) арқылы бейнеленеді, ал бұл әрекеттің цикл индексі:
C4 тобы X элементтерінің реттелген жұптарына да сол табиғи жолмен әсер ете алады. Кез келген g пермутациясы (x, y) → (x g, y g) жібереді (осы жағдайда біз (x, x) түріндегі жұптарды да қарастырамыз). X элементтерін толық D4 диграфтың доғалары ретінде қарастыруға болады (әрбір түбегінде өзіне циклдер бар). Бұл жағдайда цикл индексі:
Жекелік тобы En
Бұл топта барлық элементтерді өзгеріссіз қалдыратын бір ғана мүмкіндік бар (бұл табиғи әрекет болуы тиіс).
Циклдік топ Cn
Циклдік топ, Cn – дұрыс n қабыршалы полигонның айналу тобы, яғни шеңбер бойында тең арақашықтықта орналасқан n элемент. Бұл топта n-нің әр d бөлгіші үшін d реттік элементтердің φ(d) саны бар, мұнда φ(d) – Эйлер φ функциясы, d-ден кіші және d-мен өзара жай сандардың санын көрсетеді. Cn тобының тұрақты бейнелеуінде d реттік пермутациясы n/d ұзындығы d циклдерден тұрады, демек:
Диэдрлік топ Dn
Диэдрлік топ циклдік топқа ұқсас, бірақ сонымен қатар кері бұруларды да қамтиды. Оның табиғи әрекетінде,