Burnside's lemma and Polya enumeration theorem 日付: 11月 18, 2018 リンクを取得 Facebook × Pinterest メール 他のアプリ [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 $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. $f_1\pi=f_2$. All invariant permutations form a group $G$. * **Fixed point**. A fixed point $f$ of a permutation $\pi$ satisfies $f\pi \equiv f$. The number of fixed points of a permutation is denoted by $I(\pi)$ * **Burnside's lemma**. $$|Classes| = \frac{1}{|G|}\sum_{\pi \in G} I(\pi)$$ * **Polya enumeration theorem(special case)**.$$|Classes|=\frac{1}{|G|}\sum_{\pi \in G}k^{C(\pi)}$$ $C(\pi)$ is the number of cycles in the permutation $\pi$, $k$ is the number of values that each representation element can take. コメント
コメント
コメントを投稿