count

count

「計數」。計算數量。

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

enumeration

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

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

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

summorial

triangular number

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

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

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

factorial

factorial

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

factorial的快速演算法

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

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

luogu P5282 P5702

Stirling's formula

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

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

UVa 1185

falling factorial / rising factorial

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

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

falling factorial的快速演算法

數學公式

Wilson's theorem:階乘推廣成餘數。

Legendre's formula:階乘推廣成p進數。

permutation

permutation number

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

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

UVa 12257

combination

combination number

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

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

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

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

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

polynomial

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

binomial

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

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

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

sequence transformation🚧

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

sequence transformation🚧

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/