组合数学 (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 pa_{n}+qa_{n-1}+ra_{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\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!}}}$.

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