# 组合数学 (Fall 2016)/Problem Set 1

• 每道题目的解答都要有完整的解题过程。中英文不限。
• 第四题有一处笔误。已改正，见红色字体。

## Problem 1

Find the number of ways to select $\displaystyle{ 2n }$ balls from $\displaystyle{ n }$ identical blue balls, $\displaystyle{ n }$ identical red balls and $\displaystyle{ n }$ identical green balls.

• Give a combinatorial proof for the problem.
• Give an algebraic proof for the problem.

## Problem 3

A $\displaystyle{ 2\times n }$ rectangle is to be paved with $\displaystyle{ 1\times 2 }$ identical blocks and $\displaystyle{ 2\times 2 }$ identical blocks. Let $\displaystyle{ f(n) }$ denote the number of ways that can be done. Find a recurrence relation for $\displaystyle{ f(n) }$, solve the recurrence relation.

## Problem 4

Let $\displaystyle{ a_n }$ be a sequence of numbers satisfying the recurrence relation:

$\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }$

with initial condition $\displaystyle{ a_0=s }$ and $\displaystyle{ a_1=t }$, where $\displaystyle{ p,q,r,s,t }$ are constants such that $\displaystyle{ {\color{red}p}+q+r=0 }$, $\displaystyle{ p\neq 0 }$ and $\displaystyle{ s\neq t }$. Solve the recurrence relation.

## Problem 5

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

## Problem 6

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\ge 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!} }$.

## Bonus problem

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{ n 2^{O(n)} }$.