YPE htmlhtmlheadtitle data-vue-meta=true第一类Stirling数的Lucas定理 – 哔哩哔哩

YPE htmlhtmlheadtitle data-vue-meta=true第一类Stirling数的Lucas定理 – 哔哩哔哩

我觉得高中数论中的Lucas定理大家基本上已经熟悉了,就是组合数的简单结论:

现在谈到第一类Stirling数也有相应的Lucas定理。为了介绍这种形式的Lucas定理,先要定义第一类Stirling数。

所以第一类Stirling数有正有负。当n和k奇偶性相同的时候为正,不同的时候为负,并且第n行的第0项总是0,第1项是(n-1)的阶乘,第n项总是1。

这是为什么呢?因为这个多项式在模p意义下有0到p-1全体根,而首项系数为1的p次多项式中,x的p次方减x也有全体根。两者作差之后次数不够p次,却也有全体根,由Lagrange定理,差只能为0,即两者同余。

这个同余式就是第一类Stirling数的Lucas定理的全部内容。由于同余式的含义是对应系数同余,事实上是整个这一行的系数都对应同余。换句话说,Lucas定理将整个一行的第一类Stirling数余数情况化归到了前p-1行中的某一行的情况。

仅写成这样虽然包揽了全体情况,却还是有些抽象,不够具体。接下来需要细分成各种具体情况进行讨论。

首先,当p等于2时,上述式子就是在讨论第一类Stirling数的奇偶性。

这相当于直接化归到了第0行和第1行。那么利用二项式展开,两种情况分别列出就是:

也就是说,每一行前面一半全是偶数,后面一半与它一半的那一行组合数奇偶性相同。合成一个式子就是:

可以假设n_2不超过p,即化归后到了前p-1行。原来一行的前n_1个数(k为0到n_1-1)都被p整除。

观察式中组合数部分。组合数部分每两项之间距离是p-1,但是后面k跑遍的部分是0到p-1,有p个数,会不会造成重叠?

不会。因为第一类Stirling数数表的形状:前p-1行中,只有第0行在第0列有数1,其余行在第0列都没有数(为0);但是第0行,也只有在第0列有数1,在其余列都没有数。这就保证它们可以按照p-1的周期重复而不重叠。

为了方便讨论,将以上区分为第0行和1到p-1行两种情况,即整除与不整除两种情况。

即p的n_1倍数行,前n_1个数(0到n_1-1)被p整除,从第n_1个数开始后面每p-1个数中(p-1是偶数,因此奇偶性相同)才有一个不被p整除,并且与第n_1行对应的组合数(配上-1的系数)同余。即仅当k-n_1是p-1倍数时不被p整除:

当n_2不等于0时,前n_1个数(0到n_1-1)仍旧被p整除。于是这里认为k至少为n_1,将k-n_1(原来k属于靠右的n-n_1列)做带余除法,只是除数换成p-1,有:

这里规定,k_2的取值范围是1到p-1,与通常的带余除法略有不同。由于k不超过n,而n有这个式子:

即从n_1开始,第k_1个连续p-1化归到了第一类Stirling数第n_2行的1到p-1位置,以及组合数的第n_1行的k_1位置。这样就完成了递归。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注