Count

「計數」。計算數量。

count作為名詞，是指數量。count作為動詞，是指計算數量。counting從動詞變名詞，是指計算數量這件事情。

Enumeration

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

數學當中，「列舉listing」和「計數counting」一體兩面，同稱「枚舉enumeration」。

計算學當中，則是各飾一角，兩者演算法完全不同。又由於list是既有的資料結構名稱，導致list經常改稱enumerate，導致listing經常改稱enumeration。例如C++程式語言的enum，本義是列舉，正是改稱的結果。

Triangular Number

「三角數」。∑k=1n k = 1 + 2 + ... + n。

數學家稱作三角數。英文俗稱summorial。中文俗稱階加。

int sum(int n) { int a = 1; for (int i=1; i<=n; ++i) a += i; return a; }

Faulhaber's Formula

階加已有許多經典公式，不必逐項相加。例如高斯梯形公式：1+2+...+n = n(n-1)/2，例如正方形的L形分解：1+3+5+7+...+(2n-1) = n²。

1¹ + 2¹ + ... + n¹ = n(n+1)/2
1² + 2² + ... + n² = n(n+1)(2n+1)/6
1³ + 2³ + ... + n³ = (1+2+...+n)² = (n(n+1)/2)²

int sum(int n) { // 上底加下底括號乘以高除以二 return (1 + n) * n / 2; }

Factorial

「階乘」。n! = 1 × 2 × ... × n。

int fac(int n) { int x = 1; for (; n > 0; n--) x *= n; return x; }

Factorial的快速演算法

當n很大，想要盡量避免大數運算，可以利用中國餘數定理：選定一些互質模數（例如質數），分頭計算答案。

針對一種模數，當模數是質數p，可以利用sqrt decomposition、多項式多點求值，快速計算答案。

luogu P5282 P5702

Stirling's Formula

階乘已有快速近似公式，不必逐項相乘。

n! ≈ sqrt(2πn) (n/e)ⁿ

double fac(double n) { double e = exp(1); double c = sqrt(atan(1) * 8); // sqrt(2π) return c * sqrt(n) * pow(n/e, n); }

UVa 1185

Falling Factorial / Rising Factorial

「下降階乘」。n^k̲ = n × (n-1) × ...。總共k個數。

「上升階乘」。n^k̅ = n × (n+1) × ...。總共k個數。

int fac_up(int n, int k) { int x = 1; for (; k > 0; k--, n++) x *= n; return x; } int fac_down(int n, int k) { int x = 1; for (; k > 0; k--, n--) x *= n; return x; }

Falling Factorial的快速演算法

數學公式

Wilson's Theorem：階乘推廣成餘數。

Legendre's Formula：階乘推廣成p進數。

Permutation Number

數學符號是P(n,k)。n個取出k個，相異排列數量。

數學公式是P(n,k) = n^k̲ = n! / (n-k)!。

int count_permutations(int n, int k) { int c = 1; while (k--) c *= n--; return c; } // Stirling's formula long double log_factorial(long double n) { const long double π = 2.0 * acos(0); return log(2.0 * π * n) / 2.0 + n * (log(n) - 1.0); } int count_permutations(int n, int k) { return round(exp(log_factorial(n) - log_factorial(n-k))); }

UVa 12257

Combination Number

數學符號是C(n,k)。n個取出k個，相異組合數量。

數學公式是C(n,k) = n^k̲ / 1^k̅ = n! / (n-k)! / k!。

int count_combinations(int n, int k) { if (k * 2 > n) k = n - k; int c = 1; for (int i=1; i<=k; i++, n--) c *= n / i; return c; }

Combination Number的快速演算法

當n和k很大，想要盡量避免大數運算，可以利用中國餘數定理：選定一些互質模數（例如質數），分頭計算答案。

針對一種模數，當模數是質數p，可以利用Lucas' Theorem：n和k表示成p進位，取其位數，化作規模更小的問題。

luogu P3807 P4720

數學公式

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

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

Lucas' Theorem：C(n,k)推廣成餘數。

Kummer's Theorem：C(n,k)推廣成p進數。

Partition

繁中「分割」、簡中「分拆」。

一堆東西，分成許多份。

例如有五筆資料　　　　●★■▲◆

這是其中一種分割　　　●|★|■|▲|◆
這是其中一種分割　　　●|★|■|▲◆
這和方才是同一種分割　●|★|■|◆▲
這和方才是同一種分割　★|●|◆▲|■
這是其中一種分割　　　●★■▲◆

份是集合。份之內沒有先後順序。

分割是多重集合（其元素是份）。份之間沒有先後順序。

{1,2,3,4,5}  a partition with 5 parts
{1,2,3,45}   a partition with 4 parts
{12345}      a partition with 1 part

{1,2,3,45} = {1,2,3,54} = {2,1,54,3}

分割細分兩種類型：相異物分割（集合分割）、相同物分割（整數分割）。要嘛全部相異，要嘛全部相同，沒有討論混搭。

partitions of 5 distinct objects (partitions of a set)
{1,2,3,4,5}
{1,2,3,45}
{1,2,4,35}
{1,2,5,34}
{1,3,4,25}
{1,3,5,24}
     :

partitions of 5 identical objects (partitions of an integer)
{o,o,o,o,o}
{o,o,o,oo}
{o,o,ooo}
{o,oooo}
{o,oo,oo}
{oo,ooo}

排列組合僅討論相異物，分割討論相異物或相同物。

k-Partition

分成k份。

divide 5 distinct objects into 3 groups
{1,2,345}
{1,3,245}
{1,4,235}
{1,5,234}
{2,3,145}
   :

divide 5 identical objects into 3 groups
{o,o,ooo}
{o,oo,oo}

數學名詞「partition」，英文口語「divide」。

數學名詞「part」，英文口語「group」。

Stirling Number of the Second Kind

數學符號是S(n,k)。n個相異物分成k群，相異分割數量。

數學公式是S(n,k) = k S(n-1,k) + S(n-1,k-1)。

這是遞迴公式。一般公式長得很恐怖。

Partition Number

數學符號是p(n,k)。n個相同物分成k群，相異分割數量。

數學公式是p(n,k) = p(n-k,k) + p(n-1,k-1)。

這是遞迴公式。一般公式長得很恐怖。

數學公式

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

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

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

Partition Number：n個相同物的分群。

Partition Number：n個相同物k個群。

Stars and Bars：n個相同物k個群的排列。

luogu P5748

Twelvefold Way

球放入箱，分成12招。請見這篇文章：

球相異／相同。箱相異／相同。球必須用盡。箱不必有球／最多一球／至少一球（必須有球）。

n balls   | k boxes   ‖ ≥0 ball     | ≤1 ball     | ≥1 balls
          |           ‖ in each box | in each box | in each box
----------|-----------‖-------------|-------------|------------
domain    | codomain  ‖ function    | injection   | surjection
----------|-----------‖-------------|-------------|------------
distinct  | distinct  ‖ kⁿ          | P(k,n)      | S(n,k) k!
          |           ‖             |             |
identical | distinct  ‖ C((k,n))    | C(k,n)      | C((k,n-k))
          |           ‖             |             |
distinct  | identical ‖  sum S(n,i) | I[n≤k]      | S(n,k)
          |           ‖ i=1⋯k       |             |
identical | identical ‖  sum p(n,i) | I[n≤k]      | p(n,k)
          |           ‖ i=1⋯k       |             |

P(n,k) = P(n-1,k) + k P(n-1,k-1)   permuation number
C(n,k) = C(n-1,k) + C(n-1,k-1)     combination number
S(n,k) = k S(n-1,k) + S(n-1,k-1)   Stirling number of the 2nd kind
p(n,k) = p(n-k,k) + p(n-1,k-1)     partition number
C((n,k)) = C(n+k-1,k)              combination with repetition
I[n≤k] = (n ≤ k) ? 1 : 0           indicator function

luogu P5824

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項連乘積的總和（係數），兩者之間的關係。

Viète's Formulas：係數之相鄰兩項比值、根之k項連乘積的總和，兩者之間的關係。

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

Binomial Theorem：(x+y)ⁿ展開，各項係數是C(n,k)。

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

Constrained Combination

附加條件的組合。

Combination with Limited Repetitions

蓮霧2顆、椪柑3顆、芭樂5顆。欲在盤中擺放6顆水果，有幾種組合方式？

蓮霧擺1顆、椪柑擺2顆、芭樂擺3顆  x¹y²z³
蓮霧擺1顆、椪柑擺0顆、芭樂擺5顆  x¹y⁰z⁵
蓮霧擺0/1/2顆                    (x⁰+x¹+x²)
椪柑擺0/1/2/3顆                  (y⁰+y¹+y²+y³)
芭樂擺0/1/2/3/4/5顆              (z⁰+z¹+z²+z³+z⁴+z⁵)
蓮霧擺0/1/2顆、椪柑擺0/1/2/3顆   (x⁰+x¹+x²)(y⁰+y¹+y²+y³)

化作多項式。次方是數量，係數是方式。加法是或，乘法是且。

多項式乘法(x⁰+x¹+x²)(x⁰+x¹+x²+x³)(x⁰+x¹+x²+x³+x⁴+x⁵)，找到x⁶的係數，就是正確答案。

Combination Number

n個取出k個，相異組合數量。

第1個東西不取/取 (x₁⁰+x₁¹)
第2個東西不取/取 (x₂⁰+x₂¹)
     :
第n個東西不取/取 (xₙ⁰+xₙ¹)

多項式乘法(x⁰+x¹)ⁿ = (1+x)ⁿ，找到xᵏ的係數，就是正確答案。

Combination Number的生成函數

固定n、枚舉k，答案形成一串數字。答案顯然是上述多項式的各項係數。

數學家於是創造一種轉換：取出係數。或者反過來：拼出多項式。這個轉換目前叫做生成函數。

生成函數是一種轉換，將離散數列變成連續函數。最經典的生成函數是冪級數：數列第n項乘上xⁿ，通通相加，變成多項式函數。

(2 -5  1  0  4)  ←—→  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
   sequence              generating function

a(0) a(1) a(2) ...  ←—→  a(0)x⁰ + a(1)x¹ + a(2)x² + ...
   sequence a(n)           generating function f(x)

組合數數列的生成函數。

C(n,0) C(n,1) C(n,2) ...  ←—→  C(n,0)x⁰ + C(n,1)x¹ + C(n,2)x² + ...
      sequence a(n)                generating function f(x)

組合數數列的生成函數就是(1+x)ⁿ。

f(x) = C(n,0)x⁰ + C(n,1)x¹ + C(n,2)x² + ... = sum C(n,k) xᵏ
                                             k=0⋯n
f(x) = (x⁰+x¹)ⁿ = (1+x)ⁿ

這就是二項式定理Binomial Theorem。

順帶一提，我們也可以枚舉n、固定k，答案形成另一串數字，對應另一個多項式的各項係數。乏人使用，此處省略。

Partition Number

n個相同物的分群。

尺寸為1的群有0/1/2/3/...個 (x₁⁰+x₁¹+x₁²+...)
尺寸為2的群有0/1/2/3/...個 (x₂⁰+x₂²+x₂⁴+...)
尺寸為3的群有0/1/2/3/...個 (x₃⁰+x₃³+x₃⁶+...)
     :

多項式乘法(x⁰+x¹+x²+...)(x⁰+x²+x⁴+...)(x⁰+x³+x⁶+...)...，找到xⁿ的係數，就是正確答案。

Partition Number的生成函數

無窮多項式(x⁰+x¹+x²+...)，視作幾何級數1/(1-x)。

1/(1-x)  = x⁰+x¹+x²+...    geometric series
1/(1-x²) = x⁰+x²+x⁴+...
1/(1-x³) = x⁰+x³+x⁶+...

d/dx 1/(1-x) = 1/(1-x)² = 1x⁰+2x¹+3x²+4x³+...

分割數的生成函數就是1/(1-xⁱ)連乘積。

f(x) = (x⁰+x¹+x²+...)(x⁰+x²+x⁴+...)(x⁰+x³+x⁶+...)...

f(x) = 1/(1-x)(1-x²)(1-x³)... = mul 1/(1-xⁱ)
                               i=1⋯∞
f(x) = p(0)x⁰ + p(1)x¹ + p(2)x² + ... = sum p(n) xⁿ
                                       n=0⋯∞

f≤k(x) = f≤k-1(x) (x⁰+xᵏ+x²ᵏ+...)

f≤k(x) = mul 1/(1-xⁱ)
       i=1⋯k
f≤k(x) = sum p≤k(n,k) xⁿ
       n=0⋯∞

Ordinary Generating Function

「普通生成函數」。數列第n項乘上xⁿ，通通相加。

適合用於組合數。可以得到漂亮的多項式(1+x)ⁿ。

C(n,0)x⁰ + C(n,1)x¹ + C(n,2)x² + ... = (1+x)ⁿ

常見的數列。

(1 1 1 ...)  ←—→  1/(1-x) = x⁰ + x¹ + x² + ...   geometric series
(a⁰ a¹ a² ...)  ←—→  1/(1-ax)

普通生成函數用來計算附加條件的組合。

加法是或，乘法是且，多項式運算是在拼湊條件。

Constrained Permutation

附加條件的排列。

Permutation with Limited Repetitions/Positions

例如「庭院深深深幾許」、「男女相間坐成一圈」。

例如上升k次、逆序對k個、循環軌道k個。

因為我沒有興趣，所以我沒有研究。各位可以自行閱讀專著。

專著《Combinatorics of Permutations》。

數學公式

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

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

Motzkin Number：n個相異點的不相交弦。

UVa 1649 10213 10790 10843

luogu P4841 P5900 P7364

Derangement

「錯排」。n個相異物排列，個個不在自己編號位置。

　　　　　　　　　　　　　　　　12345
例如有五筆資料　　　　　　　　　●★■▲◆

這是其中一種錯排　　　　　　　　54321
這是其中一種錯排　　　　　　　　23451
不是錯排，有一個在自己編號位置　15432
不是錯排，有五個在自己編號位置　12345

Derangement Number（Subfactorial）

遞迴公式是D(n) = (n-1) (D(n-1) + D(n-2))。

n不能放在a[n]。
n可以放在a[0]...a[n-1]其中一個位置。
n放到a[i]之後，分兩種情況：
一、i放在a[n]：D(n-2)。
二、i不放在a[n]：把a[n]想成是a[i]，D(n-1)。

一般公式是D(n) = n!/0! - n!/1! + n!/2! - ... + (-1)ⁿ n!/n!。

取捨原理。
　恰好N個錯位
＝至多N個錯位－至多N-1個錯位＋至多N-2個錯位－至多N-3個錯位＋……
＝至少0個原位－至少1個原位＋至少2個原位－至少3個原位＋……

D(n) = sum (-1)ᵏ C(n,k) (n-k)!
      k=0⋯n
     = sum (-1)ᵏ (n! / k!)
      k=0⋯n

UVa 10497 11481

Derangement Number的極限值

排列數累積和，n趨向無限大，恰好等於n! e。

錯排數，n趨向無限大，恰好等於n!/e。

 sum 1/n!       = 1/0! + 1/1! + 1/2! + ... = e     Euler number
n=0⋯∞

 sum (-1)ⁿ/n!   = 1/0! - 1/1! + 1/2! - ... = 1/e
n=0⋯∞

lim  sum P(n,k) = n!/0! + n!/1! + n!/2! + ... = n! e
n→∞ k=0⋯n

lim D(n)        = n!/0! - n!/1! + n!/2! - ... = n!/e
n→∞

這個結果非常美麗！但是我不知道如何直觀地解釋，我也不知道如何應用。Euler Number顯然還有某些不為人知的意義與用途。

Rencontres Number

n個相異物排列，k個位在自己編號位置。

Exponential Generating Function

「指數生成函數」。數列第n項乘上xⁿ/n!，通通相加。

適合用於排列數。可以得到漂亮的多項式(1+x)ⁿ。

P(n,0)      P(n,1)      P(n,2)
—————— x⁰ + —————— x¹ + —————— x² + ... = (1+x)ⁿ
  0!          1!          2!

       x⁰             x¹          x²
P(n,0) —— x⁰ + P(n,1) —— + P(n,2) —— + ... = (1+x)ⁿ
       0!             1!          2!

常見的數列。

                       x⁰   x¹   x² 
(1 1 1 ...)  ←—→  eˣ = —— + —— + —— + ...   natural exponentiation
                       0!   1!   2!

(a⁰ a¹ a² ...)  ←—→  eᵃˣ

專著《A Walk Through Combinatorics: An Introduction to Enumeration and Graph》。

luogu P4705 P4091

Inclusion–Exclusion Principle

Maximum–Minimums Identity

https://www.cnblogs.com/GXZlegend/p/11563330.html

luogu P4707

Binomial Transform / Binomial Inversion

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

乍看是卷積，其實不然。

g(n) = sum (-1)ᵏ C(n,k) f(k)
      k=0⋯n

f(n) = sum (-1)ᵏ C(n,k) g(k)
      k=0⋯n

g(n) = sum C(n,k) f(k)
      k=0⋯n

f(n) = sum (-1)ⁿ⁻ᵏ C(n,k) g(k)
      k=0⋯n

1/(1+x) = +1 -1 +1 -1 +1 ...
1/(1-x) = +1 +1 +1 +1 +1 ...

生成函數。不適合設計演算法。

https://math.stackexchange.com/questions/2382296/
https://www.mathstat.dal.ca/FQ/Scanned/32-5/prodinger.pdf

G(x) = 1/(1-x) F(x/(1-x))

1/(1-x)     integral
xⁿ F(1/x)   reverse

luogu P4491

Stirling Number of the Second Kind

二項式反演，得到公式解，也得到快速演算法。

固定n、枚舉m，形成卷積（多項式乘法）。

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

mⁿ = sum P(m,k) S(n,k)
    k=0⋯n

S(n,m) = sum (-1)ᵐ⁻ᵏ C(m,k) (m-k)ⁿ
        k=0⋯m

luogu P5395

Derangement

二項式反演，得到公式解，也得到快速演算法。

形成卷積（多項式乘法）。

https://math.stackexchange.com/questions/83380/

n! = sum C(n,k) D(n-k)
    k=0⋯n

D(n) = sum (-1)ᵏ C(n,k) (n-k)! = sum (-1)ᵏ (n! / k!)
      k=0⋯n                     k=0⋯n

原式恰是卷積（多項式乘法）。不做二項式反演，改做反卷積。反卷積的遞推公式，但是好像沒有實際用處。

D(n) = n! - sum (-1)ᵏ C(n,k) D(n-k)
           k=1⋯n

Stirling Transform / Stirling Inversion

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

f(n) = sum S(n,k) g(k)
      k=0⋯n

g(n) = sum (-1)ⁿ⁻ᵏ [n,k] f(k)
      k=0⋯n

Power Sum

我不知道如何整理成二項式轉換的形式。

https://en.wikipedia.org/wiki/Faulhaber's_formula
principals amd techniques in combinatorics p114 ex85
power sum s(n,k) = 1ᵏ + 2ᵏ + ... + nᵏ

n^(m+1) = sum (-1)^(m+k) C(m+1,k) s(n,k)
         k=0⋯m

(n+1)^m = 1 + sum C(m,k) s(n,k)
             k=0⋯m-1

s(n,m) = n^m - sum (-1)ᵏ C(m,k) s(n,m-k)   ??????
              k=0⋯m

Newton's Indentity

視作生成函數。

rev prod (x-rᵢ) = prod (-rᵢx+1)

(ln f)' = f' / f = sum 1/(x-rᵢ)
(ln rev f)' is generating function of sr(k) when k <= N

Logarithmic Derivative
d/dx ln(f) = f′/f
https://en.wikipedia.org/wiki/Logarithmic_derivative

power sum of roots
sr(k) = r₁ᵏ + r₂ᵏ + ... + rₙᵏ

notice e(k) = 0 when k > N
       f' / f cannot be divided by 0.

root of reverse polynomial
= reciprocol of root of polynomial
https://math.stackexchange.com/questions/692191/

logarithmic derivaitve of reverse polynomial
= generating function of power sum of all polynomial roots

A PROOF OF NEWTON'S POWER SUM FORMULAS
https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1049&context=mathfacpub

all proofs
https://web.stanford.edu/~marykw/classes/CS250_W19/Netwons_Identities.pdf

luogu P5084 P6296

Möbius Transform / Möbius Inversion

乘性積分與微分。因數項的累和與取捨。

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

luogu P4980

Euler Transform / Euler Inversion

宛如算術基本定理。自然數改成x進位數（多項式），質數改成n個一綑的分割數1/(1-xⁿ)（幾何級數）。

多項式係數b（整數位數）變成1/(1-xⁿ)指數a（質數指數）：b->c牛頓恆等式求得根倒數的次方和（連分數），c->a乘性微分。

https://mathworld.wolfram.com/EulerTransform.html
https://mathworld.wolfram.com/RiddellsFormula.html
https://codeforces.com/blog/entry/91632#comment-802482

The number of different symmetric monomials
of degree n in k variables with all the coefficients 1
is equal to the number p(n,k) of partitions
of n in up to k parts.
https://math.stackexchange.com/questions/26677/