Кіріспе
Топ әрекетінің орбиталарының саны үшін формула Бернсайд леммасы, кейде Бернсайдтың санау теоремасы, Коши-Фробень леммасы немесе орбиталарды санау теоремасы деп те аталады, бұл математикалық объектілерді санағанда симметрияны ескере алу үшін жиі қолданылатын топтар теориясының нәтижесі. Оны Огюстен Луи Коши және Фердинанд Георг Фробеньус ашқан, ал Уильям Бернсайд оны сілтеме келтіргеннен кейін кеңінен танымал болды. Бұл нәтиже симметрия тобының кейбір объектілерге әсер етуінен туындаған орбиталарды есептейді: яғни, бір-біріне симметриялы объектілерді бірдей санап, ерекше объектілердің санын анықтайды; немесе симметриялық эквиваленттілік қатынасына дейін ерекше объектілерді санауды қамтиды; немесе тек канондық түрдегі объектілерді санауға мүмкіндік береді. Мысалы, белгілі бір типтегі органикалық қосылыстарды сипаттағанда, оларды кеңістіктегі бұрылу симметриясына дейін қарастырады: берілген молекуланың әртүрлі бұрылған бейнелері химиялық тұрғыдан бірдей болады. (Дегенмен, айнадағы бейне басқа қосылысты білдіруі мүмкін.) Формальды түрде, G – X жиынына әрекет ететін шекті топ болсын. G-дегі әрбір g үшін, Xg жиынтығы g-мен бекітілген X жиынының элементтерін білдіреді (g-ге қатысты сол инвариант): яғни, Xg = { x ∈ X | g. x = x }. Бернсайд леммасы орбиталар саны үшін, |X/G| деп белгіленетін, келесі формуланы тұрақтылайды:
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, or the orbit counting theorem, is a result in group theory that is often useful in taking account of symmetry when counting mathematical objects. It was discovered by Augustin Louis Cauchy and Ferdinand Georg Frobenius, and became well known after William Burnside quoted it. The result enumerates orbits of a symmetry group acting on some objects: that is, it counts distinct objects, considering objects symmetric to each other as the same; or counting distinct objects up to a symmetry equivalence relation; or counting only objects in canonical form. For example, in describing possible organic compounds of certain type, one considers them up to spatial rotation symmetry: different rotated drawings of a given molecule are chemically identical. (However a mirror reflection might give a different compound.) Formally, let G be a finite group that acts on a set X. For each g in G, let Xg denote the set of elements in X that are fixed by g (left invariant by g): that is, Xg = { x ∈ X | g. x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:
Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G. For an infinite group G, there is still a bijection:
Осылайша, орбиталар саны (табиғи сан немесе +∞) G элементімен бекітілген нүктелердің орташа санына тең. Шесіз топ G үшін де биекция бар:
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, or the orbit counting theorem, is a result in group theory that is often useful in taking account of symmetry when counting mathematical objects. It was discovered by Augustin Louis Cauchy and Ferdinand Georg Frobenius, and became well known after William Burnside quoted it. The result enumerates orbits of a symmetry group acting on some objects: that is, it counts distinct objects, considering objects symmetric to each other as the same; or counting distinct objects up to a symmetry equivalence relation; or counting only objects in canonical form. For example, in describing possible organic compounds of certain type, one considers them up to spatial rotation symmetry: different rotated drawings of a given molecule are chemically identical. (However a mirror reflection might give a different compound.) Formally, let G be a finite group that acts on a set X. For each g in G, let Xg denote the set of elements in X that are fixed by g (left invariant by g): that is, Xg = { x ∈ X | g. x = x }. Burnside's lemma asserts the following formula for the number of orbits, denoted |X/G|:
Thus the number of orbits (a natural number or +∞) is equal to the average number of points fixed by an element of G. For an infinite group G, there is still a bijection:
Қалқалар
3 ұзындығы бар 8 мүмкін биттік тізбек бар, бірақ тізбек соңдарын байланыстыру 3 ұзындығы бар 4 түрлі 2 түсті әшекейлерді ғана береді, олар 000, 001, 011, 111 канондық түрлерімен берілген: қалған тізбектер 100 және 010 айналу арқылы 001-ге тең, ал 110 және 101 011-ге тең. Яғни, айналу эквиваленттігі X тізбектерін төрт орбитаға бөледі: Бернсайд формуласы айналу санын пайдаланады, ол 3 нөлдік айналуды қоса алғанда, және әр айналымда өзгермеген биттік тізбектердің санын пайдаланады. Барлық 8 биттік векторлар нөлдік айналымда өзгермейді, ал екеуі (000 және 111) қалған екі айналымда өзгермейді. Сондықтан орбиталар саны: Ұзындығы 4 үшін 16 мүмкін биттік тізбек бар; 4 айналым; нөлдік айналым барлық 16 тізбекті өзгертусіз қалдырады; 1 айналым және 3 айналым әрқайсысы екі тізбекті өзгертусіз қалдырады (0000 және 1111); 2 айналым 4 биттік тізбекті өзгертусіз қалдырады (0000, 0101, 1010, 1111). Осылайша, түрлі әшекейлердің саны: , 0000, 0001, 0011, 0101, 0111, 1111 канондық түрлерімен бейнеленген. n бит және k түс үшін жалпы жағдайды әшекей полиномы береді.
For length 4, there are 16 possible bit strings; 4 rotations; the null rotation leaves all 16 strings unchanged; the 1 rotation and 3 rotation each leave two strings unchanged (0000 and 1111); the 2 rotation leaves 4 bit strings unchanged (0000, 0101, 1010, 1111). The number of distinct necklaces is thus: , represented by the canonical forms 0000, 0001, 0011, 0101, 0111, 1111. The general case of n bits and k colors is given by a necklace polynomial.
Санақтау мен өндіру
Бернсайд леммасы ерекше нысандарды санайды, бірақ оларды құрастырмайды. Жалпы, изоморфизмді қабылдамау арқылы комбинаторлық генерация x нысандарының g симметрияларын қарастырады. Бірақ g.x = x екенін тексеру орнына, g.x әлі жасалмағанын тексереді. Мұны іске асырудың бір жолы – g.x лексикографиялық тұрғыдан x-тен кіші емес екенін тексеру, әр эквиваленттік кластың лексикографиялық тұрғыдан ең кіші мүшесін кластың канондық түрі ретінде пайдалану. Мұндай техникамен жасалған нысандарды санау Бернсайд леммасының дұрыс қолданылғанын растай алады.
Тарих: Бернсайдтің емес леммасы
Уильям Бернсайд бұл лемманы 1897 жылы шекті топтар туралы кітабында айтып, дәлелдеді, оны Фробениусқа есептеп, бірақ одан бұрын 1845 жылы Коши бұл формуламен таныс болған. Сондықтан бұл лемма кейде Бернсайдке жатпайтын лемма деп аталады. Ғылыми жаңалықтарға қате атау беру Стиглердің есімдес заңы деп аталады.