组合数学 (Fall 2011)/Pólya's theory of counting and 组合数学 (Fall 2011)/Problem set 3: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
No edit summary
 
imported>Etone
 
Line 1: Line 1:
== Groups ==
== Problem 1==
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
* closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
* associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.


=== Permutation groups===
==Problem 2==
一个图 <math>G(V,E)</math> 的切 (cut) 是一个边集 <math>C\subseteq E</math>，使得去掉这些边之后 <math>G</math> 不再连通。


==== Cycle decomposition ====
证明：任意一个有 <math>m</math> 条边的无向图都存在一个大小为 <math>\frac{m}{2}</math> 的切。


=== Group action ===
==Problem 3 ==
{{Theorem|Definition (group action)|
令 <math>\mathcal{F}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-regular family，即 <math>\forall i\in[n]</math>，刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{F}</math> 满足 <math>i\in S</math>。
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}


== Burnside's Lemma ==
假设 <math>k\ge 10</math>。证明：存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{F}</math> 中不存在单色的集合 <math>S\in\mathcal{F}</math>。
 
=== Orbits ===
 
=== Counting orbits===
{{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 invariant under 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>
}}
 
==Pólya's Theory of Counting ==
=== The cycle index ===
 
=== Pólya's enumeration formula ===
 
=== de Bruijn's generalization===

Revision as of 17:50, 26 October 2011

Problem 1

Problem 2

一个图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 是一个边集 [math]\displaystyle{ C\subseteq E }[/math]，使得去掉这些边之后 [math]\displaystyle{ G }[/math] 不再连通。

证明：任意一个有 [math]\displaystyle{ m }[/math] 条边的无向图都存在一个大小为 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。

Problem 3

令 [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-regular family，即 [math]\displaystyle{ \forall i\in[n] }[/math]，刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{F} }[/math] 满足 [math]\displaystyle{ i\in S }[/math]。

假设 [math]\displaystyle{ k\ge 10 }[/math]。证明：存在一个对 [math]\displaystyle{ [n] }[/math] 的 2着色 [math]\displaystyle{ f:[n]\rightarrow\{0,1\} }[/math] 使得 [math]\displaystyle{ \mathcal{F} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{F} }[/math]。

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Pólya%27s_theory_of_counting&oldid=5092"