Sequence

Sequence

「數列」。一串數字。

(4 -1 6 0 9)

我們習慣用一維陣列儲存一個數列:

以下介紹一些經典的數列運算。

加減乘除

對應項加減乘除。

加法 (1 2 3) + (4 5 6) = (1+4 2+5 3+6) = (5 7 9)

累和、差分

前項累加、鄰項相減。

累和 ∑ (4 -1 6 0 9) = (4 3 9 9 18)
差分  Δ (4 -1 6 0 9) = (4 -5 7 -6 9)

最小值、最大值、總和

靜態版本請見本站文件「Maximum Sum Subarray」。

動態版本請見本站文件「Sequence」。

最小值 min (4 -1 6 0 9) = -1
最大值 max (4 -1 6 0 9) = 9
總和  ∑ (4 -1 6 0 9) = 18

排序、搜尋、選擇、計數

請見本站文件「Sort」。

排序 (4 -1 6 0 9) → (-1 0 4 6 9)
搜尋 (4 -1 6 0 9) , 0 → 3
選擇 (4 -1 6 0 9) , 0 → -1
計數 (4 -1 6 0 9) , 0 → 1

數列搜尋

請見本站文件「String Searching」。

數列搜尋 (4 -1 6 0 9) , (0 9) → 3

排列、組合

請見本站文件「Permutation」。

排列 (4 -1 6 0 9) → (6 0 9 -1 4)
組合 (4 -1 6 0 9) → (-1 0 9)

點積、卷積

請見本站文件「Convolution」。

點積 (1 2 3) · (4 5 6) = 1×4 + 2×5 + 3×6 = 32
卷積 (1 2 3 4 5) ∗ (4 5 6) = (4 13 28 43 58 49 30)

(- - 1 2 3 4 5 - -) · (6 5 4 - - - - - -) = 4
(- - 1 2 3 4 5 - -) · (- 6 5 4 - - - - -) = 13
(- - 1 2 3 4 5 - -) · (- - 6 5 4 - - - -) = 28
(- - 1 2 3 4 5 - -) · (- - - 6 5 4 - - -) = 43
(- - 1 2 3 4 5 - -) · (- - - - 6 5 4 - -) = 58
(- - 1 2 3 4 5 - -) · (- - - - - 6 5 4 -) = 49
(- - 1 2 3 4 5 - -) · (- - - - - - 6 5 4) = 30

On-Line Encyclopedia of Integer Sequences

自古以來,數學家研發了許多特殊數列,數量成千上萬。事實上已經有熱心人士,建立百科全書:「整數數列線上大全OEIS」。每當遇到陌生數列,可以在網站上尋找參考文獻。

Sequence (Arithmetic)

Sequence運算

    result (noun)
--- --------------------------
+   direct sum     直和(加法)
×   direct product 直積(乘法)
·   dot product    點積
∗   convolution    卷積
註:芒星asterisk、角星star是不同東西。
  芒星*(U+002A)、角星★(U+2605)
  芒星運算子∗(U+2217)、角星運算子⋆(U+22C6)
  卷積運算符號是六芒星,最理想的字元是芒星運算子∗(U+2217)。
  根據字型選擇,芒星運算子可能顯示五芒星、六芒星、八芒星。

加減乘除

對應項加減乘除。

(a₀ a₁ a₂) + (b₀ b₁ b₂) = (a₀+b₀ a₁+b₁ a₂+b₂)

點積

對應項相乘,通通加總。

(a₀ a₁ a₂) ∙ (b₀ b₁ b₂) = a₀b₀ + a₁b₁ + a₂b₂

卷積

許多次點積。第二串數列頭尾顛倒(迎合多項式乘法);窮舉各種對齊方式,各做一次點積(卷積的名稱由此而來)。

(a₀ a₁ a₂ a₃ a₄) ∗ (b₀ b₁ b₂) = (c₀ c₁ c₂ c₃ c₄ c₅ c₆)

c₀: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (b₂ b₁ b₀ -  -  -  -  -  - )

c₁: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  b₂ b₁ b₀ -  -  -  -  - )

c₂: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  b₂ b₁ b₀ -  -  -  - )

c₃: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  -  b₂ b₁ b₀ -  -  - )

c₄: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -   -  - b₂ b₁ b₀ -  - )

c₅: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -  -  -  -  b₂ b₁ b₀ - )

c₆: (-  -  a₀ a₁ a₂ a₃ a₄ -  - )
    (-  -   -  -  -  - b₂ b₁ b₀)

循環卷積

超出數列的部分,改成頭尾循環。

(a₀ a₁ a₂ a₃ a₄) ⊛ (b₀ b₁ b₂ b₃ b₄) = (c₀ c₁ c₂ c₃ c₄)

c₀:               c₁:               c₂:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₀ b₄ b₃ b₂ b₁)  (b₁ b₀ b₄ b₃ b₂)  (b₂ b₁ b₀ b₄ b₃)

c₃:               c₄:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₃ b₂ b₁ b₀ b₄)  (b₄ b₃ b₂ b₁ b₀)

Sequence (Calculus)(Under Construction!)

Sequence運算

    result (noun)
--- -------------------------------------------------
    cumulative sum    累積和 (前綴和) (離散積分)
Δ   finite difference 有限差分(向前差分)(離散微分) 分什麼分
註:累積和運算符號,目前尚未定義。
註:有限差分運算符號,源自微積分的變化量符號Δ。注意到是Δy而不是Δx。
  視為動作,應該是梯度∇。視為結果,才是變化量Δ。

Additive Integral(Cumulative Sum)(Summatory Function)

「加性積分」。至今每一項相加。O(N)。

(a₀ a₁ a₂ a₃ a₄) ---> (a₀ a₀+a₁ a₀+a₁+a₂ a₀+a₁+a₂+a₃ a₀+a₁+a₂+a₃+a₄)
數列 (4 -1  6  0  9)
累和 (4  3  9  9  18)
b(n) = sum a(i)
       i≤n

UVa 10324 10994 983

Additive Derivative(Finite Difference)

「加性微分」。相鄰數字差。O(N)。

累和與鄰差互為反運算!可以相互抵消!一個數列,先累和、再鄰差,仍是原數列。一個數列,先鄰差、再累和,仍是原數列。

數列 (4 -1  6  0  9)
鄰差 (4 -5  7 -6  9)
(a₀ a₁ a₂ a₃ a₄) ---> (a₀ a₁-a₀ a₂-a₁ a₃-a₂ a₄-a₃)
a(n) = b(n) - b(n-1)

UVa 10038

Multiplicative Integral

「乘性積分」。因數項相加。O(NloglogN)。

(a₁ a₂ a₃ a₄ a₅) ---> (a₁ a₁+a₂ a₁+a₃ a₁+a₂+a₄ a₅)
b(n) = sum a(i)
       i|n

luogu P5495

Multiplicative Derivative

「乘性微分」。質因數排容。O(NloglogN)。

a(n) = sum b(i) μ(i;n)
       i|n

Subset Integral

「子集積分」。子集項總和。

b(n) = sum a(i)
       i⊆n

Subset Derivative

「子集微分」。

Poset Integral(Zeta Transform)

「偏序集積分」。

b(n) = sum a(i)
       i≤n

Poset Derivative(Möbius Transform)

「偏序集微分」。

a(n) = sum b(i) μ(i;n)
       i≤n

Sequence (Convolution)(Under Construction!)

Additive Convolution(Cauchy Product)

「加性卷積」。配對運算是加法運算。

c(n) = sum a(i)b(j) = sum a(i)b(n-i) = sum a(n-i)b(i)
      i+j=n           i≤n              i≤n

當b數列全是1,即是加性積分。後面小節以此類推。

演算法是Fast Fourier Transform。O(NlogN)。

請見本站文件「Convolution」。

Multiplicative Convolution(Dirichlet Convolution)

「乘性卷積」。配對運算是乘法運算。

c(n) = sum a(i)b(j) = sum a(i)b(n/i) = sum a(n/i)b(i)
      i×j=n           i|n              i|n

目前沒有高速演算法。演算法是Divide and Conquer。計算一項的時間複雜度O(n¾)。乘性函數降至O(n)。

請見本站文件「Convolution」。

Subset Convolution

「子集卷積」。配對運算是互斥聯集運算。

c(n) = sum a(i)b(j) = sum a(i)b(n\i) = sum a(n\i)b(i)
      i⊔j=n           i⊆n              i⊆n

Poset Convolution

「偏序集卷積」。配對運算是小於等於運算。

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

積分前卷積 = 積分後乘法。定義祖性卷積:令兩元素的結合結果是最低共同祖先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

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

Poset Convolution

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

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

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

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

Dyadic Convolution

「二元卷積」。配對運算是位元運算AND、OR、XOR。

希臘語dyadic、拉丁語binary,兩者同義。數學家喜歡dyadic,計算學家喜歡binary。

c(n) = sum a(i)b(j) = sum a(i)b(n∧i) = sum a(n∧i)b(j)   bitwise AND
      i∧j=n           i⊆n              i⊆n
c(n) = sum a(i)b(j) = sum a(i)b(n∨i) = sum a(n∨i)b(j)   bitwise OR
      i∨j=n           i⊆n              i⊆n
c(n) = sum a(i)b(j) = sum a(i)b(n⊕i) = sum a(n⊕i)b(j)   bitwise XOR
      i⊕j=n           i⊆n              i⊆n

二進位數字視作集合,AND、OR、XOR視作交集、聯集、聯集減交集。

演算法仿照Fast Walsh-Hadamard Transform。O(NlogN)。

https://taodaling.github.io/blog/2019/04/24/快速沃尔什变换/

luogu P4717

Sequence (Series)

數列函數轉換【尚無正式名稱,也許是Generating Function】

離散數列、連續函數,互相轉換!

轉換方式,無限可能,自由發揮。

數學家並未命名轉換過程,只命名轉換結果:「生成函數」。

(2 -5  1  0  4)  ⟷  2x¹ - 5x¹ + 1x² + 0x³ + 4x⁵
 sequence a(n)         generating function f(x)

生成函數的其中一種經典形式是各項相加:「級數」。

一、冪級數:指數是索引值(從0開始)。

二、狄利克雷級數:底數是索引值(從1開始)。

(2 -5  1  0  4)  ⟷  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
                          power series
(2 -5  1  0  4)  ⟷  2⋅1ˣ - 5⋅2ˣ + 1⋅3ˣ + 0⋅4ˣ + 4⋅5ˣ
                          Dirichlet series

數列函數轉換的對應運算【尚無正式名稱】

離散數列運算、連續函數運算,互相對應。

對應運算,請見本站文件「Transformation」。

一、離散數列加法減法=連續函數加法減法。

(2 -5  1)  ⟷  2x⁰ - 5x¹ + 1x²
    +                 +
(1 -1  0)  ⟷  1x⁰ - 1x¹ + 0x²
    ‖                 ‖
(3 -6  1)  ⟷  3x⁰ - 6x¹ + 1x²

二、離散數列乘法除法=未定義。

(2 -5  1)  ⟷  2x⁰ - 5x¹ + 1x²
    ×          no such operator
(1 -1  0)  ⟷  1x⁰ - 1x¹ + 0x²
    ‖                 ‖
(2  5  0)  ⟷  2x⁰ + 5x¹ + 0x²

三、離散數列卷積反卷積=連續函數乘法除法。

離散數列的卷積運算,源自於連續函數的乘法運算。數學家故意將兩者定義成一樣。

(2 -5  1)        ⟷  2x⁰ - 5x¹ + 1x²
    ∗                       ×
(1 -1  0)        ⟷  1x⁰ - 1x¹ + 0x²
    ‖                       ‖
(2 -7  7  1  0)  ⟷  2x⁰ - 7x¹ + 7x² + 1x³ + 0x⁴

四、未定義=連續函數卷積反卷積。

(2 -5  1)        ⟷  2x⁰ - 5x¹ + 1x²
no such operator            ∗
(1 -1  0)        ⟷  1x⁰ - 1x¹ + 0x²
    ‖                       ‖
    ?            ⟷         ?

係值轉換【尚無正式名稱,也許是Evaluation Isomorphism】

係數、函數值,互相轉換!

需要事先決定:級數是哪種、x值是哪些。

            2x⁰ - 5x¹ + 1x²
(2 -5  1)  <———————————————>  (2 -4  8)
             x = {0, 2, 6}

級數視作線性函數、寫做矩陣。令反矩陣存在,以保證一對一轉換。令x值數量等同數列長度、令x皆相異,以保證反矩陣存在。

線性函數,請見本站文件「Linear Function」。

[ 0⁰ 0¹ 0² ] [  2 ]   [  2 ]
[ 2⁰ 2¹ 2² ] [ -5 ] = [ -4 ]
[ 6⁰ 6¹ 6² ] [  1 ]   [  8 ]

係值轉換的對應運算【尚無正式名稱】

一、係數加法減法=函數加法減法=函數值加法減法。

            2x⁰ - 5x¹ + 1x²
(2 -5  1)  <———————————————>  (2 -4  8)
    +                             +
            1x⁰ - 1x¹ + 0x²
(1 -1  0)  <———————————————>  (1 -1 -5)
    ‖                             ‖
            3x⁰ - 6x¹ + 1x²
(3 -6  1)  <———————————————>  (3 -5  3)
             x = {0, 2, 6} 

二、係數卷積反卷積=函數乘法除法=函數值乘法除法。

                        2x⁰ - 5x¹ + 1x²
(2 -5  1)        <———————————————————————————>  (2 -4  8)
    ∗                                               ×
                        1x⁰ - 1x¹ + 0x²
(1 -1  0)        <———————————————————————————>  (1 -1 -5)
    ‖                                               ‖
                  2x⁰ - 7x¹ + 7x² + 1x³ + 0x⁴
(2 -7  7  1  0)  <———————————————————————————>  (2  4 -40)
                         x = {0, 2, 6}

Sequence (Calculus)(Under Construction!)

備忘

L'Hôpital's rule: a/b = a'/b'
https://en.wikipedia.org/wiki/L%27H%C3%B4pital%27s_rule

Lambert series: a/Δa = a∗*1 , a = Δa∗⁺1
https://en.wikipedia.org/wiki/Lambert_series

Perron's formula:
https://en.wikipedia.org/wiki/Perron%27s_formula
https://en.wikipedia.org/wiki/Abel%27s_summation_formula

Lagrange inversion theorem: a⁻¹()
https://en.wikipedia.org/wiki/Lagrange_inversion_theorem
https://en.wikipedia.org/wiki/Formal_power_series
Hasse-Teichmüller derivatives order k: aₙ xⁿ -> C(n,k) aₙ xⁿ⁻ᵏ
https://en.wikipedia.org/wiki/Hasse_derivative
https://en.wikipedia.org/wiki/Umbral_calculus

difference operator: (Δf)(n) = f(n+1) - f(n)
Δ(n³) = (n+1)³ - n³ = 3n² + 3n + 1

shift operator: E