组合数学 (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)的数量。
- 求[math]\displaystyle{ f_k(n) }[/math]。(可以不是闭合形式)
- 对常数[math]\displaystyle{ k }[/math]，求[math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f_k(n)}{n!} }[/math]。(闭合形式)
Problem 2
有三种颜色的宝石，串成20块宝石的项链，旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。
（可以编程解决，也可以使用一些符号计算工具，例如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。