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

Problem 1

1. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
2. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
3. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
4. 只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
5. 有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？

Problem 2

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 3

• 一个长度为[math]\displaystyle{ n }[/math]的“山峦”是如下由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，但任何时候都不允许低于[math]\displaystyle{ x }[/math]轴。例如下图：

   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------

长度为[math]\displaystyle{ n }[/math]的“山峦”有多少？

• 一个长度为[math]\displaystyle{ n }[/math]的“地貌”是由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，允许低于[math]\displaystyle{ x }[/math]轴。长度为[math]\displaystyle{ n }[/math]的“地貌”有多少？

Problem 4

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

Problem 5

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 6

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