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

From TCS Wiki
Revision as of 12:01, 15 October 2017 by imported>Etone (→‎Problem 3)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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。注意输入规模的选择不能小到手动运算都能计算出答案。

Problem 3

在筛法的讲义中关于"Permutations with restricted positions"的部分,关键性定理

[math]\displaystyle{ N_0=\sum_{k=0}^n(-1)^kr_k(n-k)! }[/math].

的证明过程中,需建立如下等式:

[math]\displaystyle{ \sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)! }[/math].

再讲义的证明中,我们只是用一句"because we can count both sides by first placing [math]\displaystyle{ k }[/math] non-attacking rooks on [math]\displaystyle{ B }[/math] and placing [math]\displaystyle{ n-k }[/math] additional non-attacking rooks on [math]\displaystyle{ [n]\times [n] }[/math] in [math]\displaystyle{ (n-k)! }[/math] ways" 来说明其成立,然而这样的“说理”并不是一个严格的数学证明。

  • 请对上面这个等式给出严格的数学证明。

Problem 4

假设我们班上有n+2个人,其中两个人是DNA完全相同的双胞胎。我们收上n+2份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令[math]\displaystyle{ T_n }[/math]表示满足这个要求的发回作业的方式,问:

  • 计算[math]\displaystyle{ T_n }[/math]是多少;
  • [math]\displaystyle{ n\to\infty }[/math]时,随机重排并发回作业后,满足上述要求的概率是多少。

Problem 5

Let [math]\displaystyle{ \pi }[/math] be a permutation of [math]\displaystyle{ [n] }[/math]. Recall that a cycle of permutation [math]\displaystyle{ \pi }[/math] of length [math]\displaystyle{ k }[/math] is a tuple [math]\displaystyle{ (a_1,a_2,\ldots,a_k) }[/math] such that [math]\displaystyle{ a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1}) }[/math] and [math]\displaystyle{ a_1=\pi(a_k)\, }[/math]. Thus a fixed point of [math]\displaystyle{ \pi }[/math] is just a cycle of length 1.

  • Fix [math]\displaystyle{ k\ge 1 }[/math]. Let [math]\displaystyle{ f_k(n) }[/math] be the number of permutations of [math]\displaystyle{ [n] }[/math] having no cycle of length [math]\displaystyle{ k }[/math]. Compute this [math]\displaystyle{ f_k(n) }[/math] and the limit [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f_k(n)}{n!} }[/math].

Problem 6

Give a dynamical programming algorithm that given as input a bipartite graph [math]\displaystyle{ G(U,V,E) }[/math] where [math]\displaystyle{ |U|=|V|=n }[/math], returns the number of perfect matchings in [math]\displaystyle{ G }[/math] within time [math]\displaystyle{ n 2^{O(n)} }[/math].