Combinatorics (Fall 2010)/Problem set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
m Protected "Combinatorics (Fall 2010)/Problem set 1" ([edit=sysop] (indefinite) [move=sysop] (indefinite))
imported>WikiSysop
 
(5 intermediate revisions by the same user not shown)
Line 6: Line 6:


== Problem 1 ==
== Problem 1 ==
我们有<math>k</math>种不同的明信片,其中第<math>i</math>种明信片有<math>m_i</math>张。请问总共有多少种方法把所有这些明信片发给<math>n</math>个人。(注意每个人可以收多张明信片)。
我们有<math>k</math>种不同的明信片,其中第<math>i</math>种明信片有<math>m_i</math>张。请问总共有多少种方法把所有这些明信片发给<math>n</math>个人。(注意每个人可以收多张明信片或者不收明信片)。
 
 
*'''大挑战(不计分数):'''尝试考虑每个人都至少收到一张明信片的情况。


== Problem 2 ==
== Problem 2 ==
Line 14: Line 17:


(提示:用筛法。)
(提示:用筛法。)
注:cycle的概念在离散数学课上已经学到过。令<math>\pi</math>为<math>[n]</math>的排列,连续的对某个<math>i\in[n]</math>应用排列<math>\pi</math>,<math>k</math>次之后回到<math>i</math>,这就是一个长为<math>k</math>的圈。即
:<math>\underbrace{\pi\circ\pi\circ\pi\circ\cdots\pi}_{k}(i)=i</math>
例如12345的排列42531,有两个cycle,(1435)(2)。


== Problem 3 ==
== Problem 3 ==
Line 29: Line 38:


(<math>t^*_n</math>通常被称为tribonacci number。)
(<math>t^*_n</math>通常被称为tribonacci number。)
注意:只需解生成函数的闭合形式,无需展开(否则你会比较痛苦)。

Latest revision as of 02:05, 20 September 2010

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

Problem 0

你的姓名,学号。

Problem 1

我们有[math]\displaystyle{ k }[/math]种不同的明信片,其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张。请问总共有多少种方法把所有这些明信片发给[math]\displaystyle{ n }[/math]个人。(注意每个人可以收多张明信片或者不收明信片)。


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

Problem 2

[math]\displaystyle{ f_k(n) }[/math]没有长为[math]\displaystyle{ k }[/math]的圈(cycle)的[math]\displaystyle{ [n] }[/math]的排列(permutation)的数量。

  1. [math]\displaystyle{ f_k(n) }[/math]。(可以不是闭合形式)
  2. 对常数[math]\displaystyle{ k }[/math],求[math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f_k(n)}{n!} }[/math]。(闭合形式)

(提示:用筛法。)


注:cycle的概念在离散数学课上已经学到过。令[math]\displaystyle{ \pi }[/math][math]\displaystyle{ [n] }[/math]的排列,连续的对某个[math]\displaystyle{ i\in[n] }[/math]应用排列[math]\displaystyle{ \pi }[/math][math]\displaystyle{ k }[/math]次之后回到[math]\displaystyle{ i }[/math],这就是一个长为[math]\displaystyle{ k }[/math]的圈。即

[math]\displaystyle{ \underbrace{\pi\circ\pi\circ\pi\circ\cdots\pi}_{k}(i)=i }[/math]

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

Problem 3

[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]的闭合形式。
  3. 定义[math]\displaystyle{ t_n^* }[/math]
[math]\displaystyle{ \begin{cases} 0 & n=0,n=1\\ 1 & n=2\\ t_{n-3} & n\ge 3. \end{cases} }[/math]
计算[math]\displaystyle{ t_n^* }[/math]的生成函数[math]\displaystyle{ T^*(x)=\sum_{n\ge 0}t_n^* x^n }[/math]的闭合形式。

([math]\displaystyle{ t^*_n }[/math]通常被称为tribonacci number。)


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