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₂)

點積

對應項相乘,通通加總。

可以直接使用STL的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)。

可以直接使用STL的partial_sum()。

UVa 10324 10994 983

Additive Differentiation(Finite Difference)(Adjacent 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)。

可以直接使用STL的adjacent_difference()。

UVa 10038

Multiplicative Integration
Multiplicative Differentiation

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

(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(Möbius Transform)
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(Zeta Transform)
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 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

計算一項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,但是其實沒有太大關係。

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

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。

偏序集是分割關係:配對運算難以言喻。
偏序集是因數關係:配對運算是最小公倍數。

https://en.wikipedia.org/wiki/Incidence_algebra

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

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

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

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

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

Multiplicative Convolution(Dirichlet Convolution)

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

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     單位元素是ε

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

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

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

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

coprime counting function: φ(n) = # of relative primes
Möbius function:           μ(n) = -1 ^ (# of singular prime factors)
𝟏 ∗ μ = ε     𝟏的反元素是μ

乘性卷積當中,常數函數𝟏的效果是乘性積分。

乘性卷積當中,質因數取捨函數μ的效果是乘性微分。

μ ∗ 𝟏 = ε     μ的乘性積分是ε
φ ∗ 𝟏 = ι     φ的乘性積分是ι
sum μ(d) = { 1 if n = 1
d|n        { 0 otherwise

sum φ(d) = n
d|n

順便介紹因數計數函數、因數總和函數。

divisor count function: σ₀(n) = # of divisors   (sometimes d(n) τ(n))
divisor sum function:   σ₁(n) = sum of divisors (sometimes σ(n))
𝟏 ∗ 𝟏 = σ₀     𝟏的乘性積分是σ₀
ι ∗ 𝟏 = σ₁     ι的乘性積分是σ₁
sum μ(n/d) σ₀(d) = 1   --> 𝟏(n)
d|n

sum μ(n/d) σ₁(d) = n   --> ι(n)
d|n

順便介紹一道經典數學公式φ = μ ∗ ι。可以利用代數來證明。

{ ε = μ ∗ 𝟏                 μ的乘性積分是ε
{ φ ∗ 𝟏 = ι                 φ的乘性積分是ι
ε ∗ φ ∗ 𝟏 = μ ∗ 𝟏 ∗ ι       左側相卷等於右側相卷
(ε ∗ φ) ∗ 𝟏 = (μ ∗ ι) ∗ 𝟏   交換律、結合律
ε ∗ φ = μ ∗ ι               左右兩側同卷𝟏的反元素
φ = μ ∗ ι                   ε是單位元素

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)

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

黎曼猜想(Riemann Hypothesis)

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

係根轉換的對應運算

查無資料。