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