Burnside's lemma and Polya enumeration theorem

日付: 11月 18, 2018

[cp-algorithms: Burnside's lemma and Polya enumeration theorem](https://cp-algorithms.com/combinatorics/burnside.html)

The main usage of Burnside's lemma and Polya's enumeration theorem is counting the number of **equivalence classes** in sets.

* **Object**. The equivalence classes that we want to count.
* **Representation**. Many representations may correspond to the same object. It can be denoted by a function <math><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math>f of the latent variables(for example, in the binary tree coloring problem, these variables are tree nodes).
* **Invariant permutation**. A permutation of latent variables that only changes the representation, not the object. <math><semantics><mrow><msub><mi>f</mi><mn>1</mn></msub><mi>π</mi><mo>=</mo><msub><mi>f</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">f_1\pi=f_2</annotation></semantics></math>f1π=f2. All invariant permutations form a group <math><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>G.
* **Fixed point**. A fixed point <math><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math>f of a permutation <math><semantics><mrow><mi>π</mi></mrow><annotation encoding="application/x-tex">\pi</annotation></semantics></math>π satisfies <math><semantics><mrow><mi>f</mi><mi>π</mi><mo>≡</mo><mi>f</mi></mrow><annotation encoding="application/x-tex">f\pi \equiv f</annotation></semantics></math>fπ≡f. The number of fixed points of a permutation is denoted by <math><semantics><mrow><mi>I</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">I(\pi)</annotation></semantics></math>I(π)
* **Burnside's lemma**. <math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>C</mi><mi>l</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>e</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo>=</mo><mfrac><mn>1</mn><mrow><mi mathvariant="normal">∣</mi><mi>G</mi><mi mathvariant="normal">∣</mi></mrow></mfrac><munder><mo>∑</mo><mrow><mi>π</mi><mo>∈</mo><mi>G</mi></mrow></munder><mi>I</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">|Classes| = \frac{1}{|G|}\sum_{\pi \in G} I(\pi)</annotation></semantics></math>∣Classes∣=∣G∣1π∈G∑I(π)
* **Polya enumeration theorem(special case)**.<math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>C</mi><mi>l</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>e</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo>=</mo><mfrac><mn>1</mn><mrow><mi mathvariant="normal">∣</mi><mi>G</mi><mi mathvariant="normal">∣</mi></mrow></mfrac><munder><mo>∑</mo><mrow><mi>π</mi><mo>∈</mo><mi>G</mi></mrow></munder><msup><mi>k</mi><mrow><mi>C</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow></msup></mrow><annotation encoding="application/x-tex">|Classes|=\frac{1}{|G|}\sum_{\pi \in G}k^{C(\pi)}</annotation></semantics></math>∣Classes∣=∣G∣1π∈G∑kC(π) <math><semantics><mrow><mi>C</mi><mo>(</mo><mi>π</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">C(\pi)</annotation></semantics></math>C(π) is the number of cycles in the permutation <math><semantics><mrow><mi>π</mi></mrow><annotation encoding="application/x-tex">\pi</annotation></semantics></math>π, <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k is the number of values that each representation element can take.

KONGROOの基地

このブログを検索

Burnside's lemma and Polya enumeration theorem

コメント

コメントを投稿