imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| == Groups ==
| | *<font color="red" size=5>题目要有解题过程。</font> |
| 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 0 == |
| | 你的姓名、年级、学号。 |
|
| |
|
| ==== Cycle decomposition ==== | | == Problem 1 == |
| | 令<math>f_k(n)</math>为'''没有'''长为<math>k</math>的圈(cycle)的<math>[n]</math>的排列(permutation)的数量。 |
| | #求<math>f_k(n)</math>。(可以不是闭合形式) |
| | #对常数<math>k</math>，求<math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>。(闭合形式) |
|
| |
|
| === Group action === | | == Problem 2== |
| {{Theorem|Definition (group action)|
| | 有三种颜色的宝石，串成20块宝石的项链，旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。给出5种具体的<math>(n_1,n_2,n_3)</math>，以及第 <math>i</math> 种宝石刚好有 <math>n_i</math> 块 (<math>i=1,2,3</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>.
| |
| }}
| |
|
| |
|
| ==== Example: coloring a necklace ====
| | 写一篇短文（字数不限），以论文的格式给出这道题目的解决过程。 |
| Suppose a necklace is made of <math>n</math> beads, each with one of the <math>m</math> colors. Formally, a necklace is an assignment <math>x:[n]\rightarrow[m]</math> of <math>m</math> colors to <math>n</math> positions. Let <math>X=\{x:[n]\rightarrow[m]\}</math> be the set of all such assignments.
| |
|
| |
|
| For example, when <math>n=4</math> and <math>m=2</math>, <math>X</math> contains all possible 2-colorings (say red and blue) of 4 positions.
| | （可以编程解决，也可以使用一些符号计算工具，例如mathematica或linux下的MAXIMA。不建议手算。） |
| :<math>X=\{{\color{blue}bbbb}, {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{blue}b}{\color{red}rrr}, {\color{red}r}{\color{blue}bbb}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}bb}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}, {\color{red}rrrr}\}</math>
| |
|
| |
|
| We consider two kinds of symmetric operations on necklaces:
| | 如果有代码，也要提交源代码。 |
| * Rotation: the corresponding group is the cyclic group <math>C_n</math>.
| |
| * Rotation and reflection: the corresponding group is the dihedral group <math>D_n</math>.
| |
|
| |
|
| Mathematically, these operations on necklaces are described as group actions on <math>X</math>. Recall that each member <math>x\in X</math> is an <math>m</math>-coloring <math>x:[n]\rightarrow[m]</math> of <math>n</math> positions. Suppose the permutation group is <math>G</math>, for any <math>\pi\in G</math> and any <math>x\in X</math>, the group action <math>\pi\circ x</math> is naturally defined as such:
| | == Open project (可选) == |
| :<math>(\pi\circ x)(i)=x(\pi(i))</math>.
| | * 编一个程序，输入：<math>n,m,n_1,n_2,\ldots,n_{m}</math> 且有 <math>n_1+n_2+\cdots+n_m=n</math>. |
| | 输出：<math>n</math> 块宝石组成的项链，旋转(rotation)和镜像(reflection)都算等价，宝石有 <math>m</math> 种，第 <math>i</math> 种宝石刚好有 <math>n_i</math> 种，这样的项链的数量。 |
|
| |
|
| == Burnside's Lemma ==
| | * Polya计数不仅仅用于数环状结构的对称染色。自己举一个非环状结构（例如某有机化合物），指定有限个颜色，给出pattern inventory。 |
| | |
| === Orbits ===
| |
| Let <math>G</math> be a permutation group acting on a set <math>X</math>. Let <math>\pi\in G, x\in X</math>.
| |
| * The '''invariant set''' of <math>\pi</math>: | |
| ::<math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math>.
| |
| * The '''stabilizer''' of <math>x</math>:
| |
| ::<math>G_x=\{\pi\in G\mid \pi\circ x=x\}</math>.
| |
| * The '''orbit''' of <math>x</math> under action of <math>G</math>:
| |
| ::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.
| |
| | |
| For any <math>x,y,z\in X</math>, the followings can be verified for orbits
| |
| * ''reflexivity'': <math>x\in Gx</math> since <math>e\circ x=x</math>;
| |
| * ''symmetric'': if <math>y\in Gx</math> then there is a <math>\pi\in G</math> such that <math>\pi\circ x=y</math>, thus <math>\pi^{-1}\circ y=\pi^{-1}\circ\pi =(\pi^{-1}\cdot \pi)\circ x=e\circ x=x</math>, hence <math>x\in G_y</math>;
| |
| * ''transitivity'': if <math>y\in Gx</math> and <math>z\in Gy</math>, then there exist <math>\pi,\sigma\in G</math> such that <math>\pi\circ x=y</math> and <math>\sigma\circ y=z</math>, thus <math>(\sigma\cdot \pi)\circ x=\sigma\circ(\pi\circ x)=\sigma\circ y=z</math>, hence <math>z\in Gx</math>.
| |
| | |
| Therefore, <math>x\in Gy</math> defines an equivalent relation between <math>x</math> and <math>y</math>, and orbits partition the set <math>X</math>.
| |
| | |
| ==== Example: coloring a necklace ====
| |
| Back to the example of coloring necklaces.
| |
| | |
| <math>X</math> contains all possible 2-colorings (say red and blue) of 4 positions.
| |
| :<math>X=\{{\color{blue}bbbb}, {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}r}{\color{blue}bb}, {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{blue}b}{\color{red}rrr}, {\color{red}r}{\color{blue}bbb}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}bb}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}, {\color{red}rrrr}\}</math>
| |
| | |
| We consider the rotations of necklaces. The cyclic group <math>C_4</math> acting on <math>X</math> partitions the <math>X</math> into the following equivalent classes:
| |
| :<math>\begin{align}
| |
| &\{{\color{blue}bbbb}\},\\
| |
| &\{ {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}b}{\color{red}r}{\color{blue}bb}, {\color{red}r}{\color{blue}bbb}\},\\
| |
| &\{ {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}rr}{\color{blue}bb}, \},\\
| |
| &\{ {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}\},\\
| |
| &\{ {\color{blue}b}{\color{red}rrr}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}\},\\
| |
| &\{ {\color{red}rrrr}\}
| |
| \end{align}
| |
| </math>
| |
| | |
| === Counting orbits===
| |
| | |
| {{Theorem|Lemma|
| |
| :Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>,
| |
| ::<math>|G_x||Gx|=|G|\,</math>.
| |
| }}
| |
| {{Proof|
| |
| Recall that the orbit <math>Gx=\{\pi\circ x\mid \pi\in G\}</math>. Suppose that <math>Gx=\{x_1,x_2,\ldots,x_t\}</math>. Then there exist a set <math>P=\{\pi_1,\pi_2,\ldots,\pi_t\}</math> of permutations such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>. We construct a bijection between <math>G</math> and <math>P\times G_x</math>, which will prove the lemma.
| |
| | |
| For any <math>\pi\in G</math>, it holds that <math>\pi\circ x=x_i</math> for some <math>x_i</math>, and since <math>\pi_i\circ x=x_i</math>, we have
| |
| <math>\pi_i\circ x=\pi\circ x</math>, hence
| |
| :<math>(\pi_i^{-1}\cdot\pi)\circ x=\pi_i^{-1}\circ(\pi\circ x)=\pi_i^{-1}\circ(\pi_i\circ x)=(\pi_i^{-1}\cdot\pi_i)\circ x=e\circ x=x</math>.
| |
| Denote that <math>\sigma=\pi_i^{-1}\cdot \pi</math>. Then
| |
| *<math>\pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi</math>, and
| |
| *<math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>.
| |
| Therefore, each <math>\pi\in G</math> corresponds to a unique pair <math>(\pi_i,\sigma)\in P\times G_x</math>. We have a 1-1 mapping from <math>G</math> to <math>P\times G_x</math>.
| |
| | |
| For every <math>\pi_i\in P</math> and every <math>\sigma\in G_x</math>, <math>\pi=\pi_i\cdot\sigma\in G</math>. We show that this is a 1-1 mapping. Suppose that <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math> for some <math>\pi_i,\pi_j\in P</math> and <math>\sigma,\tau\in G_x</math>. Then <math>(\pi_i\cdot\sigma)\circ x=\pi_i\circ(\sigma\circ x)=\pi_i\circ x=x_i</math> and <math>(\pi_j\cdot \tau)\circ x=\pi_j\circ(\tau\circ x)=\pi_j\circ x=x_j</math>, which implies <math>x_i=x_j</math> and correspondingly <math>\pi_i=\pi_j</math>. Since <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math>, <math>\sigma=\tau</math>. Therefore, we show that the mapping is 1-1.
| |
| | |
| In conclusion, there exists a bijection between <math>P\times G_x</math> and <math>G</math>. As a consequence, <math>|Gx||G_x|=|P||G_x|=|P\times G_x|=|G|</math>.
| |
| }}
| |
| | |
| {{Theorem|Burnside's Lemma|
| |
| :Let <math>G</math> be a permutation group acting on a set <math>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>
| |
| }}
| |
| {{Proof|
| |
| Let
| |
| :<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
| |
| Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
| |
| :<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
| |
| Then a double counting gives that
| |
| :<math>\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x|</math>.
| |
| | |
| Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
| |
| :<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
| |
| We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Denote the orbits by <math>X_1,X_2,\ldots,X_{|X/G|}</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
| |
| :<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^{|X/G|}\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^{|X/G|}1=|G|{|X/G|}</math>.
| |
| Combining everything together
| |
| :<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|{|X/G|}</math>,
| |
| which gives us that the number of orbits is
| |
| :<math>{|X/G|}=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|</math>.
| |
| }}
| |
| | |
| ==Pólya's Theory of Counting ==
| |
| === The cycle index ===
| |
| Suppose we want to count the number of ways to color <math>n</math> objects using up to <math>m</math> colors, discounting symmetries on the objects described by a group <math>G</math>. If a coloring <math>x:[n]\rightarrow[m]</math> is invariant under the action of a permutation <math>\pi</math> under the action of a permutation <math>\pi\in G</math>, then every position in the same cycle of <math>\pi</math> must have the same color. Therefore, if <math>\pi</math> is decomposed to <math>k</math> disjoint cycles, the number of colorings invariant under the action of <math>\pi</math> is <math>|X_\pi|=m^k</math>.
| |
| | |
| We define the cycle index of a permutation group <math>G</math>.
| |
| For a permutation <math>\pi\in G</math> of <math>[n]</math>, if <math>\pi</math> is a product of <math>k</math> cycles, and the <math>i</math>th cycle has length <math>\ell_i</math>, let
| |
| :<math>M_\pi(x_1,x_2,\ldots,x_n)=\prod_{i=1}^k x_{\ell_i}</math>.
| |
| The '''cycle index''' of <math>G</math> is defined by
| |
| :<math>P_G(x_1,x_2,\ldots,x_n)=\frac{1}{|G|}\sum_{\pi\in G}M_\pi(x_1,x_2,\ldots,x_n)</math>.
| |
| | |
| Due to Burnside's lemma, the number of equivalent classes of <math>m</math>-colorings of <math>n</math> objects, discounting the symmetries described by permutation group <math>G</math>, is given by
| |
| :<math>P_G(\underbrace{m,m,\ldots,m}_{n})</math>
| |
| | |
| === Pólya's enumeration formula ===
| |
| For any tuple <math>\mathbf{v}=(n_1,n_2,\ldots,n_m)</math> of nonnegative integers satisfying that <math>n_1+n_2+\cdots +n_m=n</math>, let <math>a_{\mathbf{v}}</math> represent the number of nonequivalent (with respect to a permutation group <math>G</math>) <math>m</math>-colorings of the <math>n</math> objects, where the <math>i</math>th color occurs precisely <math>n_i</math> times. The '''pattern inventory''' is the (multivariate) generating function for the sequence <math>a_{\mathbf{v}}</math>, defined as
| |
| :<math>F_G(y_1,y_2,\ldots,y_m)=\sum_{\mathbf{v}}a_{\mathbf{v}}y_1^{n_1}y_2^{n_2}\cdots y_m^{n_m}</math>,
| |
| where the sum runs over all <math>\mathbf{v}=(n_1,n_2,\ldots,n_m)</math> satisfying that <math>n_1+n_2+\cdots +n_m=n</math> and <math>n_i\ge 0, 1\le i\le m</math>.
| |
| | |
| {{Theorem|Theorem (Pólya's enumeration formula)|
| |
| :Let <math>G</math> be a permutation group. The pattern inventory for the nonequivalent <math>m</math>-colorings of <math>n</math> objects under the action of <math>G</math> is:
| |
| ::<math>F_G(y_1,y_2,\ldots,y_m)=P_G\left(\sum_{i=1}^m y_i, \sum_{i=1}^m y_i^2,\ldots, \sum_{i=1}^m y_i^n\right)</math>.
| |
| }}
| |
| | |
| === de Bruijn's generalization===
| |