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

Problem 1

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

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

Problem 2

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 3

Let [math]\displaystyle{ N_m }[/math] denote the number of objects from a collection of [math]\displaystyle{ N }[/math] objects that possess exactly [math]\displaystyle{ m }[/math] of the properties [math]\displaystyle{ a_1,a_2,\ldots,a_r }[/math]. Generalize the principle of inclusion-exclusion by computing [math]\displaystyle{ N_m }[/math] as the following form

[math]\displaystyle{ N_m=\sum_{k=m}^r(-1)^{k-m}{k\choose m}s_k }[/math],

and please explicitly give the [math]\displaystyle{ s_k }[/math].

Problem 4

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

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

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

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