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

From EtoneWiki
Jump to: navigation, search

Contents

要求

解答要求有完整的过程。

Problem 1

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

  • 计算Tn是多少;
  • n\to\infty时,随机重排并发回作业后,满足上述要求的概率是多少。

Problem 2

Let π be a permutation of [n]. Recall that a cycle of permutation π of length k is a tuple (a_1,a_2,\ldots,a_k) such that a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1}) and a_1=\pi(a_k)\,. Thus a fixed point of π is just a cycle of length 1.

  • Fix k\ge 1. Let fk(n) be the number of permutations of [n] having no cycle of length k. Compute this fk(n) and the limit \lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}.

Problem 3

Let Nm denote the number of objects from a collection of N objects that possess exactly m of the properties a_1,a_2,\ldots,a_r. Generalize the principle of inclusion-exclusion by computing Nm as the following form

N_m=\sum_{k=m}^r(-1)^{k-m}{k\choose m}s_k,
and please explicitly give the sk.

Problem 4

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

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

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

Personal tools