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
總乘積 ∏ (4 -1 6 0 9) = 0

排序、搜尋、選擇、計數

請見本站文件「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₂)

點積

對應項相乘,通通加總。

可以直接使用C++標準函式庫的inner_product()。

(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

additive integration【尚無正式名稱】
(cumulative sum)(prefix sum)

「加性積分」或「累積和」或「前綴和」。至今每一項相加。

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

演算法是動態規劃。時間複雜度O(N)。

可以直接使用C++標準函式庫的partial_sum()。

UVa 10324 10994 983

additive differentiation【尚無正式名稱】
(adjacent difference)(finite difference)

「加性微分」或「相鄰差」或「有限差分」。相鄰項相減。

累和與鄰差互為反運算!可以相互抵消!先累和、再鄰差,仍是原數列。先鄰差、再累和,仍是原數列。後面小節以此類推。

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

演算法是動態規劃。時間複雜度O(N)。

可以直接使用C++標準函式庫的adjacent_difference()。

UVa 10038

multiplicative integration(Möbius transformation)
multiplicative differentiation(Möbius inversion)
【尚無正式名稱】

「乘性積分」。因數項相加。

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

「乘性微分」。因數項取捨。

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

其中μ(n)是質因數取捨函數Möbius function。

μ(n) = { 0    if some prime factors of n are repeated
       { +1   if all prime factors of n are distinct
       {      and total number is even
       { -1   if all prime factors of n are distinct
       {      and total number is odd
n = p₁e₁ × p₂e₂ × ... × pₖeₖ
μ(n) = { 0    if e₁>1 or e₂>1 or ... or eₖ>1
       { +1   if e₁=e₂=...=eₖ=1 and k is even
       { -1   if e₁=e₂=...=eₖ=1 and k is odd

演算法是動態規劃、篩法。時間複雜度O(NloglogN)。

luogu P5495

subset integration【尚無正式名稱】
subset differentiation【尚無正式名稱】

「子集積分」。子集項相加。

b(S) = sum a(T)
       T⊆S

「子集微分」。子集項取捨。

b(S) = sum (-1)|S|-|T|a(T)
       T⊆S

實作時,使用bitset,視作二進位整數,讓外觀宛如數列。

演算法是動態規劃。時間複雜度O(NlogN),N是子集數量。時間複雜度O(2ᴺN),N是元素數量。

poset integration【尚無正式名稱】
poset differentiation【尚無正式名稱】

「偏序集積分」。子孫項相加。

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

「偏序集微分」。子孫項取捨。

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

演算法是動態規劃、拓樸排序。時間複雜度O(N²)。

sequence - convolution

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

索引值配對,數值相乘,通通加總,得到一項。

c(n) = sum a(i)b(j)     已知索引值n,用加法湊出n。
      i+j=n
c(n) = sum a(i)b(n-i)   自身i、減出來的n-i,湊一對。
       i≤n

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

計算一項O(N)。計算每一項O(N²)。運用循環卷積、快速傅立葉轉換降為O(NlogN)。請見本站文件「convolution」。

multiplicative convolution(Dirichlet 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

計算一項O(sqrtN)。計算每一項O(NsqrtN)。目前沒有高速演算法。

dyadic convolution

「二元卷積」。配對運算是聯集、交集、對稱差集。

c(S) = sum a(A)b(B)
      A∪B=S
c(S) = sum a(A)b(B)
      A∩B=S
c(S) = sum a(A)b(B)
      A⊖B=S

實作時,使用bitset。配對運算化作OR、AND、XOR。

希臘語dyadic、拉丁語binary,兩者同義。因為配對運算化作位元運算,所以取名dyadic。我覺得有點牽強就是了。

c(n) = sum a(i)b(j)
      i|j=n
c(n) = sum a(i)b(j)
      i&j=n
c(n) = sum a(i)b(j)
      i^j=n

計算一項O(N)。計算每一項O(N²)。運用子集積分降為O(NlogN)。N是子集數量。

三數列各自積分,卷積化作乘法。

c(S) = sum a(A)b(B)  —→   sum c(S) = ( sum a(S) ) ( sum b(S) )
      A∪B=S              T∪S=S        T∪S=S        T∪S=S
      積分
     —————→
 卷 ¦      | 乘
 積 ↓      ↓ 法
     ←—————
      微分

聯集運算的積分,等同子集積分。交集運算的積分,等同超集積分。對稱差集運算(聯集減交集)的積分,即是兩者相減。

integration     | differentiation
--------------------------------------------
b(S) = sum a(T) | b(S) = sum (-1)|S|-|T|a(T)
      T∪S=S     |       T∪S=S
b(S) = sum a(T) | b(S) = sum (-1)|S|-|T|a(T)
      T∩S=S     |       T∩S=S
b(S) = sum a(T) | b(S) = sum (-1)|S|-|T|a(T)
      T⊖S=S     |       T⊖S=S

程式碼外觀宛如Walsh–Hadamard transform,但是其實沒有太大關係。

luogu P4717

subset convolution

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

c(S) = sum a(A)b(B) = sum a(T)b(S\T) = sum a(S\T)b(T)
      A⊔B=S           T⊆S              T⊆S

計算一項O(N)。計算每一項O(N²)。運用動態規劃降為O(N(logN)²)。N是子集數量。

計算一項O(2ᴺ)。計算每一項O((2ᴺ)²) = O(4ᴺ),更精確一點O(3ᴺ)。運用動態規劃降為O(N²2ᴺ)。N是元素數量。

由於互斥,動態規劃表格增加一個維度,紀錄集合大小。

Fourier Meets Möbius: Fast Subset Convolution
https://arxiv.org/abs/cs/0611101

luogu P6097

poset convolution

「偏序集卷積」。配對運算是最低共同祖先LCA。

偏序集是分割關係:配對運算難以言喻。
偏序集是因數關係:配對運算是最小公倍數。
Invitation to Algorithmic Uses of Inclusion–Exclusion
https://arxiv.org/abs/1105.2942
Efficient Möbius Transformations and Their Applications to D-S Theory
https://www.researchgate.net/publication/337698211

convolution

卷積由兩個集合、三個運算組成。

註:兩個集合、三個運算目前沒有正式學術名稱。

c(n) = sum a(i)×b(j)
      i+j=n

索引集合index  :自然數ℕ   i j
數值集合value  :實數ℝ     a(i) b(j)
配對運算match  :加法+     i+j=n
合併運算merge  :乘法×     a(i)×b(j)
累計運算summate:加法+     sum

卷積多采多姿,尚待挖掘探索。

convolution    | index   | value   | match  | merge | summate
---------------| --------| --------| -------| ------| -------
additive       | integer | number  | +      | ×     | +      
multiplicative | integer | number  | ×      | ×     | +      
---------------| --------| --------| -------| ------| -------
subset         | bitset  | number  | ⊔      | ×     | +      
dyadic         | bitset  | number  | ∩/∪/⊖  | ×     | +      
poset          | bitset  | number  | LCA    | ×     | +      
---------------| --------| --------| -------| ------| -------
infimal        | real    | number  | +      | +     | inf    
Minkowski sum  | vectors | vectors | ×      | +     | ∪      
convolution    | algorithm
---------------| ----------------------------------------------
additive       | Fourier transform / number theoretic transform
multiplicative | fast algorithm is still unknown
---------------| ----------------------------------------------
dyadic         | dynamic programming: Walsh–Hadamard transform
subset         | dynamic programming: bitset
poset          | dynamic programming: topological sort
---------------| ----------------------------------------------
infimal        | ?
Minkowski sum  | Fourier transform

sequence - algebra

additive convolution(Cauchy product)

加性卷積具備交換律、結合律、加法分配律。

a ∗ b = b ∗ a                       交換律
(a ∗ b) ∗ c = a ∗ (b ∗ c)           結合律
(a + b) ∗ c = (a ∗ c) + (b ∗ c)     加法分配律

加性卷積當中,單位元素是脈衝函數δ。

小寫希臘字母δ,唸作/ˈ dɛltə/,可以寫作delta。

impulse function:  δ(n) = [n = 0]   (1 0 0 0 0 ...)
constant function: 𝟏(n) = 1         (1 1 1 1 1 ...)
identity function: ι(n) = n         (0 1 2 3 4 ...)
a ∗ δ = a     單位元素是δ
a ∗ b = δ     a的反元素是b

加性卷積當中,常數函數𝟏的反元素是什麼?【尚待確認】

粗體阿拉伯數字𝟏,唸作blackboard bold one。

加性卷積當中,恆等函數ι的反元素是什麼?【尚待確認】

小寫希臘字母ι,唸作/aɪˈ oʊtə/,可以寫作iota。

multiplicative convolution(Dirichlet product)

乘性卷積具備交換律、結合律、乘法分配律。

a ∗ b = b ∗ a                       交換律
(a ∗ b) ∗ c = a ∗ (b ∗ c)           結合律
(a × b) ∗ c = (a ∗ c) × (b ∗ c)     乘法分配律

乘性卷積當中,單位元素是脈衝函數ε。

小寫希臘字母ε,唸作/ˈ ɛpsɨlɒn/,可以寫作epsilon。

impulse function:  ε(n) = [n = 1]   (1 0 0 0 0 ...)
constant function: 𝟏(n) = 1         (1 1 1 1 1 ...)
identity function: ι(n) = n         (1 2 3 4 5 ...)
a ∗ ε = a     單位元素是ε
a ∗ b = ε     a的反元素是b

乘性卷積當中,常數函數𝟏的反元素是質因數取捨函數μ。

小寫希臘字母μ,唸作/mju:/,可以寫作mu。

乘性卷積當中,恆等函數ι的反元素是什麼?【尚待確認】

小寫希臘字母ι,唸作/aɪˈ oʊtə/,可以寫作iota。

𝟏 ∗ μ = ε     𝟏的反元素是μ

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

數列函數轉換的對應運算

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

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

(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⁴

對應運算的概念,請見本站文件「transformation」。

數列函數轉換的對應運算:卷積

數列的卷積運算,最初源自生成函數的乘法運算。

一、數列加性卷積=冪級數乘法(指數相加)。

二、數列乘性卷積=狄利克雷級數乘法(底數相乘)。

(2 -5  1)        ←—→  2x⁰ - 5x¹ + 1x²
    ∗                        ×
(1 -1  0)        ←—→  1x⁰ - 1x¹ + 0x²
    ‖                        ‖
(2 -7  7  1  0)  ←—→  2x⁰ - 7x¹ + 7x² + 1x³ + 0x⁴
(a₀ a₁ a₂)        ←—→  a₀x⁰ + a₁x¹ + a₂x²
    ∗                          ×
(b₀ b₁ b₂)        ←—→  b₀x⁰ + b₁x¹ + b₂x²
    ‖                          ‖
(c₀ c₁ c₂ c₃ c₄)  ←—→  c₀x⁰ + c₁x¹ + c₂x² + c₃x³ + c₄x⁴
(2 -5  1)        ←—→  2⋅1ˣ - 5⋅2ˣ + 1⋅3ˣ
    ∗                        ×
(1 -1  0)        ←—→  1⋅1ˣ - 1⋅2ˣ + 0⋅3ˣ
    ‖                        ‖
(2 -7  1  5  0   ←—→  2⋅1ˣ - 7⋅2ˣ + 1⋅3ˣ + 5⋅4ˣ + 0⋅5ˣ
 -1  0  0  0)       - 1⋅6ˣ + 0⋅7ˣ + 0⋅8ˣ + 0⋅9ˣ
(a₀ a₁ a₂)         ←—→  a₀1ˣ + a₁2ˣ + a₂3ˣ
    ∗                           ×
(b₀ b₁ b₂)         ←—→  b₀1ˣ + b₁2ˣ + b₂3ˣ
    ‖                           ‖
(c₀ c₁ c₂ ... c₈)  ←—→  c₀1ˣ + c₁2ˣ + c₂3ˣ + ... + c₂9ˣ

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

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

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

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

唯一解定理(unisolvence theorem)

當x皆相異,係值轉換必是一對一轉換!

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

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

線性函數的概念,請見本站文件「linear function」。

內插函數的概念,請見本站文件「interpolation」。

係值轉換的對應運算

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

            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}

係根轉換【尚無正式名稱,也許是polynomial factorization】

係數、根,互相轉換!

            2x⁰ - 3x¹ + 1x² = 0
(2 -3  1)  <———————————————————>  {1 2}

代數基本定理(fundamental theorem of algebra)

冪級數:當首項係數為一,係根轉換是一對一轉換。

多項式餘式定理(polynomial remainder theorem)

冪級數:r是根,(x-r)是因式,兩者等價。

黎曼猜想(Riemann hypothesis)

狄利克雷級數:係根關係目前仍是謎!

係根轉換的對應運算

查無資料。