2017.9.15 Slections with repetition Porposition6:#{integer solutions to +...+n=k.where >0=(n-i /k-1 proof:The question is equivalent to How many ways of distribut- ing sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n-1 cuts from k-1 possibles. -(-) integer solutions tok.where n-1 罗中太-+轻5奇之 A…6w头=+ie时 (1)fis weiidefined..if(c1,…,tn)∈A then(h,…,n)∈B. (2)injection. (3)surjection. →4==(+-1 n-1/ Porposition7:X=[n],A={{a a}X,1≤a1≤2≤ ≤n,anda+1-a:≥k+l,i∈r-1 6
2017.9.15 Slections with repetition Porposition6: # {integer solutions to x1 + · · · + xn = k. where xi > 0}= k − 1 n − 1 . proof: The question is equivalent to How many ways of distributing k sweets to n children.Such that each child has at least one sweet. Lay out the sweets in a single row of length k,cut it into n pieces.then given yhe sweets in the ith piece to child i.So we need n − 1 cuts from k − 1 possibles. ⇒ k − 1 n − 1 . # {integer solutions to x1+· · ·+xn = k. where xi ≥ 0}= n + k − 1 n − 1 . proof:LetA={integer solutions x1 + · · · + xn = k, xi ≥ 0} B ={integer solutions y1 + · · · + yn = n + k, yi > 0} Define f : A → B,(x1, · · · , xn) 7→ (y1, · · · , yn) by yi = xi+1, i ∈ [n]. Show:f is a bijection. (1) f is weiidefined.if (x1, · · · , xn) ∈ A then (y1, · · · , yn) ∈ B. (2) injection. (3) surjection. ⇒ |A| = |B| = n + k − 1 n − 1 Porposition7: X = [n], A = {{a1, · · · , ar} ⊆ X, 1 ≤ a1 ≤ a2 ≤ · · · ≤ ar ≤ n, and ai+1 − ai ≥ k + 1, i ∈ [r − 1]}. 6
roof:Let B={integers set b+...+br+=n -1,where bi 2 0,≥k+1,i=2…,6+1≥0 f:A→B,(a1,…,ar)→(b1,…,br+1 By b1=a1-1≥0. b=a-a-1≥k+1,i=2,…,n 0r+1=n-a 0. Easy to check f is a bijection.And construct a function. g:B→C C={integers set c+...+c+1=n-1-(k+1)(r-1),where ci,....cr+1> 0,} andG=b,C=6-(k+1),i=2,·,r,Gr+1=br+1 Also,check g is a bijection.Hence, 4=1g=1C=（0-1-k+r)+r+)-=(（--)口 8.t.a nti omial Theorem) (1+2+…+xn)厂= +oa-alal…20.zn0 proof: (m1+x2+…+xn)y= the coefficient of n is equal to the number of vectors (veroecrtmsbproposition,weget th theorem
proof: Let B ={integers set b1 + · · · + br+1 = n − 1, where b1 ≥ 0, bi ≥ k + 1, i = 2, · · · , r, br+1 ≥ 0.} f : A → B,(a1, · · · , ar) 7→ (b1, , · · · , br+1) By b1 = a1 − 1 ≥ 0. bi = ai − ai−1 ≥ k + 1, i = 2, · · · , r. br+1 = n − ar ≥ 0. Easy to check f is a bijection.And construct a function. g : B → C C ={integers set c1+· · ·+cr+1 = n−1−(k+1)(r−1), where c1, · · · , cr+1 ≥ 0,} and c1 = b1, ci = bi − (k + 1), i = 2, · · · , r, cr+1 = br+1. Also,check g is a bijection.Hence, |A| = |B| = |C| = n − 1 − (k + 1)(r − 1) + (r + 1) − 1 r = n − k(r − 1) r . Arrangements with Repetition Propostion8:X = {x1, · · · , xn}.B ={all vectors of length r over X s.t.xi occurs ai times.} Then,|B| = r! a1!a2!···an! . proof:just double counting. Corollary:(Polynomial Theorem) (x1 + x2 + · · · + xn) r = X a1+a2+···+an=r r! a1!a2! · · · an! x1 a1 · · · xn an . proof: (x1 + x2 + · · · + xn) r = X 1≤i1,i2,··· ,ir≤n xi1 xi2 · · · xir the coefficient of x1 a1 · · · xn an is equal to the number of vectors (i1, · · · , in) over [n],s.t.i occur ai times.by proposition8,we get this theorem. 7
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 8
Remark: (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
Thm.(Vandermonder's Indentity)Vm,n,r20 (+）=(0()-(O) a(+）-(0) proof: 1) (1+x)m+n=(1+x)m=(1+x)" →(-0)》 compute coefficient offor both side +)-王)）-2() (2) 三(0G)-2(0(m)-王（(m）-(+) [Exercise】 含（因-(） ()）()-(C+） 同()-）-（+0-) ④（图）(）=(a)-m）≥≥m )()-(a）
Thm.(Vandermonder’s Indentity) ∀m, n, r ≥ 0 (1) m + n r = Pr i=0 n i m r − i = P i+j=r n i m j . (2) m + n r + m = P i−j=r n i m j . proof: (1) (1 + x) m+n = (1 + x) m = (1 + x) n ⇒ mX +n r=0 m + n r x r = Xn i=0 n i x iXm j=0 m j x j compute coefficient of x r for both side. m + n r = X i+j=r n i m j = Xr i=0 n i m r − i . (2) X i−j=r n i m j = X i−j=r n i m m − j = X i+(m−j)=m+r n i m m − j = m + n r + m . [Exercise] (1) Pn k=0 n k 2 = 2n n . (2) Pn k=0 m k n p + k = n + m p + m . (3) Pm k=1 m k n − 1 k − 1 = n + m − 1 n . (4) n k k m = n m n − m k − m (n ≥ k ≥ m). (5) Pn k=0 n k k m = n m 2 n−m. 9
Combinatorics 2017 Fall week2 note Teaching by:Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science.2nd Edition.Stasys Jukna,Springer 2017/09/19 Estimating Theorem 1 For Vn≤l,e()≤nl≤en()r Proof:consider "Inrdr, ala-p-m≤厂广mc≤2i-tm →lm(n-1)！≤nlnn-n+1≤innl. raise e to the power of each side, (n-l!≤em-n+1≤nl where enlnn-n+1 =(elmn)"e-me=e. ◇ Stirling formula:n!()".wheref(n)gn)meansm1. ()-()a Corllary斋≤(）sr Theorem2:Forl≤k≤n,()≤()≤(0)k Proof:For lower bound,,use the fact是≤g号，i≤k (r≤星岩…Ψ=(
Combinatorics 2017 Fall week2 note Teaching by: Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017/09/19 Estimating Theorem 1 For ∀n ≤ 1, e( n e ) ≤ n! ≤ en( n e ) n . Proof: consider R n 1 lnxdx, ln(n − 1)! = Xn−1 i=1 lni ≤ Z n 1 lnx ≤ Xn i=1 lni = lnn!. =⇒ ln(n − 1)! ≤ nlnn − n + 1 ≤ lnn!. raise e to the power of each side, (n − 1)! ≤ e nlnn−n+1 ≤ n!. where e nlnn−n+1 = (e lnn) n e −n e = n n en e. Stirling formula: n! ∼ √ 2πn( n e ) n . wheref(n) ∼ g(n)means limn→∞ f(n) g(n) = 1. Fact: max{ n k : k = 0, 1, 2 · · · n} = n n 2 , if n is even; n n 2 = n n 2 , if n is odd. Corollary: 2 n n+1 ≤ n n 2 ≤ 2 n . Stirling approximation: n n 2 ∼ 2 n √ n q 2 π . Theorem 2: For1 ≤ k ≤ n,( n k ) k ≤ ( n k ) ≤ ( en k ) k . Proof: For lower bound, use the fact n k ≤ n−i k−1 , ∀i ≤ k, ( n k ) k ≤ n k · n−1 k−1 · · · · · n−k+1 1 = n k , 1