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


== Problem 1 ==
假设我们班上有<math>n+2</math>个人，其中两个人是DNA完全相同的双胞胎。我们收上<math>n+2</math>份作业后，将这些作业打乱后发回给全班同学，每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令<math>T_n</math>表示满足这个要求的发回作业的方式，问：
* 计算<math>T_n</math>是多少；
* 在<math>n\to\infty</math>时，随机重排并发回作业后，满足上述要求的概率是多少。

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

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

== Problem 3 ==
Select a permutation of <math>[n]=\{1,2,\dots,n\}</math> from the symmetric group <math>S_n</math> 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 <math>k</math>?
* What is the expected number of cycles?

== Problem 4 ==
For any <math>k</math>-size subset <math>A</math> of vertices set <math>\{1,2,\dots,n\}</math>, there are <math>T_{n,k}</math> forests on the <math>n</math> vertices with exactly <math>m</math> connected components that each element of <math>A</math> is in a different component. 
* Prove <math>T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1}</math>.
* Prove <math>T_{n,k}=k\cdot n^{n-k-1}</math>.

== Problem 5 ==
Give a '''dynamic programming''' algorithm that given as input a bipartite graph <math>G(U,V,E)</math> where <math>|U|=|V|=n</math>, returns the number of perfect matchings in <math>G</math> within time <math>O(n^22^n)</math>.