View source for 组合数学 (Fall 2015)/Problem Set 1

每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。

== Problem 1 ==
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，有多少种方法？
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人收到<math>r</math>张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
#只有一种明信片，共有<math>m</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
#有<math>k</math>种不同的明信片，其中第<math>i</math>种明信片有<math>m_i</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？

== Problem 2 ==
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls.

== Problem 3 ==
* Give a combinatorial proof for the following identity:
:<math>
\sum_{k=1}^n k{n\choose k}=n\cdot 2^{n-1}.
</math>

*Give a closed form for <math>\sum_{k=1}^n k^2{n\choose k}</math> and prove it.

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

    /\
   /  \/\/\    /\/\
  /        \/\/    \/\/\
  ----------------------
:长度为<math>n</math>的“山峦”有多少？

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

==Problem 5==
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.

== Problem 6 ==
* 令<math>s_n</math>表示长度为<math>n</math>，没有2个连续的1的二进制串的数量，即
*:<math>s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}|</math>。
:求 <math>s_n</math>。

*令<math>t_n</math>表示长度为<math>n</math>，没有3个连续的1的二进制串的数量，即
*:<math>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>。
*#给出计算<math>t_n</math>的递归式，并给出足够的初始值。
*#计算<math>t_n</math>的生成函数<math>T(x)=\sum_{n\ge 0}t_n x^n</math>，给出生成函数<math>T(x)</math>的闭合形式。

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

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