Sequence

「數列」。一串數字。

(4 -1 6 0 9)

一維陣列儲存一個數列：

int a[5] = {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運算

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

int a[3] = {1, 2, 3}; int b[3] = {4, 5, 6}; int c[3]; void add() { for (int i=0; i<3; ++i) c[i] = a[i] + b[i]; }

點積

對應項相乘，通通加總。

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

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

int a[3] = {1, 2, 3}; int b[3] = {4, 5, 6}; int dot() { int sum = 0; for (int i=0; i<3; ++i) sum += a[i] * b[i]; return sum; }

卷積

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

(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₀)

int a[5] = {1, 2, 3, 4, 5}; int b[3] = {4, 5, 6}; int c[5+3-1]; void convolution() { for (int i=0; i<5+3-1; ++i) { c[i] = 0; for (int j=0; j<3; ++j) if (i-j >= 0 && i-j < 5) c[i] += a[i-j] * b[j]; } }

循環卷積

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

(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₀)

int a[5] = {1, 2, 3, 4, 5}; int b[5] = {5, 6, 7, 8, 9}; int c[5]; void circular_convolution() { for (int i=0; i<5; ++i) { c[i] = 0; for (int j=0; j<5; ++j) c[i] += a[(i-j+5)%5] * b[j]; } }

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()。

int a[5] = {4, -1, 6, 0, 9}; int sum[5]; // 累和 void cumulative_sum() { sum[0] = a[0]; for (int i=1; i<5; i++) sum[i] = sum[i-1] + a[i]; } // [i,j]區間和。 // 預先以O(N)計算累和，便能以O(1)計算區間和。 int interval_sum(int i, int j) { if (i > j) swap(i, j); if (i == 0) return sum[j]; return sum[j] - sum[i - 1]; } // 陣列開頭加一空格，就不必擔心超出陣列邊界。程式碼更簡潔。 int a[5+1] = {0, 4, -1, 6, 0, 9}; int sum[5+1] = {0}; // 累和 void cumulative_sum() { for (int i=1; i<=5; i++) sum[i] = sum[i-1] + a[i]; } int interval_sum(int i, int j) { if (i > j) swap(i, j); return sum[j] - sum[i - 1]; }

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

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

int a[5] = {4, -1, 6, 0, 9}; int diff[5]; // 鄰差 void adjacent_difference() { diff[0] = a[0]; for (int i=1; i<5; i++) diff[i] = a[i] - a[i-1]; }

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

vector<int> prime; // O(π(N)N) = O(N²/logN) void multiplicative_integration(int a[], int N) { for (int p: prime) for (int i=p; i<=n; i++) if (i % p == 0) a[i] += a[i / p]; } void multiplicative_differentiation(int a[], int N) { for (int p: prime) for (int i=p; i<=n; i++) if (i % p == 0) a[i] -= a[i / p]; } vector<int> prime; // O(N/p1 + N/p2 + ...) = O(NloglogN) void multiplicative_integration(int a[], int N) { for (int p: prime) for (int i=1; i<=n; i++) { if (i * p > n) break; a[i * p] += a[i]; } } void multiplicative_differentiation(int a[], int N) { for (int p: prime) for (int i=1; i<=n; i++) { if (i * p > n) break; a[i * p] -= a[i]; } }

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是元素數量。

// with if-statement void subset_integration(int a[], int N) { for (int i=0; i<N; i++) // N是元素數量 for (int s=0; s<(1<<N); s++) if (s & (1<<i)) a[s] += a[s ^ (1<<i)]; } void subset_differentiation(int a[], int N) { for (int i=0; i<N; i++) for (int s=0; s<(1<<N); s++) if (s & (1<<i)) a[s] -= a[s ^ (1<<i)]; } // without if-statement void subset_integration(int a[], int N) { for (int k=1; k<=(N>>1); k<<=1) // N是子集數量 for (int i=0; i<N; i+=(k<<1)) for (int j=0; j<k; j++) // a[i+j+k] += a[i+j]; a[i|j|k] += a[i|j]; } void subset_differentiation(int a[], int N) { for (int k=1; k<=(N>>1); k<<=1) for (int i=0; i<N; i+=(k<<1)) for (int j=0; j<k; j++) a[i|j|k] -= a[i|j]; }

Poset Integration【尚無正式名稱】
Poset Differentiation【尚無正式名稱】

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

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

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

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

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

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，但是其實沒有太大關係。

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

void OR(float a[], int N, bool type) { float w = (type ? 1 : -1); for (int k=1; k<=(N>>1); k<<=1) for (int i=0; i<N; i+=(k<<1)) for (int j=0; j<k; j++) a[i|j|k] += a[i|j] * w; } void AND(float a[], int N, bool type) { float w = (type ? 1 : -1); for (int k=1; k<=(N>>1); k<<=1) for (int i=0; i<N; i+=(k<<1)) for (int j=0; j<k; j++) a[i|j] += a[i|j|k] * w; } void XOR(float a[], int N, bool type) { float w = (type ? 1 : .5f); for (int k=1; k<=(N>>1); k<<=1) for (int i=0; i<N; i+=(k<<1)) for (int j=0; j<k; j++) { float t = a[i|j]; a[i|j] = (t + a[i|j|k]) * w; a[i|j|k] = (t - a[i|j|k]) * w; } } void dyadic_convolution(float a[], float b[], float c[], int N) { OR(a, N, true); // integration OR(b, N, true); for (int i=0; i<N; i++) c[i] = a[i] * b[i]; OR(c, N, false); // differentiation } void OR(float a[], int l, int r, int w) { if (l == r) return; int m = (l + r) / 2; OR(a, l, m, w); OR(a, m+1, r, w); for (int i=0; i<m; i++) a[l|i] += a[(m+1)|i] * w; }

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

void subset_convolution(float a[], float b[], float c[], int N) { float f[N+1][1<<N]; // N是元素數量 float g[N+1][1<<N]; // 1<<N是子集數量 float h[N+1][1<<N]; for (int i=0; i<(1<<N); i++) f[popcount(i)][i] = a[i]; for (int i=0; i<(1<<N); i++) g[popcount(i)][i] = b[i]; for (int i=0; i<=N; i++) { OR(f[i], 1<<N, true); // integration OR(g[i], 1<<N, true); // integration // 迴圈內外對調，得以減少cache miss。 for (int s=0; s<(1<<N); s++) for (int j=0; j<=i; j++) h[i][s] += f[j][s] * g[i-j][s]; OR(h[i], 1<<N, false); // differentiation } for (int i=0; i<(1<<N); i++) c[i] = h[popcount(i)][i]; }

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
---------------------| ----------------------------------------------
dyadic convolution   | dynamic programming: Walsh–Hadamard Transform
subset convolution   | dynamic programming: bitset
poset convolution    | dynamic programming: topological sort
---------------------| ----------------------------------------------
infimal convolution  | ?
Minkowski sum        | Fourier transform

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

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

希臘字母μ，唸做/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 Counting Function / Divisor Sum Function

「因數計數函數」。n的因數數量。常數函數𝟏的乘性積分。

「因數總和函數」。n的因數總和。恆等函數ι的乘性積分。

divisor counting function: σ₀(n) = # of divisors   (or d(n) τ(n))
divisor sum function:      σ₁(n) = sum of divisors (or σ(n))

𝟏 ∗ 𝟏 = σ₀     𝟏的乘性積分是σ₀
ι ∗ 𝟏 = σ₁     ι的乘性積分是σ₁

sum μ(n/d) σ₀(d) = 1   --> 𝟏(n)
d|n

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

Möbius Transformation / Möbius Inversion

「莫比烏斯變換」與「莫比烏斯反演」。乘性積分與乘性微分。可以利用代數來表示。

Möbius transformation: g = f ∗ 𝟏        f的乘性積分是g
Möbius inversion:      f = g ∗ μ        g的乘性微分是f

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

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

註：該詞彙同時用於複變函數領域和數論領域，但是意義不同。數學家在複變函數領域採用Möbius Transformation，在數論領域採用Möbius Inversion，以便區隔。

transform作為動詞，是指計算過程。transform作為名詞，是指計算結果。transformation從動詞變名詞，是指計算過程。類似詞彙還有inverse與inversion、sort與sorting。

luogu P4705 P4091 P4980

數列函數轉換【尚無正式名稱，也許是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）

狄利克雷級數：係根關係目前仍是謎！

係根轉換的對應運算

查無資料。