Combinatorics (Fall 2010)/Problem set 1

From EtoneWiki
Jump to: navigation, search
  • 每道题目的解答都要求有过程。
  • 如发现雷同,雷同的双方都将直接在该门课程的最终成绩中不及格。

Problem 0

你的姓名,学号。

Problem 1

我们有种不同的明信片,其中第种明信片有张。请问总共有多少种方法把所有这些明信片发给个人。(注意每个人可以收多张明信片或者不收明信片)。


  • 大挑战(不计分数):尝试考虑每个人都至少收到一张明信片的情况。

Problem 2

没有长为的圈(cycle)的的排列(permutation)的数量。

  1. 。(可以不是闭合形式)
  2. 对常数,求。(闭合形式)

(提示:用筛法。)


注:cycle的概念在离散数学课上已经学到过。令的排列,连续的对某个应用排列次之后回到,这就是一个长为的圈。即

例如12345的排列42531,有两个cycle,(1435)(2)。

Problem 3

表示长度为,没有3个连续的1的二进制串的数量,即

  1. 给出计算的递归式,并给出足够的初始值。
  2. 计算的生成函数,给出的闭合形式。
  3. 定义
计算的生成函数的闭合形式。

(通常被称为tribonacci number。)


注意:只需解生成函数的闭合形式,无需展开(否则你会比较痛苦)。