组合数学 (Fall 2011)/Problem set 1

每道题目的解答都要有完整的解题过程。

Problem 0

你的姓名，学号、年级。

有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/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]的“山峦”有多少？

一个长度为[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{ s_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有2个连续的1的二进制串的数量，即
[math]\displaystyle{ s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}| }[/math]。

求 [math]\displaystyle{ s_n }[/math]。

令[math]\displaystyle{ t_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有3个连续的1的二进制串的数量，即
[math]\displaystyle{ t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}| }[/math]。
1. 给出计算[math]\displaystyle{ t_n }[/math]的递归式，并给出足够的初始值。
2. 计算[math]\displaystyle{ t_n }[/math]的生成函数[math]\displaystyle{ T(x)=\sum_{n\ge 0}t_n x^n }[/math]，给出生成函数[math]\displaystyle{ T(x) }[/math]的闭合形式。

注意：只需解生成函数的闭合形式，无需展开。