Remark: 0fn=2=a-6ma+r-2()w (2)if z1=2=...=In 1 then n" Propostion9:X=r,A =fordered partitions of X into n parts s.t.ith block has size a)Then proof:Let =i,..Let B=fall vectors of length r over 回crtimes,.ie网，ia,=rd definef:A→B,(h,…,Rn)→(b1,…,br).[bybh=jifi∈Rl check that is a bijection.then l Propostion9:Exercise]X=r,S ={unordered partitions of X,s.t.there arek blocks of size i,ier).Then, 1S=(2刚州kkk Stirling Number of 2nd kind. Def:Let S(r,n)be the number of partitions of [r]into n unordered non-empty sets. S(r,n)= n(1)(2）…(2…k [ExereiselS(,r.2=2（(月 Binomial Theorem n≥0，for all x and y. e+r-( k=0 8Remark: (1) if n = 2, x1 = a, x2 = b, then (a + b) r = Pr i=0  r i  a i b r−i . (2) if x1 = x2 = · · · = xn = 1 then n r = P a1+a2+···+an=r r! a1!a2!···an! . Partition:X = R1 ∪ R2 ∪ · · · ∪ Rn. there are two cases: unordered partition {R1, · · · , Rn},and ordered partition (R1, · · · , Rn). Propostion9:|X| = r, A ={ordered partitions of X into n parts s.t. ith block has size ai}. Then |A| = r! a1!a2!···an! . proof:Let X = x1, · · · , xn. Let B={all vectors of length r over [n] s.t.i occurs ai times. i ∈ [n], Pn i=1 iai = r.} define f : A → B,(R1, · · · , Rn) 7→ (b1, , · · · , br). [by bi = j if i ∈ Rj ] check that f is a bijection.then |A| = |B| = r! a1!a2!···an! . Propostion9:[Exercise] |X| = r, S ={unordered partitions of X, s.t. there are ki blocks of size i, i ∈ [r], Pr i=1 iki = r}.Then, |S| = r! (1!)k1 (2!)k2 · · ·(r!)kr k1!k2! · · · kr! . Stirling Number of 2nd kind. Def:Let S(r, n) be the number of partitions of [r] into n unordered non-empty sets. S(r, n) = X Pr i=1 P ki=n r i=1 iki=r r! (1!)k1 (2!)k2 · · ·(r!)kr k1!k2! · · · kr! . [Exercise]S(r, 2) = 1 2 rP−1 i=1  r i  . Binomial Theorem n ≥ 0, for all x and y. (x + y) n = Xn k=0  n k  x k y n−k . 8