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

## Problem 1

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

## Problem 2

Give a combinatorial proof for the following identity:

${\displaystyle \sum _{k=1}^{n}k{n \choose k}=n\cdot 2^{n-1}.}$
• (optional) Give a closed form for ${\displaystyle \sum _{k=1}^{n}k^{2}{n \choose k}}$ and prove it.

## Problem 3

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

## Problem 4

Let ${\displaystyle \pi }$ be a permutation of ${\displaystyle [n]}$. Recall that a cycle of permutation ${\displaystyle \pi }$ of length ${\displaystyle k}$ is a tuple ${\displaystyle (a_{1},a_{2},\ldots ,a_{k})}$ such that ${\displaystyle a_{2}=\pi (a_{1}),a_{3}=\pi (a_{2}),\ldots ,a_{k}=\pi (a_{k-1})}$ and ${\displaystyle a_{1}=\pi (a_{k})\,}$. Thus a fixed point of ${\displaystyle \pi }$ is just a cycle of length 1.

• Fix ${\displaystyle k\geq 1}$. Let ${\displaystyle f_{k}(n)}$ be the number of permutations of ${\displaystyle [n]}$ having no cycle of length ${\displaystyle k}$. Compute this ${\displaystyle f_{k}(n)}$ and the limit ${\displaystyle \lim _{n\rightarrow \infty }{\frac {f_{k}(n)}{n!}}}$.