组合数学 (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 a 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{ q+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

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].