南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Generating Functions

Generating Functions

Generating Functions

Generating Functions: Enumerative Combinatorics "the most useful but most Volume I difficult to understand method RICHARD P.STANLEY (for counting)

“the most useful but most difficult to understand method (for counting)” Generating Functions:

generate ©umerate all subsets of {O,●，Q} (x0+x21)(x0+x1)(x0+2) z0aOx0 +x0xOx1+z0x1x0+x0x1z1 x1x0x0+x1x0x1+x1x1x0+x1x1x1 (1+x)3=1+3x+3x2+x3 coefficient of:of k-subsets

{ , , } enumerate all subsets of generate (x0 + x1)(x0 + x1)(x0 + x1) = + + + + + + + x1 x0x0x0 x0x0x1 x0 x0 x1 x0 x1 x1 x0 x0 x1 x0 x1 x1 x0 x1 x1 x1 x1 (1 + x) 3 =1+3x + 3x2 + x3 coefficient of xk : # of k-subsets

{○，O,○， ●，●，●，O, ○，○，○，○，○} (1+x+x2+x3) (1+x+x2+x3+x4) (1+x+x2+x3+x4+x5) 三 1+3+6x2+10x3+14x4+17x5+18x6 +17x7+14x8+10x9+6x10+3x11+x12

(1 + x + x2 + x3) (1 + x + x2 + x3 + x4) (1 + x + x2 + x3 + x4 + x5) { } , , , , , , , , , , , = 1+3+6x2 + 10x3 + 14x4 + 17x5 + 18x6 +17x7 + 14x8 + 10x9 + 6x10 + 3x11 + x12

Double Decks choose m cards from 2 decks of n cards (+1+x)(唱+2+x)…(a%+x%+x品) coefficient of m-order terms coefficient of xmm in (1+x+x2)

coefficient Double Decks (x0 1 + x1 1 + x2 1) (x0 2 + x1 2 + x2 2) ···(x0 n + x1 n + x2 n) of m-order terms (1 + x + x2) n coefficient of xm in 2 deck of s n cards choose m cards from

Double Decks choose m cards from 2 decks of n cards 1++=∑(e+2* *会0-）得 p<k

Double Decks 2 deck of s n cards choose m cards from (1 + x + x2) n = ￾ k ￾n k ￾ (x + x2) k = ￾ k ￾n k ￾ xk￾ ￾￾k ￾k ￾ ￾ x￾ = ￾ k ￾ ￾￾k ￾n k ￾￾k ￾ ￾ xk+￾ = ￾ m ￾￾ ￾ ￾ n m ￾ ￾ ￾￾m ￾ ￾ ￾ ￾￾ xm ( )

Multisets multisets on S={1,2,...,n} (1+x1+c+…)(1+x2+c2+…)…(1+xm+x2+…) =Πxma) m:S→Nxi∈S 1+++…”=∑m+m=()》* |‖geometric m∈Nn (1-x）n=∑-m(-n-1）(-n-k+1(-1)xk k! k≥0 Taylor

Multisets multisets on (1 + x1 + x2 1 + ···)(1 + x2 + x2 2 + ···)···(1 + xn + x2 n + ···) S = {x1, x2,...,xn} = ￾ m:S￾N ⇥ xi⇥S x m(xi) i (1 + x + x2 + ···) n = ⇤ k￾0 ￾￾n k ⇥⇥ xk = ￾ m⇥Nn xm1+···+mn (1 ￾ x) ￾n = ￾ k￾0 (￾n)(￾n ￾ 1)···(￾n ￾ k + 1)(￾1)k k! xk = geometric Taylor

Multisets multisets on S={1,22,...,n} (1+1++…)(1+x2+c2+…）…(1+xn+x2+…) =∑Πxma) m:S→Nxi∈S +++…==() m∈Nn k>0 1-”=(+会-) (》(+)

Multisets multisets on (1 + x1 + x2 1 + ···)(1 + x2 + x2 2 + ···)···(1 + xn + x2 n + ···) S = {x1, x2,...,xn} = ￾ m:S￾N ⇥ xi⇥S x m(xi) i (1 + x + x2 + ···) n = ⇤ k￾0 ￾￾n k ⇥⇥ xk = ￾ m⇥Nn xm1+···+mn (1 ￾ x) ￾n = ￾ k￾0 xk ￾n + k ￾ 1 k ￾ = ￾￾n k ￾￾ = ￾n + k ￾ 1 k ￾

Ordinary Generating Function OGF) {any a0,a1,a2,·· generating function: G()=∑anxn m=0 =a0+a1x+a2x2+

Ordinary Generating Function (OGF) G(x) = ￾ ￾ n=0 anxn = a0 + a1x + a2x2 + ··· {a a0, a1, a2,... n} generating function:

Compositions by 1 and 2 of compositions of n #of(x1,x2,.,ck） with summands from for some k≤m {1,2} c1+··十ck=n x∈{1,2} Fn Fn-1+Fn-2 F0=0F1=1 Case.I Ck=1 x1+···+2ck-1=m-1 Case.2 xk=2x1+·+xk-1=n-2

# of compositions of n with summands from {1,2} xi ￾ {1, 2} Fn Case.1 Case.2 xk = 1 xk = 2 x1 + ··· + xk￾1 = n ￾ 1 x1 + ··· + xk￾1 = n ￾ 2 = Fn￾1 + Fn￾2 F0 = 0 F1 = 1 Compositions by 1 and 2 for some k ￾ n # of (x1, x2,...,xk) x1 + ··· + xk = n