学习指导-教学单元-22.6-Catalan 数、Stirling 数
一、主要知识点
1. 概念
●Catalan 数的定义、生成函数及实际应用
●第一类Stirling 数的定义、公式及应用
●第二类Stirling 数的定义、公式及应用
2. 重要的公式
（1）Catalan 数
1
2
trunc函数和int,11
1=≥=∑-=-h n h h h n k k n k n ⎪⎪⎭
⎫  ⎝⎛--=1221n n n h n （2）第一类Stirling 数
)!1(1,001
111)1(-=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡≥>⎥⎦
⎤⎢⎣⎡--+⎥⎦⎤⎢⎣⎡--=⎥⎦⎤⎢⎣⎡n n n r n r n r n n r n ∑==⎥⎦
⎤⎢⎣⎡-=⎪⎪⎭
⎫  ⎝⎛=⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡n r n r n n n n n n n n 1!
2)1(21,1 (3)第二类Stirling 数
11,00111=⎭
⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧⎭⎬⎫⎩⎨⎧--+⎭⎬⎫⎩⎨⎧-=⎭⎬⎫⎩⎨⎧n n r n r n r r n 1,21,1221=⎭
⎬⎫⎩⎨⎧⎪⎪⎭⎫  ⎝⎛=⎭⎬⎫⎩⎨⎧--=⎭⎬⎫⎩⎨⎧-n n n n n n n 的正整数解求和对满足n n n n m n m n n n n m m =+++⎭⎬⎫⎩⎨⎧=⎪⎪⎭
⎫  ⎝⎛∑...,!...2121∑==⎭⎬⎫⎩⎨⎧⎪⎪⎭⎫  ⎝⎛m
k n m k k n k m 1!
∑=⎭
⎬⎫⎩⎨⎧-⎪⎪⎭⎫  ⎝⎛=⎭⎬⎫⎩⎨⎧+n i r i i n r n 011二、学习要求
1. 熟练掌握Catalan 数和两类Stirling 数的定义、递推方程及公式
2. 能够使用上述公式求解简单的组合计数问题
3. 了解上述组合计数的应用实例
三、重点难点指导
放球问题是重要的组合计数模型，在实践中有着重要的应用。表1根据球与盒子是否被标号（分别用“Y”和“N”表示）、是否允许盒子为空分成八个子类，并列出了对应的计数方法或者结果。观察计数结果，放球问题与方程的非负整数解、正整数的拆分等计数模型有关联，计数结果与组合数、第二类Strling 数有着密切的联系。
表1

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。