GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 学习笔记
  3. 正文

第二类斯特林数学习笔记

2019年02月25日 418点热度 0人点赞 0条评论

本菜鸡尚未学会第二类斯特林数,请各位dalao不要相信本文的任何一个字


什么是第二类斯特林数

在组合数学,Stirling数可指两类数,第一类Stirling数和第二类Stirling数,都是由18世纪数学家James Stirling提出的。
Stirling数有两种,第一类和第二类Stirling数,它们自18世纪以来一直吸引许多数学家的兴趣,如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根(Copenhagen)大学的尼尔森(Niels Nielsen,1865-1931)提出了"Stirlingschen Zahlen erster Art" [第一类Stirling数]和"Stirlingschen Zahlen zweiter Art" [第二类Stirling数],首次把这两类数冠以「Stirling数」之名 。因为苏格兰数学家斯特林(J. Stirling, 1692-1770)首次发现这些数并说明了它们的重要性。 ——百度百科

用人话来说,第二类斯特林数$S(i,j)$用来表示i个不一样的球放入j个相同盒子里的方案数。


怎么算第二类斯特林数

我们可以假设当前这个球是单独放一个盒子还是放入有别的球的盒子中,如果单独放一个盒子,显然答案为$S(i-1,j-1)$,如果放入别的盒子中,因为它放在不同的盒子后能与盒子中原本有的球组成不同的方案,因此我们要在$S(i-1,j)$前面乘以盒子总数$j$

因此,我们可以得到以下递推式:

$S(i,j)=S(i-1,j-1)+j*S(i-1,j)$

还有一个我并不会证的通项公式,会证之后再补(咕咕咕)

$S(n,m)={\frac 1 {m!}}\sum_{k=0}^m (-1)^k C(m,k)(m-k)^n$


第二类斯特林数有啥性质

有且只有一个,而且我也不会证,会证后补(咕咕咕)

$n^k=\sum_ { i=0}^n S(k,i)×i!×C(n,i)$

这个式子主要用于算一些蜜汁幂次方的时候可以用得到,例如这道题

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 学习笔记 数学
最后更新:2019年02月25日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 34
  • 23
  • 79,010
  • 22,848

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号