数的形状及Stirling数的一般计算公式

mcfrookknd

大量文章研究Stirling数的计算公式,多数通过组合计数方式推导,并未得出通用的公式
参照https:\\wenku.baidu.com/view/e5a0002a4b73f242336c5fda.html

本文通过反向递推关系推导出Stirling数一般的计算公式,整个过程浓缩只需几行,以数的形状的慨念来描述,可以获得极其简单的结论
结论是一目了然的，可以反复验证

M个不同数的乘积,因子从小到大排列,因子间共M-1个间隔,有的连续,有的有空隙(称为洞),本文定义为数的形状。
(3.2.3)F1(N,M)=第一类Stirling数 s(n,n-m)=∑MIN(PX)*C(N,IDX(PX)),求和,因子数=M 的数的形状

详细见
https:\\kdocs.cn/l/sNVOwOuA8?f=501
[金山文档] 数的形状及Stirling数的一般计算公式.pdf

或附件

mcfrookknd

(3.2.3)F1(N,M)=第一类Stirling数 s(n,n-m)=∑MIN(PX)*C(N,IDX(PX)),求和遍历因子数=M 的数的形状

mcfrookknd

简单的得到第2类Stirling数 S(N,N-8)=
C(N,9)+501*C(N,10)+22935*C(N,11)+302995*C(N,12)+1636635*C(N,13)
+4099095*C(N,14)+4729725*C(N,15)+2027025*C(N,16)

mcfrookknd

数的形状
定义M个不同正整数的无序对表示为(K1,K2...Km),把Ki 从小到大排序,相邻数间共M-1个间隔
用A代表连续,B代表空隙(称为洞),记做M-1个字符的串: AABB...代表一个类型,表示为PX
PA为PX中A数量, PB为PX中B数量

MIN(PX)为PX型中的最小积,如MIN(AA)=1*2*3,MIN(AB)=1*2*4
IDX(PX)=2+PA+2*PB=M+PB+1,如IDX(AA)=4,IDX(AB)=5
SUM(N,PX)为1到N-1中所有PX型项乘积的和,如 SUM(6,AB)=1*2*4+1*2*5+2*3*5

则可证 SUM(N,PX)=Min*C(N,Idx)

可以验证
SUM(6,AA)=1*2*3+2*3*4+3*4*5=1*2*3*C(6,4)=90
SUM(6,AB)=1*2*4+1*2*5+2*3*5=1*2*4*C(6,5)=48
SUM(6,BA)=1*3*4+1*4*5+2*4*5=1*3*4*C(6,5)=72
SUM(7,BB)=1*3*5+1*3*6+1*4*6+2*4*6=1*3*5*C(7,6)=105
SUM(8,BB)=SUM(7,BB)+1*(3+4+5)*7+2*(4+5)*7+3*5*7=1*3*5*C(8,6)=420
SUM(8,BAB)=1*3*4*6+1*(3*4+4*5)*7+2*4*5*7=576=1*3*4*6*C(8,7)
SUM(9,BAB)=SUM(8,BAB)+(3*4+4*5+5*6)*8+2*(4*5+5*6)*8+3*5*6*8=2592=Min*C(9,7)

第1类stirling数 s(N,N-M)=∑MIN(PX)*C(N,IDX(PX)),求和遍历因子数=M的PX


推出同余等式
对质数P,  因子数相同,PB相同的{PX},且PB>0,IDX(PX)=P,P>3 则∑MIN(PX)≡0 MOD P*(P-1)
例如:

ABB,BAB,BBA:Idx=71*2*4*6+1*3*4*6+1*3*5*6=5*6*7≡0MOD7*6
AAAB,AABA,ABAA,BAAA:Idx=71*2*3*4*6+1*2*3*5*6+1*2*4*5*6+1*3*4*5*6=2*11*7*6≡0MOD7*6

njzz_yy

https:\\kdocs.cn/l/sNVOwOuA8?f=501
以前不能发网址，现在能发了，谢谢！