maths.free › Combinatorics & Graph Theory › Pólya's Enumeration Theorem › Burnside's Lemma

Burnside's Lemma

Burnside's lemmaAgain, not originally proved by Burnside. It was known to Frobenius and for the most part by Cauchy. However, it was most easily found in Burnside's book, and thus his name came to be attached. relates the number of equivalence classes of the action of a group on a finite set to the number of elements of the set fixed by the elements of the group. Before stating and proving it, we need some notation and a proposition. If a group \(G\) acts on a finite set \(\cgC\), let \(\sim\) be the equivalence relation induced by this action. (As before, the action of \(\pi\in G\) on \(\cgC\) will be denoted \(\pi^*\).) Denote the equivalence class containing \(C\in \cgC\) by \(\langle C\rangle\)\(\langle C\rangle\)equivalence class of \(C\). For \(\pi\in G\), let \(\fix_\cgC(\pi)=\{C\in \cgC\colon \pi^*(C) = C\}\), the set of colorings fixed by \(\pi\). For \(C\in\cgC\), let \(\stab_G(C)=\{\pi\in G\colon \pi(C) = C\}\) be the stabilizer\(\stab_G(C)\)stabilizer of \(C\) under action of \(G\) of \(C\) in \(G\), the permutations in \(G\) that fix \(C\).

To illustrate these concepts before applying them, refer back to . Using that information, we can determine that \(\fix_\cgC(r_2) = \{C_1,C_{10},C_{11},C_{16}\}\). Determining the stabilizer of a coloring requires finding the rows of the table in which it appears. Thus, \(\stab_{D_8}(C_7) = \{\iota,h\}\) and \(\stab_{D_8}(C_{11}) = \{\iota,r_2,p,n\}\).

Proposition

Let a group \(G\) act on a finite set \(\cgC\). Then for all \(C\in \cgC\), \[\begin{aligned}\end{aligned}\]

Proof

Let \(\stab_G(C) = \{\pi_1,\dots,\pi_k\}\) and \(T(C,C') = \{\pi\in G\colon \pi^*(C) = C'\}\). (Note that \(T(C,C) = \stab_G(C)\).) Take \(\pi\in T(C,C')\). Then \(\pi\circ \pi_i\in T(C,C')\) for \(1\leq i\leq k\). Furthermore, if \(\pi\circ \pi_i = \pi\circ \pi_j\), then \(\pi^{-1}\circ\pi\circ \pi_i=\pi^{-1}\circ\pi\circ \pi_j\). Thus \(\pi_i=\pi_j\) and \(i=j\). If \(\pi'\in T(C,C')\), then \(\pi\inv\circ \pi'\in T(C,C)\). Thus, \(\pi\inv\circ\pi' = \pi_i\) for some \(i\), and hence \(\pi' = \pi\circ \pi_i\). Therefore \(T(C,C') = \{\pi\circ\pi_1,\dots,\pi\circ\pi_k\}\). Additionally, we observe that \(T(C',C) = \{\pi\inv\colon \pi\in T(C,C')\}\). Now for all \(C'\in\langle C\rangle\), \[\begin{aligned}\end{aligned}\] Therefore, \[\begin{aligned}\end{aligned}\] Now notice that each element of \(G\) appears in \(T(C,C')\) for precisely one \(C'\in\langle C\rangle\), and the proposition follows.

With established, we are now prepared for Burnside's lemma.

Before we proceed to the proof, note that the calculation in Burnside's lemma for the example of \(2\)-coloring the vertices of a square is exactly the calculation we performed at the end of .

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

Эми сиз Бул функцияны калкулятор чече албайт, бирок анын бөлүгү эсептелет. Төмөндө бирин сынап көрүңүз же өзүңүздүнсүн жазыңыз.

Өзүңүздүн иштөөңүздү улантыңыз

Бесплатный аккаунт добавляет заметки к каждому уроку, записывает завершенные и решенные задачи в одном месте, а также позволяет задавать вопросы учителю по этой странице. Математика өзү бардык окуучуларга ачык, ал компьютерге киргенде да, кирбегенде да.

Каттоо Кирүү

Бул жерде колдонулган символдор

Бардык символдорду басып, толук аныктамасын, сүрөтүн жана ар бир тамгасынын маанисин көрсөңүз болот.

Кээ бирлердин суроосу

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Бул барактын айрым бөлүгү төмөнкү булактан алынды Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Бул жерде кыскартылып жана кайрадан түшүндүрүлгөн; каталарыбыз өзүбүздүкү.

Кээ бирлери Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion, exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs