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

• 每道题目的解答都要有完整的解题过程。中英文不限。

• 第四题有一处笔误。已改正，见红色字体。

Problem 1

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

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

Problem 2

李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 [math]\displaystyle{ p }[/math] 张，李雷获得选票 [math]\displaystyle{ q }[/math] 张，[math]\displaystyle{ p\gt q }[/math]。我们将总共的 [math]\displaystyle{ p+q }[/math] 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。

Problem 3

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

Problem 4

Let [math]\displaystyle{ a_n }[/math] be a sequence of numbers satisfying the recurrence relation:

[math]\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }[/math]

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

Problem 5

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

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

Problem 6

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

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

Bonus problem

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