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

From TCS Wiki
Revision as of 14:55, 28 September 2011 by imported>Etone (Created page with "== Problem 0 == 你的姓名、年级、学号。 == Problem 1 == 令<math>f_k(n)</math>为'''没有'''长为<math>k</math>的圈(cycle)的<math>[n]</math>的排列(permutation)…")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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。

(可以编程解决,也可以使用一些符号计算工具,例如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。