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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
 
(13 intermediate revisions by the same user not shown)
Line 1: Line 1:
=要求 =
<font color=red size=5>解答要求有完整的过程。</font>
== Problem 1==
== Problem 1==
Prove the following identity:
假设我们班上有n+2个人,其中两个人是DNA完全相同的双胞胎。我们收上n+2份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令<math>T_n</math>表示满足这个要求的发回作业的方式,问:
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
* 计算<math>T_n</math>是多少;
* <math>n\to\infty</math>时,随机重排并发回作业后,满足上述要求的概率是多少。


(Hint: Use double counting.)
==Problem 2==
 
==Problem 4==
Let <math>\pi</math> be a permutation of <math>[n]</math>.
Let <math>\pi</math> be a permutation of <math>[n]</math>.
Recall that a cycle of permutation <math>\pi</math> of length <math>k</math> is a tuple <math>(a_1,a_2,\ldots,a_k)</math> such that <math>a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1})</math> and <math>a_1=\pi(a_k)\,</math>. Thus a fixed point of <math>\pi</math> is just a cycle of length 1.
Recall that a cycle of permutation <math>\pi</math> of length <math>k</math> is a tuple <math>(a_1,a_2,\ldots,a_k)</math> such that <math>a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1})</math> and <math>a_1=\pi(a_k)\,</math>. Thus a fixed point of <math>\pi</math> is just a cycle of length 1.
* Fix <math>k\ge 1</math>. Let <math>f_k(n)</math> be the number of permutations of <math>[n]</math> having no cycle of length <math>k</math>. Compute this <math>f_k(n)</math> and the limit <math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>.
* Fix <math>k\ge 1</math>. Let <math>f_k(n)</math> be the number of permutations of <math>[n]</math> having no cycle of length <math>k</math>. Compute this <math>f_k(n)</math> and the limit <math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>.
==Problem 3 ==
Let <math>N_m</math> denote the number of objects from a collection of <math>N</math> objects that possess ''exactly'' <math>m</math> of the properties <math>a_1,a_2,\ldots,a_r</math>. Generalize the principle of inclusion-exclusion by computing <math>N_m</math> as the following form
:<math>N_m=\sum_{k=m}^r(-1)^{k-m}{k\choose m}s_k</math>,
:and please explicitly give the <math>s_k</math>.
== Problem 4 ==
你要设计一个标志,以下形状中的12条线段可以分别又红、绿、蓝三色之一构成。要求考虑这个形状的“转动”和“反转”两种对称。
    __
  __|  |__
|__    __|
    |__|
*定义这个对称构成的群,可以通过生成元定义,也可以直接把元素都写出来;
*写出cycle index;
*如果要求三种颜色出现的次数一样多,写出这时的pattern inventory;
*如果有四种颜色红、绿、蓝、黄,并要求四种颜色出现的次数一样多,写出这时的pattern inventory;
整个过程中可以借助一些数学软件如Mathematica的帮助。

Latest revision as of 12:38, 3 November 2015

要求

解答要求有完整的过程。

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的帮助。