组合数学 (Fall 2016)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "== Problem 1 == 你要设计一个标志,以下形状中的12条线段可以分别又红、绿、蓝三色之一构成。要求考虑这个形状的“转动”和“反转..."
 
imported>Etone
 
(6 intermediate revisions by the same user not shown)
Line 12: Line 12:
整个过程中可以借助一些数学软件如Mathematica的帮助。
整个过程中可以借助一些数学软件如Mathematica的帮助。


== Problem 2 (optional)==
== Problem 2 ==
设计一个算法。输入一组(m,n),计算出n个<font color=red>无标记</font>点、m条边的:
考虑<math>n</math>颗、共<math>m</math>种宝石构成的项链。假设<math>k\ge1</math>整除<math>n</math>,我们考虑所有<math>k</math>整数倍步数的转动。对于一个pattern <math>\vec{v}=(n_1,n_2,\ldots,n_m), \sum_{i=1}^m n_i=n</math>,令<math>a_{\vec{v}}</math>为在该对称下、具有这一pattern(第<math>i</math>种宝石恰好<math>n_i</math>个,<math>i=1,2,\ldots,m</math>)的项链种类。
*无向图有几个;
 
*有向图有几个。
设计一个算法。输入一组<math>(m,n,k)</math>以及一个pattern <math>\vec{v}=(n_1,n_2,\ldots,n_m), \sum_{i=1}^m n_i=n</math>,输出<math>a_{\vec{v}}</math>
给出你算法使用的permutation group的数学上的定义与构造。给出算法的源代码(鼓励使用Mathematica软件的语言和函数、否则使用C/C++/Java等通用高级语言),并为每一段源代码给出功能的注释和数学上的严格定义。
 
选择至少3组输入的(n,m),给出算法输出的图的个数和算法自动生成的pattern inventory。注意输入规模的选择不能小到手动运算都能计算出答案。
给出你算法使用的permutation group的数学上的定义与构造。给出算法的源代码(鼓励使用Mathematica或者Matlab软件的语言和函数,否则请使用C/C++/Java/Python等通用高级编程语言或脚本语言),并为每一段源代码给出功能上的注释和数学上的严格定义。
 
选择至少两组输入的<math>(m,n,k)</math>,给出算法输出的<math>a_{\vec{v}}</math>值和算法自动生成的pattern inventory。注意输入规模的选择不能小到手动运算都能计算出答案。

Latest revision as of 05:38, 17 October 2016

Problem 1

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

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

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

Problem 2

考虑[math]\displaystyle{ n }[/math]颗、共[math]\displaystyle{ m }[/math]种宝石构成的项链。假设[math]\displaystyle{ k\ge1 }[/math]整除[math]\displaystyle{ n }[/math],我们考虑所有[math]\displaystyle{ k }[/math]整数倍步数的转动。对于一个pattern [math]\displaystyle{ \vec{v}=(n_1,n_2,\ldots,n_m), \sum_{i=1}^m n_i=n }[/math],令[math]\displaystyle{ a_{\vec{v}} }[/math]为在该对称下、具有这一pattern(第[math]\displaystyle{ i }[/math]种宝石恰好[math]\displaystyle{ n_i }[/math]个,[math]\displaystyle{ i=1,2,\ldots,m }[/math])的项链种类。

设计一个算法。输入一组[math]\displaystyle{ (m,n,k) }[/math]以及一个pattern [math]\displaystyle{ \vec{v}=(n_1,n_2,\ldots,n_m), \sum_{i=1}^m n_i=n }[/math],输出[math]\displaystyle{ a_{\vec{v}} }[/math]

给出你算法使用的permutation group的数学上的定义与构造。给出算法的源代码(鼓励使用Mathematica或者Matlab软件的语言和函数,否则请使用C/C++/Java/Python等通用高级编程语言或脚本语言),并为每一段源代码给出功能上的注释和数学上的严格定义。

选择至少两组输入的[math]\displaystyle{ (m,n,k) }[/math],给出算法输出的[math]\displaystyle{ a_{\vec{v}} }[/math]值和算法自动生成的pattern inventory。注意输入规模的选择不能小到手动运算都能计算出答案。