组合数学 (Fall 2011)/Pólya's theory of counting: Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone |
||
| Line 3: | Line 3: | ||
== Burnside's Lemma == | == Burnside's Lemma == | ||
{{Theorem|Burnside's Lemma| | {{Theorem|Burnside's Lemma| | ||
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For each <math>\pi\in G</math>, let <math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math> be the set of elements | :Let <math>G</math> be a permutation group acting on a set <math>X</math>. For each <math>\pi\in G</math>, let <math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math> be the set of elements invariant under group action by <math>\pi</math>. The number of orbits, denoted <math>|X/G|</math>, is | ||
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math> | ::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math> | ||
}} | }} | ||
==Pólya's Theory of Counting == | ==Pólya's Theory of Counting == | ||
Revision as of 08:25, 23 September 2011
Groups
Burnside's Lemma
Burnside's Lemma - Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/math]. For each [math]\displaystyle{ \pi\in G }[/math], let [math]\displaystyle{ X_\pi=\{x\in X\mid \pi\circ x=x\} }[/math] be the set of elements invariant under group action by [math]\displaystyle{ \pi }[/math]. The number of orbits, denoted [math]\displaystyle{ |X/G| }[/math], is
- [math]\displaystyle{ |X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|. }[/math]
- Let [math]\displaystyle{ G }[/math] be a permutation group acting on a set [math]\displaystyle{ X }[/math]. For each [math]\displaystyle{ \pi\in G }[/math], let [math]\displaystyle{ X_\pi=\{x\in X\mid \pi\circ x=x\} }[/math] be the set of elements invariant under group action by [math]\displaystyle{ \pi }[/math]. The number of orbits, denoted [math]\displaystyle{ |X/G| }[/math], is