# 要求

## Problem 1

• 计算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

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

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