组合数学 (Fall 2011)/Pólya's theory of counting: Difference between revisions

From TCS Wiki
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(x)=x\}</math>. The number of orbits, denoted <math>|X/G|</math>, is  
: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> be the set of fixed points of <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 14:54, 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] be the set of fixed points of [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]

Pólya's Theory of Counting