首页 > 其他 > 详细

斯特林数学习笔记

时间:2019-07-13 00:58:43      阅读:48      评论:0      收藏:0      [点我收藏+]

标签:之前   全部   方式   n-1   数组   个数   -i   不同   然而   

第一类斯特林数

我们记\(\begin{bmatrix}n\\m\end{bmatrix}\)为将\(n\)个不同的数分为\(m\)个非空圆排列的方案数, 即第一类斯特林数


\[ \displaystyle \begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)*\begin{bmatrix}n-1\\m\end{bmatrix} \]
要么第\(n\)个数单独成环, 要么将第\(n\)个数接到前面某一个数的后面, 第二种是有\(n - 1\)种选择方式的

第一类斯特林数的几条性质

第一条

\[ \displaystyle n! = \sum_{i = 0}^{n}\begin{bmatrix}n\\i\end{bmatrix} \]

假设下式成立
\[ \displaystyle n! = \sum_{i = 0}^{n}\begin{bmatrix}n \\ i\end{bmatrix} \]
使用归纳法证明, 则有
\[ \displaystyle \begin{aligned} \sum_{i = 0}^{n + 1}\begin{bmatrix}n + 1 \\ i\end{bmatrix} &= \begin{bmatrix}n + 1 \\ n + 1\end{bmatrix} + \sum_{i = 0}^{n}\begin{bmatrix}n + 1 \\ i\end{bmatrix}\&=\sum_{i = 0}^{n}(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix}) + \begin{bmatrix}n+1\\n+1\end{bmatrix}\&=n * \sum_{i = 0}^{n}\begin{bmatrix}n\\i\end{bmatrix}+\sum_{i=0}^{n}\begin{bmatrix}n\\i-1\end{bmatrix}+\begin{bmatrix}n+1\\n+1\end{bmatrix}\\&=n*\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}+\sum_{i=0}^{n-1}\begin{bmatrix}n\\i\end{bmatrix}+\begin{bmatrix}n+1\\n+1\end{bmatrix}\&=(n + 1)*\sum_{i=0}^{n-1}\begin{bmatrix}n\\i\end{bmatrix}+n*\begin{bmatrix}n\\n\end{bmatrix}+\begin{bmatrix}n+1\\n+1\end{bmatrix}\&=(n + 1)*\sum_{i=0}^{n-1}\begin{bmatrix}n\\i\end{bmatrix}+n*\begin{bmatrix}n\\n\end{bmatrix}+\begin{bmatrix}n\\n\end{bmatrix}+n*\begin{bmatrix}n\\n+1\end{bmatrix}\&=(n + 1)*\sum_{i=0}^{n-1}\begin{bmatrix}n\\i\end{bmatrix}+(n +1)*\begin{bmatrix}n\\n\end{bmatrix}+0\&=(n+1)*\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}\&=(n+1)*n!\&=(n+1)! \end{aligned} \]
故第一条性质成立(保证n=1时成立, 下同)

第二条

\[ \displaystyle x^{\underline n} = \sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i \]

同上, 假设下式成立
\[ \displaystyle x^{\underline n}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i \]
还是使用归纳法证明, 有
\[ \displaystyle \begin{aligned} x^{\underline {n+1}}&=(x-n)x^{\underline n}\&=x\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i-n\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\&=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^{i+1}-(-1)*(-1)*n\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\&=\sum_{i=0}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}(-1)^{n+1-i}x^i-\begin{bmatrix}n\\0 - 1\end{bmatrix}(-1)^{n+1}x^0+(-1)*n\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\&=\sum_{i=1}^{n+1}\begin{bmatrix}n\\i - 1\end{bmatrix}(-1)^{n+1-i}x^i+n*\sum_{i = 0}^{n}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n+1-i}x^i\&=\sum_{i=1}^{n+1}\begin{bmatrix}n\\i - 1\end{bmatrix}(-1)^{n+1-i}x^i+n*\sum_{i = 0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n+1-i}x^i\&=\sum_{i=1}^{n+1}(-1)^{n+1-i}x^i(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix})\&=\sum_{i=1}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i\&=\sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i\\end{aligned} \]
故第二条性质成立

第三条

\[ \displaystyle x^{\overline n} = \sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]

同上, 假设下式成立
\[ \displaystyle x^{\overline n} = \sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]

仍使用数学归纳法证明, 有
\[ \displaystyle \begin{aligned} x^{\overline {n+1}}&= (x+n)x^{\overline n}\&=x*\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i + n * \sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i\&=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}+n*\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}x^i\&=\sum_{i=1}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^i+n*\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}x^i\&=\sum_{i=1}^{n+1}x^i(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix})\&= \sum_{i=1}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}x^i\&= \sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}x^i\\end{aligned} \]
以上只为一些简单的性质, 并不是全部的性质(然而我也不知道有哪些性质)

第二类斯特林数

\(\begin{Bmatrix}n\\m\end{Bmatrix}\)为将\(n\)个不同的数组成\(m\)个非空集合的方案数, 即第二类斯特林数


\[ \displaystyle \begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m*\begin{Bmatrix}n-1\\m\end{Bmatrix} \]
即要么第\(n\)个元素单独为一个集合, 要么将其放入之前的集合, 第二种有\(m\)个集合可供选择

第二类斯特林数的几条性质

我所知道的唯一一条

\[ \displaystyle n^m=\sum_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}*C_n^i*i! \]

假设下式成立
\[ \displaystyle n^m=\sum_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}*C_n^i*i! \]
使用数学归纳法证明
\[ \displaystyle \begin{aligned} n^{m+1}&=n^m*n\&=n*\sum_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}*C_n^i*i!\&=\sum_{i=0}^{m+1}n*\begin{Bmatrix}m\\i\end{Bmatrix}*C_n^i*i!\&=\sum_{i=0}^{m+1}n*\begin{Bmatrix}m\\i\end{Bmatrix}*\frac{n!}{i!*(n-i)!}*i!\&=\sum_{i=0}^{m+1}n*\begin{Bmatrix}m\\i\end{Bmatrix}*\frac{n!}{(n-i)!}\&=n!*\sum_{i=0}^{m+1}\frac{n*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}\&=n!*\sum_{i=0}^{m+1}\frac{i*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}+\frac{(n-i)*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}\&=n!*\sum_{i=0}^{m+1}\frac{i*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}+\frac{\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i-1)!}\&= n!*(\sum_{i=0}^{m+1}\frac{i*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}+\sum_{i=1}^{m+1}\frac{\begin{Bmatrix}m\\i-1\end{Bmatrix}}{(n-i)!})\&= n!*(\sum_{i=1}^{m+1}\frac{i*\begin{Bmatrix}m\\i\end{Bmatrix}}{(n-i)!}+\sum_{i=1}^{m+1}\frac{\begin{Bmatrix}m\\i-1\end{Bmatrix}}{(n-i)!})\&= n!*\sum_{i=1}^{m+1}\frac{i*\begin{Bmatrix}m\\i\end{Bmatrix}+\begin{Bmatrix}m\\i-1\end{Bmatrix}}{(n-i)!}\&= n!*\sum_{i=1}^{m+1}\frac{\begin{Bmatrix}m+1\\i\end{Bmatrix}}{(n-i)!}\&= n!*\sum_{i=0}^{m+1}\frac{\begin{Bmatrix}m+1\\i\end{Bmatrix}}{(n-i)!}\&= \sum_{i=1}^{m+1}\frac{n!*\begin{Bmatrix}m+1\\i\end{Bmatrix}}{(n-i)!}\&= \sum_{i=1}^{m+1}\frac{n!*\begin{Bmatrix}m+1\\i\end{Bmatrix}}{i!*(n-i)!}*i!\&= \sum_{i=1}^{m+1}\begin{Bmatrix}m+1\\i\end{Bmatrix}*\frac{n!}{i!*(n-i)!}*i!\&= \sum_{i=1}^{m+1}\begin{Bmatrix}m+1\\i\end{Bmatrix}*C_n^i*i!\&= \sum_{i=0}^{m+1}\begin{Bmatrix}m+1\\i\end{Bmatrix}*C_n^i*i!\\end{aligned} \]
故此性质成立

斯特林数学习笔记

标签:之前   全部   方式   n-1   数组   个数   -i   不同   然而   

原文:https://www.cnblogs.com/ztlztl/p/11178785.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号