Combinatorics (Fall 2010)/Problem set 1: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop Created page with '== Problem 0 == 你的姓名，学号。 == Problem 1 == 我们有<math>k</math>种不同的明信片，其中第<math>i</math>种明信片有<math>m_i</math>张。请问总共…' |
imported>WikiSysop |
||
| Line 6: | Line 6: | ||
== Problem 2 == | == Problem 2 == | ||
== Problem 3 == | |||
令<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>的闭合形式。 | |||
#定义<math>t_n^*</math>为 | |||
::<math>\begin{cases} | |||
0 & n=0,n=1\\ | |||
1 & n=2\\ | |||
t_{n-3} & n\ge 3. | |||
\end{cases}</math> | |||
:计算<math>t_n^*</math>的生成函数<math>T^*(x)=\sum_{n\ge 0}t_n^* x^n</math>的闭合形式。 | |||
(<math>t^*_n</math>通常被称为tribonacci number。) | |||
Revision as of 01:09, 17 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
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]。
- 给出计算[math]\displaystyle{ t_n }[/math]的递归式，并给出足够的初始值。
- 计算[math]\displaystyle{ t_n }[/math]的生成函数[math]\displaystyle{ T(x)=\sum_{n\ge 0}t_n x^n }[/math]，给出[math]\displaystyle{ T(x) }[/math]的闭合形式。
- 定义[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。)