Polynomial(Under Construction!)

Monomial axⁿ

「單項式」。變數的次方、通通相乘、乘上倍率。

一個變數:axⁿ。

多個變數:axᵖy𐞥zʳ。

Polynomial ∑aᵢxⁱ

「多項式」。多種單項式相加。

一個變數:a₀x⁰ + a₁x¹ + a₂x² + ... = ∑aᵢxⁱ。

多個變數:a₀₀₀x⁰y⁰z⁰ + a₀₀₁x⁰y⁰z¹ + a₀₁₀x⁰y¹z⁰ + a₁₀₀x¹y⁰z⁰ + a₀₀₂x⁰y⁰z² + a₀₁₁x⁰y¹z¹ + ... = ∑aᵢⱼₖxⁱyʲzᵏ。

數學公式

Newton's Identity:每項k次方的總和、k項連乘積的總和,兩者之間的關係。

Binomial(Under Construction!)

Monomial xⁿ

「單項式」。一種變數的次方。這是第二種定義。

x⁰
x¹
x²
x³

Binomial (x+y)ⁿ

「二項式」。兩種變數相加的次方。

(x + y)⁰
(x + y)¹
(x + y)²
(x + y)³

二項式展開成多項式。「和、冪」化作「冪、積、和」。

(x + y)⁰ = x⁰y⁰
(x + y)¹ = x⁰y¹ + x¹y⁰
(x + y)² = x⁰y² + 2x¹y¹ + x²y⁰
(x + y)³ = x⁰y³ + 3x¹y² + 3x²y¹ + x³y⁰

二項式係數恰是巴斯卡三角形。

(x + y)⁰ = C(0,0)x⁰y⁰
(x + y)¹ = C(1,0)x⁰y¹ + C(1,1)x¹y⁰
(x + y)² = C(2,0)x⁰y² + C(2,1)x¹y¹ + C(2,2)x²y⁰
(x + y)³ = C(3,0)x⁰y³ + C(3,1)x¹y² + C(3,2)x²y¹ + C(3,3)x³y⁰

幾何意義是邊邊角角。

luogu P1313

Binomial Series (x+1)ⁿ

「二項式級數」。y改成1。

(x + 1)⁰ = x⁰
(x + 1)¹ = x⁰ + x¹
(x + 1)² = x⁰ + 2x¹ + x²
(x + 1)³ = x⁰ + 3x¹ + 3x² + x³

數學公式

Binomial Coefficient:C(n,k)。

Pascal's Identity:C(n,k) = C(n-1,k) + C(n-1,k-1)。

Vandermonde's Identity:C(m+n,k) = ki=0 C(m,i) C(n,k-i)。

Binomial Theorem:(x+y)ⁿ展開。

Lucas' Theorem:二項式定理推廣成餘數。

Kummer's Theorem:二項式定理推廣成p進數。

Frobenius Endomorphism:(x+y)ᵖ ≡ xᵖ + yᵖ (mod p)。

UVa 1649 10213 10790 10843

演算法

https://blog.csdn.net/skywalkert/article/details/104681101

https://min-25.hatenablog.com/entry/2019/10/08/214743

luogu P3807 P4720

Enumeration(Under Construction!)

Enumeration

字面意義是「數數」。中文翻譯是「枚舉」。

數學當中,「計數counting」和「列舉listing」一體兩面,同稱「枚舉enumeration」。計算學當中,則是各飾一角。

本文著重「計數counting」的部分。

數學公式

Derangement:n個相異數的錯排。

Catalan Number:n個相同點的二元樹。

Cayley's Formula:n個相異點的樹。

Partition Function:n個相同物的分群。

Bell Number:n個相異物的分群。

Stirling Number of the Second Kind:n個相異物k個群。

Stirling Number of the First Kind:n個相異物k個群的排列。

luogu P5748 P7364 P5900 P5084 P6296 P4389

範例:Derangement

「亂序」或「錯排」。人人不在自己編號位置。

d(n) = (n-1) (d(n-1) + d(n-2))
n不能放在a[n],可以放在a[0]...a[n-1]其中一個位置
放到a[i]之後,分兩種情況:i放在a[n],i不放在a[n]
                          d(n-2)     把a[n]想做是a[i],d(n-1)

Rencontres Number:仿照巴斯卡三角形。

UVa 10497 11481

範例:Partition Function

「分割函數」。每種整數的加法分解。

    inf
1 + sum p(n) xⁿ = 1/(1-x)(1-x²)(1-x³)...   Euler
    n=1
                = (1+x¹+x²+...)(1+x²+x⁴+...)(1+x³+x⁶+...)...
1/(1-x) = 1+x¹+x²+x³...                        geometric series
d/dx 1/(1-x) = 1/(1-x)² = 0+1+2x¹+3x²+4x³+...

Sequence(Under Construction!)

Series Reversion

https://mathworld.wolfram.com/SeriesReversion.html

Inclusion–Exclusion Principle

http://vfleaking.blog.uoj.ac/blog/87

Maximum–Minimums Identity

https://notebook.memset0.cn/16

Binomial Transform / Binomial Inversion

https://www.cnblogs.com/GDOI2018/p/14491894.html

https://notebook.memset0.cn/er-xiang-shi-fan-yan

luogu P4491

Stirling Transform / Stirling Inversion

https://zhuanlan.zhihu.com/p/65424997

https://blog.csdn.net/liutian429073576/article/details/53727939

https://en.wikipedia.org/wiki/Stirling_number
https://en.wikipedia.org/wiki/Stirling_polynomials
https://en.wikipedia.org/wiki/Bernoulli_number
https://en.wikipedia.org/wiki/Bernoulli_polynomials

Generating Function(Under Construction!)

Ordinary Generating Function

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

Exponential Generating Function

https://oi-wiki.org/math/gen-func/egf/
https://mathworld.wolfram.com/EulerTransform.html
https://codeforces.com/blog/entry/91632#comment-802482
https://old.memset0.cn/luogu4841/
https://zhuanlan.zhihu.com/p/53079223
http://zory.ink/posts/68d9.html

Probability Generating Function

https://zhuanlan.zhihu.com/p/138290902

https://riteme.site/blog/2018-3-2/cut-the-stick.html

Linear Differential Equation

https://web.math.sinica.edu.tw/mathmedia/HTMLarticle18.jsp?mID=43208

https://codeforces.com/topic/76978/

luogu P6613

Polynomial Sequence(Under Construction!)

Difference Operator

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

shift operator: E

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

Hasse Derivative

https://blog.csdn.net/EI_Captain/article/details/118317406

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

Binomial Convolution

Bernoulli polynomial / Euler polynomial
binomial convolution / Appell sequence
https://en.wikipedia.org/wiki/Bernoulli_polynomials#Another_explicit_formula
https://math.stackexchange.com/questions/1487803/
https://en.wikipedia.org/wiki/Appell_sequence
https://en.wikipedia.org/wiki/Sheffer_sequence
https://en.wikipedia.org/wiki/Polynomial_sequence

Polar Derivative

Apolar polynomials / polar derivative
https://mathoverflow.net/questions/378463/
{ p(x) = a₀x⁰ + ... + aₙxⁿ
{ q(x) = b₀x⁰ + ... + bₙxⁿ
where        a₀bₙ           a₁bₙ₋₁                aₙb₀
      (-1)⁰ —————— + (-1)¹ —————— + ... + (-1)ⁿ —————— = 0
            C(n,0)         C(n,1)               C(n,n)

Polynomial of Falling Factorial Polynomial

https://www.cnblogs.com/chasedeath/p/13073206.html

luogu P5383 P5393 P5394 P5667