CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:namespace:stirling数 [2020/08/04 21:53]
great_designer [第一类Stirling数的Lucas定理]
+++ 2020-2021:teams:namespace:stirling数 [2020/08/05 22:14] (当前版本)
great_designer [生成函数]
@@ 行 310: / 行 310: @@
 所以完全同样的可以写出第一类Stirling数与绝对值的Lucas定理：
-$$\sum_{k=0}^{n_1p+n_2} s_1(n_1p+n_2,k)x^k \equiv {(x^p-x)}^{n_1}\sum_{k=0}^{n_2} s_1(n_2,k)x^k=x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} s_1(n_2,k)x^k \mod p$$
+$$\sum_{k=0}^{n_1p+n_2} s_1(n_1p+n_2,k)x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} s_1(n_2,k)x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} s_1(n_2,k)x^k \mod p$$
-$$\sum_{k=0}^{n_1p+n_2} |s_1(n_1p+n_2,k)|x^k \equiv {(x^p-x)}^{n_1}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k=x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k \mod p$$
+$$\sum_{k=0}^{n_1p+n_2} |s_1(n_1p+n_2,k)|x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k \mod p$$
+也有第二类Stirling数按列的Lucas定理。
+$$\sum_{n=k_1p+k_2}^{\infty} S_2(n,k_1p+k_2)x^n\equiv \frac{x^{pk_1}}{{(1-x^{p-1})}^{k_1}}\sum_{n=k_2}^{\infty} S_2(n,k_2)x^n=x^{pk_1}\sum_{t=0}^{\infty} C_{k_1-1+t}^{k_1-1}x^{(p-1)t}\sum_{n=k_2}^{\infty} S_2(n,k_2)x^n\mod p$$
+对于第二类Stirling数，这个式子可以直接展开。记带余除法：
+$$n-(k_1p+k_2)=n_1(p-1)+n_2$$
+其中n_2取值为0到p-2。则有：
+$$S_2(k_1p+k_2+n_1(p-1)+n_2,k_1p+k_2)\equiv\sum_{t=0}^{n_1} C_{k_1+n_1-t-1}^{k_1-1}S_2(k_2+n_2+(p-1)t,k_2)\mod p$$
+这是一个较复杂的卷积式，并不是一一对应的化归，但是总之将情况化归到了0到p-1列的某一列中。
 ====奇偶性====
-显然带不带绝对值奇偶性都是一样的，乘不乘-1奇偶性也是一样的。令n_2为0或者是1：
+对于第一类Stirling数，显然带不带绝对值奇偶性都是一样的，乘不乘-1奇偶性也是一样的。令n_2为0或者是1：
-$$\sum_{k=0}^{2n_1} s_1(2n_1,k)x^k \equiv x^{n_1}{(x-1)}^{n_1}\sum_{k=0}^{0} s_1(0,k)x^k=x^{n_1}\sum_{t=0}^{n_1}C_{n_1}^tx^t \mod 2$$
+$$\sum_{k=0}^{2n} s_1(2n,k)x^k \equiv x^{n}{(x-1)}^{n}\sum_{k=0}^{0} s_1(0,k)x^k=x^{n}\sum_{t=0}^{n}C_{n}^tx^t \mod 2$$
-$$\sum_{k=0}^{2n_1+1} s_1(2n_1+1,k)x^k \equiv x^{n_1}{(x-1)}^{n_1}\sum_{k=0}^{1} s_1(1,k)x^k=x^{n_1+1}\sum_{t=0}^{n_1}C_{n_1}^tx^t \mod 2$$
+$$\sum_{k=0}^{2n+1} s_1(2n+1,k)x^k \equiv x^{n}{(x-1)}^{n}\sum_{k=0}^{1} s_1(1,k)x^k=x^{n+1}\sum_{t=0}^{n}C_{n}^tx^t \mod 2$$
 也就是说，每一行前面一半全是偶数，后面一半与它一半的那一行组合数奇偶性相同。
+对于第二类Stirling数，令k_2是0或1。由于第0列只有0的位置是1，第1列从1开始全是1，所以：
+$$S_2(2k_1+n,2k_1)\equiv C_{k_1+n-1}^{k_1-1}\mod 2$$
+$$S_2(2k_1+1+n,2k_1+1)\equiv\sum_{t=0}^{n} C_{k_1+t-1}^{k_1-1}=C_{k_1+n}^{k_1}\mod 2$$
 ====奇素数====
-接下来必须假设p不是2，即p是奇素数。
+接下来必须假设p不是2，即p是奇素数。由于只有第一类Stirling数有一一对应的化归，所以只研究第一类Stirling数。
 二项式展开：

CVBB ACM Team

用户工具

站点工具

页面工具