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

• 第四题有一处笔误，本题只有n,k两个量。已改正，见红色字体。

Problem 1

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

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

Problem 2

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

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

• 定义对称构成的群，可以通过生成元定义，也可以直接把元素都写出来；
• 写出cycle index和pattern inventory；
• 直接写出三种颜色出现的次数一样多的次数。可以借助一些数学软件如Mathematica的帮助。

Problem 3

Select a permutation of $[n]=\{1,2,\dots ,n\}$ from the symmetric group $S_n$ uniformly at random. (All permutation are supposed to have an equal probability of selection.)

• What is the probability that the cycle containing 1 has length $k$?
• What is the expected number of cycles?

Problem 4

For any $k$-size subset $A$ of vertices set $\{1,2,\dots ,n\}$, there are $T_{n,k}$ forests on the $n$ vertices with exactly $k$ connected components that each element of $A$ is in a different component.

• Prove $T_{n,k}=\sum _{i=0}^{n-k}(\genfrac{}{}{0ex}{}{n-k}{i})T_{n-1,k+i-1}$.
• Prove $T_{n,k}=k\cdot n^{n-k-1}$.

Problem 5

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