组合数学 (Fall 2011)/Pólya's theory of counting: Difference between revisions
Jump to navigation
Jump to search
imported>Etone No edit summary |
imported>Etone |
||
| Line 1: | Line 1: | ||
== Groups == | == Groups == | ||
== Burnside's Lemma == | == 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(x)=x\}</math>. The number of orbits, denoted <math>|X/G|</math>, is | |||
::<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 14:34, 16 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(x)=x\} }[/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(x)=x\} }[/math]. The number of orbits, denoted [math]\displaystyle{ |X/G| }[/math], is