2020-2021:teams:namespace:stirling数
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:stirling数 [2020/08/04 21:35] great_designer [生成函数] |
2020-2021:teams:namespace:stirling数 [2020/08/05 22:14] (当前版本) great_designer [生成函数] |
||
|---|---|---|---|
| 行 113: | 行 113: | ||
| =====定义式===== | =====定义式===== | ||
| + | |||
| + | ====普通定义==== | ||
| 首先限定下面几个式子的n的全体，n_1到n_k为正整数，并且： | 首先限定下面几个式子的n的全体，n_1到n_k为正整数，并且： | ||
| 行 137: | 行 139: | ||
| $$s_1(n,2)={(-1)}^n (n-1)!H_{n-1}$$ | $$s_1(n,2)={(-1)}^n (n-1)!H_{n-1}$$ | ||
| + | |||
| + | ====负下标==== | ||
| + | |||
| + | 如果利用下文的递推式，强行推广至负下标，会得到这样的结论： | ||
| + | |||
| + | $$s_1(n,k)={(-1)}^{n+k}S_2(-k,-n)$$ | ||
| =====递推式===== | =====递推式===== | ||
| 行 171: | 行 179: | ||
| =====生成函数===== | =====生成函数===== | ||
| + | |||
| + | ====指数型生成函数==== | ||
| 因为上面列出的数表都是下三角形矩阵，所以对于每一行，长度都是有限的，而对于每一列，长度都是无限的。如果配上两个变元x与y，就能写出二元的生成函数。 | 因为上面列出的数表都是下三角形矩阵，所以对于每一行，长度都是有限的，而对于每一列，长度都是无限的。如果配上两个变元x与y，就能写出二元的生成函数。 | ||
| - | 先看Bell数，Bell数是同行（固定n，对全体k求和）第二类Stirling数的和。对于Bell数，有**指数型生成函数**。指数型生成函数就是每项下面要配一个阶乘，就像指数的展开式一样： | + | 先看Bell数，Bell数是同行（固定n，对全体k求和）第二类Stirling数的和。对于Bell数，有指数型生成函数。指数型生成函数就是每项下面要配一个阶乘，就像指数的展开式一样： |
| $$B(x)=\sum_{n=0}^{\infty} \frac{B_n}{n!}x^n=e^{e^x-1}$$ | $$B(x)=\sum_{n=0}^{\infty} \frac{B_n}{n!}x^n=e^{e^x-1}$$ | ||
| 行 196: | 行 206: | ||
| 它是多项式，阶乘比只是一种形式上的记号，这里提前说明。 | 它是多项式，阶乘比只是一种形式上的记号，这里提前说明。 | ||
| - | 对于第一类Stirling数，还有按行的**普通生成函数**，直接配上系数，没有阶乘做分母： | + | ====普通生成函数==== |
| + | |||
| + | 对于第一类Stirling数，有按行的普通生成函数，直接配上系数，没有阶乘做分母： | ||
| $$\sum_{k=0}^{n} s_1(n,k)x^k=\frac{x!}{(x-n)!}$$ | $$\sum_{k=0}^{n} s_1(n,k)x^k=\frac{x!}{(x-n)!}$$ | ||
| 行 210: | 行 222: | ||
| 也就是说，除了两端的第一类Stirling数，第p行中间的第一类Stirling数都被p整除。 | 也就是说，除了两端的第一类Stirling数，第p行中间的第一类Stirling数都被p整除。 | ||
| - | 第二类没有按行的结论，只有按列的结论： | + | 第二类没有按行的结论，但有按列的结论： |
| $$\sum_{n=0}^{\infty} S_2(n,k)x^n=\frac{x^k}{(1-x)(1-2x)……(1-kx)}$$ | $$\sum_{n=0}^{\infty} S_2(n,k)x^n=\frac{x^k}{(1-x)(1-2x)……(1-kx)}$$ | ||
| + | |||
| + | 也有同余式： | ||
| + | |||
| + | $$\sum_{n=0}^{\infty} S_2(n,p)x^n=\frac{x^p}{(1-x)(1-2x)……(1-px)}\equiv \frac{x^p}{1-x^{p-1}}\mod p$$ | ||
| 行 274: | 行 290: | ||
| 运用这个结论，几乎是显然的。我们还可以借此构造更多的实例，在此就不写了。 | 运用这个结论，几乎是显然的。我们还可以借此构造更多的实例，在此就不写了。 | ||
| - | =====第一类Stirling数的Lucas定理===== | + | =====Lucas定理===== |
| ====生成函数==== | ====生成函数==== | ||
| 行 294: | 行 310: | ||
| 所以完全同样的可以写出第一类Stirling数与绝对值的Lucas定理： | 所以完全同样的可以写出第一类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数。 |
| 二项式展开： | 二项式展开： | ||
2020-2021/teams/namespace/stirling数.1596548128.txt.gz · 最后更改: 2020/08/04 21:35 由 great_designer
