组合数学 (Fall 2016)/Problem Set 2

Problem 1

你要设计一个标志，以下形状中的12条线段可以分别又红、绿、蓝三色之一构成。要求考虑这个形状的“转动”和“反转”两种对称。

    __
 __|  |__
|__    __|
   |__|

• 定义这个对称构成的群，可以通过生成元定义，也可以直接把元素都写出来；
• 写出cycle index；
• 如果要求三种颜色出现的次数一样多，写出这时的pattern inventory；
• 如果有四种颜色红、绿、蓝、黄，并要求四种颜色出现的次数一样多，写出这时的pattern inventory；

整个过程中可以借助一些数学软件如Mathematica的帮助。

Problem 2 (optional)

设计一个算法。输入一组(m,n)，计算出n个无标记点、m条边的：

• 无向图有几个；
• 有向图有几个。

给出你算法使用的permutation group的数学上的定义与构造。给出算法的源代码（鼓励使用Mathematica或者Matlab软件的语言和函数，否则请使用C/C++/Java/Python/Fortran等通用高级编程语言、脚本语言、或数值计算语言），并为每一段源代码给出功能的注释和数学上的严格定义。 选择至少3组输入的(n,m)，给出算法输出的图的个数和算法自动生成的pattern inventory。注意输入规模的选择不能小到手动运算都能计算出答案。