组合数学 (Spring 2014)/Problem Set 1

From EtoneWiki
Jump to: navigation, search

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

Problem 1

  1. 种不同的明信片,每种明信片有无限多张,寄给个人,每人一张,有多少种方法?
  2. 种不同的明信片,每种明信片有无限多张,寄给个人,每人一张,每个人必须收到不同种类的明信片,有多少种方法?
  3. 种不同的明信片,每种明信片有无限多张,寄给个人,每人收到张不同的明信片(但不同的人可以收到相同的明信片),有多少种方法?
  4. 只有一种明信片,共有张,寄给个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?
  5. 种不同的明信片,其中第种明信片有张,寄给个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?

Problem 2

Give a combinatorial proof for the following identity:

  • (optional) Give a closed form for and prove it.

Problem 3

A rectangle is to be paved with identical blocks and identical blocks. Let denote the number of ways that can be done. Find a recurrence relation for , solve the recurrence relation.

Problem 4

Let be a permutation of . Recall that a cycle of permutation of length is a tuple such that and . Thus a fixed point of is just a cycle of length 1.

  • Fix . Let be the number of permutations of having no cycle of length . Compute this and the limit .