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

From TCS Wiki
Jump to navigation Jump to search
imported>Haimin
No edit summary
imported>Etone
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
<font color="red" size=5>Under Construction</font>
*<font color="red" size=5>第四题有一处笔误,本题只有n,k两个量。已改正,见红色字体。</font>
 
== Problem 1 ==
== Problem 1 ==
假设我们班上有<math>n+2</math>个人,其中两个人是DNA完全相同的双胞胎。我们收上<math>n+2</math>份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令<math>T_n</math>表示满足这个要求的发回作业的方式,问:
假设我们班上有<math>n+2</math>个人,其中两个人是DNA完全相同的双胞胎。我们收上<math>n+2</math>份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令<math>T_n</math>表示满足这个要求的发回作业的方式,问:
Line 16: Line 15:
*写出cycle index和pattern inventory;
*写出cycle index和pattern inventory;
*直接写出三种颜色出现的次数一样多的次数。可以借助一些数学软件如Mathematica的帮助。
*直接写出三种颜色出现的次数一样多的次数。可以借助一些数学软件如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 ==
== Problem 4 ==
(All permutation are supposed to have an equal probability of selection).  
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>\color{red}k</math> connected components that each element of <math>A</math> is in a different component.  
* What is the probability that the cycle containing 1 has length k?
* Prove <math>T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1}</math>.
* What is the expected number of cycles?
* Prove <math>T_{n,k}=k\cdot n^{n-k-1}</math>.


== Problem 5 ==
== Problem 5 ==
Let <math>A</math> be an arbitrary set of <math>k</math> different vertices chosen from distinct vertices <math>1,2,\dots,n</math>. There are <math>T_{n,k}</math> forests on <math>n</math> distinct vertices with exactly <math>m</math> connected components that each element of <math>A</math> is in a different tree.
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>.
* Prove <math>T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k-1+i}</math>.
* Prove <math>T_{n,k}=k\cdot n^{n-k-1}</math>.

Latest revision as of 15:53, 21 October 2019

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

Problem 1

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

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

Problem 2

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

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

Problem 3

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

Problem 4

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

  • Prove [math]\displaystyle{ T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1} }[/math].
  • Prove [math]\displaystyle{ 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]\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{ O(n^22^n) }[/math].