Бернсайдын лемм / Пойагийн тоолох теорем¶

Бернсайдын лемм¶

Бернсайдын лемм-ийг 1897 онд Бернсайд томьёолж баталсан боловч түүхэн хувьд үүнийг 1887 онд Фробениус, бүр эрт 1845 онд Коши аль хэдийн нээсэн. Тиймээс үүнийг заримдаа Коши-Фробениусын лемм гэж бас нэрлэдэг.

Бернсайдын лемм нь бидэнд дотоод тэгш хэм дээр үндэслэн олонлог дахь эквивалент ангийн тоог тоолох боломж олгодог.

Объект ба дүрслэл¶

Бид объектын тоо ба дүрслэлийн тоог тодорхой ялгах ёстой.

Өөр өөр дүрслэл ижил объектод харгалзаж болох боловч мэдээж дурын дүрслэл яг нэг объектод харгалзана. Ингэснээр бүх дүрслэлийн олонлог эквивалент ангиудад хуваагдана. Бидний даалгавар бол объектын тоо буюу эквивалентаар эквивалент ангийн тоог тооцоолох явдал юм. Дараах жишээ объект ба дүрслэлийн ялгааг илүү тодорхой болгоно.

Жишээ: хоёртын модыг будах¶

Бидэнд дараах бодлого байна гэж бодъё. Бид $n$ оройтой үндэстэй хоёртын модыг хоёр өнгөөр будах аргын тоог тоолох ёстой бөгөөд орой бүрд бид зүүн ба баруун хүүхдийг ялгахгүй.

Энд объектуудын олонлог нь модны өөр өөр будалтуудын олонлог юм.

Одоо бид дүрслэлүүдийн олонлогийг тодорхойлно. Будалтын дүрслэл гэдэг нь орой бүрд өнгө оноодог $f(v)$ функц юм (энд бид $0$ ба $1$ өнгийг ашиглана). Дүрслэлүүдийн олонлог нь ийм төрлийн бүх боломжит функцийг агуулах олонлог бөгөөд түүний хэмжээ $2^n$-тэй тэнцүү байх нь ойлгомжтой.

Үүний зэрэгцээ бид энэ олонлогийг эквивалент ангиудад хуваах хуваалтыг нэвтрүүлнэ.

Жишээ нь $n = 3$ гэж үзье, мод нь $1$ үндэс ба түүний хоёр хүүхэд $2$, $3$-аас тогтоно. Тэгвэл дараах $f_1$ ба $f_2$ функцийг эквивалент гэж үзнэ.

$$\begin{array}{ll} f_1(1) = 0 & f_2(1) = 0\\ f_1(2) = 1 & f_2(2) = 0\\ f_1(3) = 0 & f_2(3) = 1 \end{array}$$

Инвариант сэлгэмэл¶

Яагаад энэ хоёр $f_1$ ба $f_2$ функц нэг эквивалент ангид харьяалагдах вэ? Зөн совингоор энэ нь ойлгомжтой — бид $1$ оройн хүүхдүүд буюу $2$, $3$ оройг дахин байрлуулж болох ба $f_1$ функцийн ийм хувиргалтын дараа энэ нь $f_2$-тэй давхцана.

Гэвч албан ёсоор энэ нь дараах байх инвариант сэлгэмэл $\pi$ (өөрөөр хэлбэл объектыг өөрийг нь биш, зөвхөн түүний дүрслэлийг өөрчилдөг сэлгэмэл) оршин байна гэсэн үг:

$$f_2 \pi \equiv f_1$$

Тэгэхээр объектуудын тодорхойлолтоос эхлэн бид бүх инвариант сэлгэмэл буюу дүрслэлд сэлгэмэлийг хэрэглэхэд объектыг өөрчилдөггүй бүх сэлгэмэлийг олж болно. Дараа нь бид инвариант сэлгэмэл бүрийн хувьд $f_2 \pi \equiv f_1$ нөхцөлийг (эсвэл эквивалентаар $f_1 \pi \equiv f_2$) шалгах замаар $f_1$ ба $f_2$ хоёр функц эквивалент эсэхийг (өөрөөр хэлбэл тэдгээр нь ижил объектод харгалзах эсэхийг) шалгаж болно. Хэрэв нөхцөл хангагдах дор хаяж нэг сэлгэмэл олдвол $f_1$ ба $f_2$ эквивалент, эс бөгөөс тэдгээр нь эквивалент биш.

Объектын тодорхойлолтын хувьд ийм бүх инвариант сэлгэмэлийг олох нь Бернсайдын лемм болон Пойагийн тоолох теорем хоёуланг хэрэглэх гол алхам юм. Эдгээр инвариант сэлгэмэл тодорхой бодлогоос хамаардаг нь тодорхой бөгөөд тэдгээрийг олох нь зөн совингийн үндэслэл дээр суурилсан цэвэр эвристик процесс юм. Гэвч ихэнх тохиолдолд хэдэн "суурь" сэлгэмэлийг гараар олоход хангалттай бөгөөд эдгээрээр бусад бүх сэлгэмэлийг үүсгэж болно (мөн ажлын энэ хэсгийг компьютерт шилжүүлж болно).

Инвариант сэлгэмэлүүд бүлэг үүсгэдгийг ойлгоход хэцүү биш, учир нь инвариант сэлгэмэлүүдийн үржвэр (композиц) нь дахин инвариант сэлгэмэл болно. Инвариант сэлгэмэлүүдийн бүлэг-ийг $G$ гэж тэмдэглэнэ.

Леммийн батламж¶

Леммийг томьёолохын тулд бидэнд алгебрын өөр нэг тодорхойлолт хэрэгтэй. Сэлгэмэл $\pi$-ийн хөдлөшгүй цэг $f$ гэдэг нь энэ сэлгэмэлийн дор инвариант байх элемент юм: $f \equiv f \pi$. Жишээ нь манай жишээнд хөдлөшгүй цэгүүд нь $\pi$ сэлгэмэлийг хэрэглэхэд өөрчлөгддөггүй (өөрөөр хэлбэл функцийн тэнцлийн албан ёсны утгаар өөрчлөгддөггүй) будалтуудад харгалзах тэдгээр $f$ функцүүд юм. $\pi$ сэлгэмэлийн хөдлөшгүй цэгийн тоо-г $I(\pi)$ гэж тэмдэглэнэ.

Тэгвэл Бернсайдын лемм дараах байдалтай: эквивалент ангийн тоо нь $G$ бүлгийн бүх сэлгэмэлийн хувьд хөдлөшгүй цэгүүдийн тоонуудын нийлбэрийг энэ бүлгийн хэмжээнд хуваасантай тэнцүү:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

Бернсайдын лемм өөрөө практикт ашиглахад тийм ч тохиромжтой биш ч ($I(\pi)$ утгыг хэрхэн хурдан хайхыг тодорхойгүй), эквивалент ангийг тооцоолох санаа суурилдаг математик мөн чанарыг хамгийн тодорхой илчилдэг.

Бернсайдын леммийн баталгаа¶

Энд тайлбарласан Бернсайдын леммийн баталгаа нь практик хэрэглээний хувьд чухал биш тул анх уншихад алгасаж болно.

Энд байгаа баталгаа нь мэдэгдэж буй хамгийн энгийн бөгөөд бүлгийн онолыг ашигладаггүй. Баталгааг Kenneth P. Bogart 1991 онд нийтэлсэн.

Бид дараах батламжийг батлах хэрэгтэй:

$$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

Баруун тал дахь утга нь "инвариант хос" $(f, \pi)$ буюу $f \pi \equiv f$ байх хосуудын тооноос өөр зүйл биш. Бид нийлбэрийн дарааллыг өөрчилж болох нь ойлгомжтой. Бид нийлбэрийг бүх элемент $f$-ээр давтуулж, $J(f)$ буюу $f$ нь хөдлөшгүй цэг байх сэлгэмэлийн тоогоор нийлбэрлэнэ.

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Энэ томьёог батлахын тулд бид баганыг нь бүх $f_i$ функцээр, мөрийг нь бүх $\pi_j$ сэлгэмэлээр тэмдэглэсэн хүснэгт зохионо. Мөн бид нүднүүдийг $f_i \pi_j$-ээр дүүргэнэ. Хэрэв бид энэ хүснэгт дэх баганыг олонлог гэж харвал зарим нь давхцах ба энэ нь эдгээр баганад харгалзах $f$ функцүүд мөн эквивалент гэсэн үг. Тиймээс ялгаатай (олонлог болох) баганын тоо нь ангийн тоотой тэнцүү. Дашрамд хэлэхэд бүлгийн онолын үүднээс $f_i$-ээр тэмдэглэгдсэн багана нь энэ элементийн орбит юм. Эквивалент элементүүдийн хувьд орбитууд давхцах ба орбитын тоо нь яг ангийн тоог өгнө.

Тиймээс хүснэгтийн баганууд эквивалент ангиудад задарна. Нэг ангийг тогтоож, түүн дэх баганыг харцгаая. Эхлээд эдгээр багана зөвхөн эквивалент ангийн $f_i$ элементүүдийг агуулж болохыг тэмдэглэе (эс бөгөөс ямар нэг $\pi_j$ сэлгэмэл функцүүдийн нэгийг өөр эквивалент анги руу зөөсөн байх ба бид зөвхөн инвариант сэлгэмэлийг л харж байгаа тул энэ нь боломжгүй). Хоёрдугаарт $f_i$ элемент бүр багана бүрд ижил тооны удаа гарч ирнэ (энэ нь мөн баганууд эквивалент элементүүдэд харгалзах баримтаас гарна). Эндээс бид нэг эквивалент анги доторх бүх багана бие биетэйгээ мультиолонлог болох давхцахыг дүгнэж болно.

Одоо дурын элемент $f$-г тогтооё. Нэг талаас энэ нь өөрийн баганад яг $J(f)$ удаа гарна (тодорхойлолтоор). Нөгөө талаас нэг эквивалент анги доторх бүх багана мультиолонлог болох ижил. Тиймээс өгөгдсөн эквивалент ангийн багана бүрд дурын элемент $g$ яг $J(g)$ удаа гарна.

Тиймээс хэрэв бид эквивалент анги тус бүрээс дурын нэг багана авч, тэдгээр дэх элементийн тоог нийлбэрлэвэл нэг талаас $|\text{Classes}| \cdot |G|$ (зүгээр л баганын тоог мөрийн тоогоор үржүүлж), нөгөө талаас бүх $f$-ийн хувьд $J(f)$ хэмжигдэхүүнүүдийн нийлбэрийг (энэ нь өмнөх бүх үндэслэлээс гарна) олж авна:

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Пойагийн тоолох теорем¶

Пойагийн тоолох теорем нь Бернсайдын леммийн ерөнхийлөл бөгөөд эквивалент ангийн тоог олох илүү тохиромжтой хэрэгслийг мөн өгдөг. Энэ теоремыг Пойагаас өмнө 1927 онд Редфилд аль хэдийн нээсэн боловч түүний нийтлэл математикчдын анхаарлаас гадуур үлдсэнийг тэмдэглэх нь зүйтэй. Пойа 1937 онд бие даан ижил үр дүнд хүрсэн бөгөөд түүний нийтлэл илүү амжилттай байсан.

Энд бид Пойагийн тоолох теоремын зөвхөн практикт маш ашигтай болох онцгой тохиолдлыг авч үзнэ. Теоремын ерөнхий томьёог авч үзэхгүй.

$\pi$ сэлгэмэл дэх циклийн тоог $C(\pi)$ гэж тэмдэглэнэ. Тэгвэл дараах томьёо (Пойагийн тоолох теоремын онцгой тохиолдол) биелнэ:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$$

$k$ нь дүрслэлийн элемент бүрийн авч болох утгын тоо бөгөөд хоёртын модыг будах тохиолдолд энэ нь $k = 2$ байх болно.

Баталгаа¶

Энэ томьёо нь Бернсайдын леммийн шууд дагавар юм. Үүнийг олохын тулд бид зүгээр л леммд гарч ирдэг $I(\pi)$-ийн шууд илэрхийллийг олох хэрэгтэй. $I(\pi)$ нь $\pi$ сэлгэмэл дэх хөдлөшгүй цэгийн тоо гэдгийг эргэн санаарай.

Тиймээс бид $\pi$ сэлгэмэл ба ямар нэг элемент $f$-г авч үзнэ. $\pi$-г хэрэглэх явцад $f$ дэх элементүүд сэлгэмэл дэх циклүүдээр дамжин хөдөлнө. Үр дүн нь $f \equiv f \pi$ болох ёстой тул нэг циклээр хүрсэн элементүүд бүгд тэнцүү байх ёстой. Үүний зэрэгцээ өөр өөр циклүүд бие даасан. Тиймээс сэлгэмэл $\pi$-ийн цикл бүрийн хувьд бид нэг утга ($k$ боломжийн дундаас) сонгож болох ба ингэснээр бид хөдлөшгүй цэгийн тоог олж авна:

$$I(\pi) = k^{C(\pi)}$$

Хэрэглээ: Зүүлт будах¶

"Зүүлт" бодлого бол сонгодог комбинаторикийн бодлогуудын нэг юм. Даалгавар нь $n$ сувднаас бүрдэх, тус бүр нь $k$ өнгийн аль нэгээр будагдаж болох өөр өөр зүүлтний тоог тоолох явдал юм. Хоёр зүүлтийг харьцуулахдаа тэдгээрийг эргүүлж болох боловч урвуулж болохгүй (өөрөөр хэлбэл циклик шилжүүлэлт зөвшөөрөгдөнө).

Энэ бодлогод бид инвариант сэлгэмэлүүдийн бүлгийг шууд олж болно:

$$\begin{align} \pi_0 &= 1 2 3 \dots n\\ \pi_1 &= 2 3 \dots n 1\\ \pi_2 &= 3 \dots n 12\\ &\dots\\ \pi_{n-1} &= n 1 2 3\dots\end{align}$$

$C(\pi_i)$-г тооцоолох шууд томьёог олъё. Эхлээд $\pi_i$ сэлгэмэл нь $j$-р байрлалд $i + j$ ($n$ модулиар авсан) утгатай болохыг тэмдэглэе. $\pi_i$-ийн циклийн бүтцийг шалгавал. Бид $1$ нь $1 + i$ рүү, $1 + i$ нь $1 + 2i$ рүү, тэр нь $1 + 3i$ рүү гэх мэтчилэн $1 + k n$ хэлбэрийн тоонд хүрэх хүртэл явахыг харна. Үлдсэн элементүүдийн хувьд ижил төстэй батламж хийж болно. Иймээс бид бүх цикл ижил урттай буюу $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$ байхыг харна. Тиймээс $\pi_i$ дэх циклийн тоо нь $\gcd(i, n)$-тэй тэнцүү байна.

Эдгээр утгыг Пойагийн тоолох теоремд орлуулбал бид шийдийг олж авна:

$$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$$

Та энэ томьёог ийм хэлбэрээр үлдээж болох буюу бүр илүү хялбарчилж болно. Нийлбэрийг $n$-ийн бүх хуваагчаар давтахаар шилжүүлье. Анхны нийлбэрт олон эквивалент гишүүн байна: хэрэв $i$ нь $n$-ийн хуваагч биш бол ийм хуваагчийг $\gcd(i, n)$-г тооцоолсны дараа олж болно. Тиймээс хуваагч $d ~|~ n$ бүрийн хувьд түүний гишүүн $k^{\gcd(d, n)} = k^d$ нийлбэрт олон удаа гарч ирэх ба өөрөөр хэлбэл бодлогын хариуг

$$\frac{1}{n} \sum_{d ~|~ n} C_d k^d,$$

гэж дахин бичиж болно, энд $C_d$ нь $\gcd(i, n) = d$ байх ийм $i$ тооны тоо юм. Бид энэ утгын шууд илэрхийллийг олж болно. Ийм дурын $i$ тоо нь $\gcd(j, n / d) = 1$ байх $i = d j$ хэлбэртэй (эс бөгөөс $\gcd(i, n) > d$). Тиймээс бид ийм зан төлөвтэй $j$-ийн тоог тоолж болно. Эйлерийн функц бидэнд $C_d = \phi(n / d)$ үр дүнг өгөх ба тиймээс бид хариуг олж авна:

$$\frac{1}{n} \sum_{d ~|~ n} \phi\left(\frac{n}{d}\right) k^d$$

Хэрэглээ: Тороид будах¶

Бид эквивалент ангийн тооны шууд томьёог олж чадахгүй байх нь нэлээд түгээмэл. Олон бодлогод бүлэг дэх сэлгэмэлийн тоо гараар тооцоолоход хэт их байж болох ба тэдгээр дэх циклийн тоог аналитик байдлаар тооцоолох боломжгүй байдаг.

Тэр тохиолдолд бид бүхэл $G$ бүлгийг үүсгэж чадахаар хэдэн "суурь" сэлгэмэлийг гараар олох ёстой. Дараа нь бид $G$ бүлгийн бүх сэлгэмэлийг үүсгэж, тэдгээр дэх циклийн тоог тоолж, томьёогоор хариуг тооцоолох программ бичиж болно.

Тороид будах бодлогын жишээг авч үзье. $n \times m$ ($n < m$) нүдтэй цаас байгаа бөгөөд зарим нүд нь хар өнгөтэй. Дараа нь энэ цаасны $m$ урттай хоёр талыг наасны дараа цилиндр гарна. Дараа нь цилиндрийн хоёр тойргийг (дээд ба доод) мушгилгүйгээр наасны дараа тороид гарна. Даалгавар нь наасан шугамыг бид харж чадахгүй, тороидыг эргүүлж болно гэж үзээд өөр өнгөтэй тороидын тоог тооцоолох явдал юм.

Бид дахин $n \times m$ цаасны хэсгээс эхэлнэ. Дараах төрлийн хувиргалтууд эквивалент ангийг хадгалдгийг харахад амархан: мөрүүдийн циклик шилжүүлэлт, баганануудын циклик шилжүүлэлт, цаасыг 180 градусаар эргүүлэх. Эдгээр хувиргалтууд бүхэл инвариант хувиргалтуудын бүлгийг үүсгэж чадахыг мөн харахад амархан. Хэрэв бид цаасны нүднүүдийг ямар нэгэн байдлаар дугаарлавал эдгээр төрлийн хувиргалтад харгалзах $p_1$, $p_2$, $p_3$ гэсэн гурван сэлгэмэлийг бичиж болно.

Дараа нь зөвхөн үржвэр болгон олж авсан бүх сэлгэмэлийг үүсгэх л үлдэнэ. Ийм бүх сэлгэмэл нь $i_1 = 0 \dots m-1$, $i_2 = 0 \dots n-1$, $i_3 = 0 \dots 1$ байх $p_1^{i_1} p_2^{i_2} p_3^{i_3}$ хэлбэртэй байх нь ойлгомжтой.

Тиймээс бид энэ бодлогын хэрэгжүүлэлтийг бичиж болно.

using Permutation = vector<int>;

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation p(n*m), p1(n*m), p2(n*m), p3(n*m);
    for (int i = 0; i < n*m; i++) {
        p[i] = i;
        p1[i] = (i % n + 1) % n + i / n * n;
        p2[i] = (i / n + 1) % m * n + i % n;
        p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}

Бернсайдын лемм / Пойагийн тоолох теорем¶