# 组合数学 (Fall 2017)/Problem Set 2

## Problem 1

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

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

## Problem 3

${\displaystyle N_{0}=\sum _{k=0}^{n}(-1)^{k}r_{k}(n-k)!}$.

${\displaystyle \sum _{I\in {[n] \choose k}}|A_{I}|=r_{k}(n-k)!}$.

• 请对上面这个等式给出严格的数学证明。

## Problem 4

• 计算${\displaystyle T_{n}}$是多少；
• ${\displaystyle n\to \infty }$时，随机重排并发回作业后，满足上述要求的概率是多少。

## Problem 5

Let ${\displaystyle \pi }$ be a permutation of ${\displaystyle [n]}$. Recall that a cycle of permutation ${\displaystyle \pi }$ of length ${\displaystyle k}$ is a tuple ${\displaystyle (a_{1},a_{2},\ldots ,a_{k})}$ such that ${\displaystyle a_{2}=\pi (a_{1}),a_{3}=\pi (a_{2}),\ldots ,a_{k}=\pi (a_{k-1})}$ and ${\displaystyle a_{1}=\pi (a_{k})\,}$. Thus a fixed point of ${\displaystyle \pi }$ is just a cycle of length 1.

• Fix ${\displaystyle k\geq 1}$. Let ${\displaystyle f_{k}(n)}$ be the number of permutations of ${\displaystyle [n]}$ having no cycle of length ${\displaystyle k}$. Compute this ${\displaystyle f_{k}(n)}$ and the limit ${\displaystyle \lim _{n\rightarrow \infty }{\frac {f_{k}(n)}{n!}}}$.

## Problem 6

Give a dynamical programming algorithm that given as input a bipartite graph ${\displaystyle G(U,V,E)}$ where ${\displaystyle |U|=|V|=n}$, returns the number of perfect matchings in ${\displaystyle G}$ within time ${\displaystyle n2^{O(n)}}$.