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:SN ⇥ xi⇥S x m(xi) i (1 + x + x2 + ···) n = ⇤ k0 n k ⇥⇥ xk = m⇥Nn xm1+···+mn (1 x) n = k0 (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:SN ⇥ xi⇥S x m(xi) i (1 + x + x2 + ···) n = ⇤ k0 n k ⇥⇥ xk = m⇥Nn xm1+···+mn (1 x) n = k0 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 + ··· + xk1 = n 1 x1 + ··· + xk1 = n 2 = Fn1 + Fn2 F0 = 0 F1 = 1 Compositions by 1 and 2 for some k n # of (x1, x2,...,xk) x1 + ··· + xk = n