组合数学 (Fall 2011)/Problem set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "== Problem 0 == 你的姓名、年级、学号。 == Problem 1 == 令<math>f_k(n)</math>为'''没有'''长为<math>k</math>的圈(cycle)的<math>[n]</math>的排列(permutation)…"
 
imported>Etone
No edit summary
 
Line 1: Line 1:
*<font color="red" size=5>题目要有解题过程。</font>
== Problem 0 ==
== Problem 0 ==
你的姓名、年级、学号。
你的姓名、年级、学号。
Line 8: Line 10:


== Problem 2==
== Problem 2==
有三种颜色的宝石,串成20块宝石的项链,旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。
有三种颜色的宝石,串成20块宝石的项链,旋转(rotation)和镜像(reflection)都算等价。给出对于这种项链计数的pattern inventory。给出5种具体的<math>(n_1,n_2,n_3)</math>,以及第 <math>i</math> 种宝石刚好有 <math>n_i</math> 块 (<math>i=1,2,3</math>) 的项链的计数。
 
写一篇短文(字数不限),以论文的格式给出这道题目的解决过程。


(可以编程解决,也可以使用一些符号计算工具,例如mathematica或linux下的MAXIMA。不建议手算。)
(可以编程解决,也可以使用一些符号计算工具,例如mathematica或linux下的MAXIMA。不建议手算。)
如果有代码,也要提交源代码。


== Open project (可选) ==
== Open project (可选) ==

Latest revision as of 01:43, 29 September 2011

  • 题目要有解题过程。

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。