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

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];
}

點積

對應項相乘，通通加總。

可以直接使用 C++ 標準函式庫的 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];
}
}

sequence — calculus

additive integration 【尚無正式名稱】
（ cumulative 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() 。

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 ）

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

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

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

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

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

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 。

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

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 ）

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

係根轉換的對應運算

查無資料。