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

• 题目要有解题过程。

Problem 0

你的姓名、年级、学号。

Problem 1

令[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]。(闭合形式)

Problem 2

有三种颜色的宝石，串成20块宝石的项链，旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。给出5种具体的[math]\displaystyle{ (n_1,n_2,n_3) }[/math]，以及第 [math]\displaystyle{ i }[/math] 种宝石刚好有 [math]\displaystyle{ n_i }[/math] 块 ([math]\displaystyle{ i=1,2,3 }[/math]) 的项链的计数。

写一篇短文（字数不限），以论文的格式给出这道题目的解决过程。

（可以编程解决，也可以使用一些符号计算工具，例如mathematica或linux下的MAXIMA。不建议手算。）

如果有代码，也要提交源代码。

Open project (可选)

• 编一个程序，输入：[math]\displaystyle{ n,m,n_1,n_2,\ldots,n_{m} }[/math] 且有 [math]\displaystyle{ n_1+n_2+\cdots+n_m=n }[/math].

输出：[math]\displaystyle{ n }[/math] 块宝石组成的项链，旋转(rotation)和镜像(reflection)都算等价，宝石有 [math]\displaystyle{ m }[/math] 种，第 [math]\displaystyle{ i }[/math] 种宝石刚好有 [math]\displaystyle{ n_i }[/math] 种，这样的项链的数量。

• Polya计数不仅仅用于数环状结构的对称染色。自己举一个非环状结构（例如某有机化合物），指定有限个颜色，给出pattern inventory。