组合数学 (Fall 2015)/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.

Problem 3

• Give a combinatorial proof for the following identity:

[math]\displaystyle{ \sum_{k=1}^n k{n\choose k}=n\cdot 2^{n-1}. }[/math]

• Give a closed form for [math]\displaystyle{ \sum_{k=1}^n k^2{n\choose k} }[/math] and prove it.

Problem 4

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.