Poset(Under Construction!)

Poset

數列推廣成偏序集(反擬陣?)。

一個偏序集,子集合總和(偏序集積分)、子集合排容(偏序集微分),互為反運算。

積分前摺積 = 積分後乘法。定義祖性摺積:令兩元素的結合結果是最低共同祖先LCA。數列摺積的結合運算子是加法、乘法,偏序集摺積則是LCA。

fast zeta transform
https://mycourses.aalto.fi/mod/resource/view.php?id=90388

引入cyclic inclusion-exclusion就滿足對偶了?此時偏序集積分的效果等同於FFT、FNT等轉換。

Invitation to Algorithmic Uses of Inclusion–Exclusion
https://arxiv.org/abs/1105.2942
容斥原理与子集卷积
https://zhuanlan.zhihu.com/p/33228260
https://zhuanlan.zhihu.com/p/33254080
https://zhuanlan.zhihu.com/p/33293771
https://zhuanlan.zhihu.com/p/33328788
https://zhuanlan.zhihu.com/p/33347805
https://zhuanlan.zhihu.com/p/33376490

時間複雜度從O(Nᴺ)降到O(2ᴺN)。

範例

當偏序集是子集關係。結合運算子是聯集。

當偏序集是分割數(組合數)關係,此定理即是巴斯卡三角形。

當偏序集是因數關係,此定理即是Möbius inversion formula。此時偏序集微積分可以寫成乘性摺積:積分是摺以常數函數1,微分是摺以Möbius function μ。結合運算子是最小公倍數。

    偏序集積分
    --------->
 祖 |        | 點
 性 |        | 乘
 摺 |        |        我猜是這樣
 積 v        v
    <---------
    偏序集微分
   乘性摺積(因數關係)

Sequence + Poset

當偏序集是數列項次的因數關係。

原數列每一項除以(1+xⁱ)後z轉換,等於積分後z轉換。左式叫做Lambert series。

原數列ζ轉換、再乘上一個倍率ζ(s),等於積分後ζ轉換。

反元素:

ζ(s) = sum 1/(nˢ)
1/ζ(s) = sum u(n)/(nˢ)

Euler Product

歐拉加乘對偶。

最大公因數的傅立葉轉換就是Euler's Totient Function

http://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform

       N-1
φ(n) =  ∑ { gcd(n, k) ÷ ei⋅2π⋅(n/N)⋅k }
       k=0

Matroid(Under Construction!)

Antimatroid

反擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,聯集也要被包含
向下 規則1.
給兩三個大集合,可以有交集
每個大集合都要窮舉各種子集合,生一堆子子孫孫出來
終點(匯)顯然是空集合

向上 規則2.
給兩三個大集合,可以有交集
兩兩大集合都要窮舉各種聯集,生一堆父父祖祖出來
起點(源)顯然是宇集合

Matroid

擬陣。廣義遞迴關係。許多集合,層層包含。

可以畫成有向無環圖(層數是集合大小),整體呈菱形結構。

1. 隨便抓個集合,刪除某個元素,也要被包含 = 子集合也要被包含
2. 隨便抓兩個集合,隨便從差集找到某個元素,然後小集合添上元素,也要被包含
   隨便抓兩個集合,交集+差集子集也要被包含
1. 子集合通通不可被包含  除了空集合
2. 聯集-交集也要被包含