偏序(斯特林，组合数)

偏序(斯特林，组合数)

此贴留坑，日后再填。

集合

---

集合的元素可以是一个集合。
空集是任何集合的子集，所以空集独有一个特性：

$$\phi \in \lbrace \phi \rbrace,\phi \subset \lbrace \phi \rbrace$$

偏序

---

($\forall$：对于所有的)
现在有集合$U$，令$R \subset U \times U$。
令U中的元素为$\lbrace u_ 1,u_ 2,...,u_ k\rbrace$
则$R \subset \lbrace \lbrace u_ i,u_ j \rbrace \rbrace(1 \leq i,j \leq k)$

把$xRy$看成是一种返回$bool$值的运算符。

• 若$\forall x \in U ,(x,x) \in R,$则$R$具有自反性。
• $x \not R x$ 反自反
• $xRy, yRz \Rightarrow xRz$ 传递性
• $x \neq y , xRy \Rightarrow yRx$ 对称性
• $x \neq y , xRy \Rightarrow y \not R x$ 反对称

---

• 偏序：自反，传递，反对称($\leq,x \|y,x \subset y$)
• 严格偏序：反自反，传递，反对称($<,$)
• 等价：自反，传递，对称($=,\equiv,\cong,\sim$)

全序：对于$\forall x,y$，必有$xRy$或$yRx$(可比)

链的定义：在集合中选出一些数组成链，使得对于$a_ i$和$a_ {i+1}$，必有$a_ iRa_ {i+1}$(等价于链中任意两元素可比)。
反链定义：对于反链中的$\forall a,b$，$a,b$都不可比。
反dilworth定理：一个构成最少的反链个数等于其能够组成的最长链的长度。
把偏序看成一张图。
每次取入度为0的点出来构成一条反链。
删掉点，重复操作。
次数为原图中的最长链。

偏序函数

---

一个函数$f(x,y)$若属于偏序函数，则有：
仅当满足$xRy$时，$f(x,y)$值才可能不为零。
（比如$x \leq y$，所以C(),A(),斯特林数都是偏序函数了）

偏序函数卷积定义：若$a \otimes b = c$
则$c(x,y) = \sum_ z a(x,z) \times b(z,y)$

既然有卷积，那就一定有单位根和逆元
可以想一下构造一个函数$e$，使得任何一个函数$a \otimes e = a$
那也就是说$(x,y)$上的值只能从$(x,y)$那里转移过来
那这样$e$就是$e(x,y)=[x==y]$了

卷积不满足交换律，但满足结合律，具体证明展开($a \otimes (b \otimes c)$)搞事情。
设函数$f$的左逆元为$a$,右逆元为$b$
有$a \otimes f = e,f \otimes b = e$
$a = a \otimes e = a \otimes (f \otimes b) = (a \otimes f) \otimes b=b$

现在要求$f$的逆元。
在单位根上只有$e(x,x)$的值为一，而对于$a \otimes b$后的$(x,x)$的值，根据卷积的定义只能由$a(x,x) \times b(x,x)$得来。
所以$ f^{-1}(x,x)=\frac{1}{f(x,x)}$
现在对求偏序卷积的式子进行一些操作
$\sum_{x \leq z \leq y} f(x,z) \times f^{-1}(z,y) =[x==y]$
然后把$z$最小的那一项提出来
$[x==y]+f(x,z) \times f^{-1}(x,y) = \sum_ {x < z \leq y} f^{-1}(x,z) \times f(z,y)$
最后对于每一个$y$，从大到小枚举$x$，求$f^{-1}(x,y)$

一些偏序函数的Interesing应用

---

是否还记得狄利克雷卷积中的$id_ 0$？
这里他复出了，或者说，这才是他本应有的样子。
由于偏序是一个广泛（抽象？)的概念，所以这里$id_ 0$也会随着$R$的定义改变而不同。

若$xRy$表示$x \leq y$
则$id_ 0(x,y)=[x \leq y]$
$id_ 0^{-1}=-1(y=x+1),1(y=x),0(otherwise)$
新建一个函数$a(1,y)=p_ y$
令$a^+=a \otimes id_ 0$
于是$a ^ + (1,n)=\sum_ k a(1,k) id_ 0(k,n)$
前缀和？
仔细想想$id_ 0^{-1}$在干的事情，会发现-1,1这个规律的数字组是在用差分从前缀和还原出原数组。

若$xRy$表示$x|y$则反演
一维？
$f(n)=\sum_ {d|n} g(d)\mu(\frac{n}{d})$

若$xRy$表示$x \subset y$则容斥

这又与斯特林和组合数何干？

---

一些定义

$n^ {\underline{k}} =n \times (n-1) \times (n-2) \times ... \times (n-k+1)$，代表$n$的$k$次下降幂。
$n^ {\overline{k}}=n \times (n+1) \times (n+2) \times ... \times (n+k-1)$，代表$n$的$k$次上升幂。
$(^a_ b)=\frac{a!}{b!(a-b)!}$，$a$取$b$
$[ ^a_ b]$：第一类斯特林数，代表$a$轮$b$，即a个点放入b个相同的环。
$\lbrace ^a_ b\rbrace$： 第二类斯特林数，代表a个点放入b个相同的集合。
需要注意的是，斯特林数是可以逆推回负数的，而且值关于(0,0)对称。

二项式反演

$(^a_ b) \otimes (-1)^{a-b} (^a_b )=e$

$\sum_ c (^a_c)(-1)^{c-b}(^c_ b)$
$=\sum_ c(-1)^{c-b}(^a_ c)(^c_ b)$
(其中$(^a_ c)(^c_ b)$的组合意义可以理解为在一个大范围内确定大圈，然后再里面找一个小圈。
这样等价于找一个小圈，再枚举可以贡献到多少个大圈上。)
$=\sum_ c(-1)^{c-b}(^a_ b)(^{a-b}_ {c-b})$
$=(^a_ b)\sum_ c(-1)^{c-b}(^{a-b}_ {c-b})$
$=(^a_ b)(1-1)^ {a-b}$
$=(^a_ b)[ a = b ] =e$

斯特林

$n^{\overline{m}}=\sum _ k [ ^n_k ]n^k$
$n^m= \sum _ k \lbrace ^m_ k \rbrace n^{\underline{k}}$
(这个式子可以用来求第二类斯特林，下面讲推导)
$[^a_ b] \otimes (-1)^{a-b} \lbrace ^a_ b \rbrace =e$

$\lbrace ^a _ b \rbrace \otimes (-1)^{a-b} [^a_ b] =e$
这里用归纳证明：
$\sum_ c \lbrace ^a_ c \rbrace (-1)^{c-b} [^c_ b]$
代入第二类斯特林数的递推式
$=\sum_ c ( \lbrace ^{a-1}_ c \rbrace \times c + \lbrace ^{a-1}_ {c-1} \rbrace)(-1)^{c-b}[^c_ b]$
$=\sum_ c \lbrace ^{a-1}_ {c-1} \rbrace (-1) ^ {c-b} [ ^c _ b ]+\sum _ c c \lbrace ^{a-1}_ c \rbrace (-1) ^ {c-b} [^c _ b]$
代入第一类斯特林数的递推式
$=\sum _ c \lbrace ^ {a-1}_ {c-1} \rbrace (-1) ^ {c-b} ( [ ^{c-1} _ b ] \times (c-1) + [ ^{c-1} _ {b-1} ] ) + \sum _ c c \lbrace ^{a-1}_ c \rbrace (-1) ^ {c-b} [^c _ b]$
由于$c$没有限制，所以可以把$c-1$看成$c$
$=\sum _ c \lbrace ^ {a-1}_ {c} \rbrace (-1) ^ {c+1-b} ( [ ^c _ b ] \times c + [ ^{c} _ {b-1} ] ) + \sum _ c c \lbrace ^{a-1}_ c \rbrace (-1) ^ {c-b} [^c _ b]$
$=\sum_ c \lbrace ^ {a-1} _ c \rbrace (-1)^ {c-(b-1)}([ ^c _ b ] \times c + [ ^{c} _ {b-1} ] - c \times [^ c _ b ])$
$=\sum_ c \lbrace ^ {a-1} _ c \rbrace (-1)^ {c-(b-1)} [ ^c _ {b-1} ]$
当$a=b$时原式为1，否则可以通过不停减少使得某项为0。

$O(nlogn)$求二类斯特林数推导

$n^m=\sum_ k \lbrace ^m_ k \rbrace n^{\underline{k}}=\sum_ k \lbrace ^m_ k \rbrace (^n_ k)k!$
左边的组合意义：$m$个不同的球放入$n$个不同的抽屉。
右边：枚举$k$,让$m$个不同的球组成$k$个集合，并将集合放入$n$个不同的抽屉。
然后开始乱搞。
两边同时乘上$(^n_ k)$的逆元
$\sum _k k^m(-1)^{n-k}(^n _ k)=\lbrace ^m _ n \rbrace n!$
$\lbrace ^m _ n \rbrace=\frac{\sum _k k^m(-1)^{n-k}(^n _ k)}{n!}$
把$(^n _ k)$写成阶乘形式并化简

$\lbrace ^m _ n \rbrace=\frac{\sum _ k k^m (-1) ^ {n-k} } { k! (n-k)! }= \sum_ k \frac { k ^ m }{ k\! } \times \frac { ( -1 ) ^ { n-k } } { (n-k) \! }$
这样就可以FFT了。