Combinatorics 2017 Fall weekl note Teaching by:Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017.9.12 Notation: &6onc艾aten的 (2)for integer n>0 [n]:={1,2.....n} (3)A vector(or string)of length n over X （x1.“,rn.x:∈X,1∈n (4)i.e.that is. 3exist. →imply. s.t.such that ！unique
Combinatorics 2017 Fall week1 note Teaching by: Professor Xiande Zhang Reference: Extremal Combinatorics with applications in Computer Science. 2nd Edition.Stasys Jukna,Springer. 2017.9.12 Notation: (1) A set X (a collection of distinct elements) |X| :=# elements of X (2) for integer n > 0 [n] := {1, 2, · · · , n} (3) A vector(or string) of length n over X (x1, ·, xn).xi ∈ X, i ∈ [n] (4) i.e. that is. ∃ exist. ⇒ imply. s.t. such that. ! unique. 1
Counting: Function.For sets a.B.a function aB is a relation between A and B.(a,f(a))s.t.for each aA,3 B satisfying b=f(a) Injection(one to one function):if a a',then f(a)f(a). Surjection(onto)∀b∈B,3a∈A,s.tf(a=b. Bijection(one to one correspondence)Injection&Surjection. Porpostion1.For sets A,B (1)if3 injection f:A→B then A≤|BL. (2)if3 surjection f:A→B then A≥lBl (3)if 3 bijection f A-B then Al Bl. proof: (1)Assume B<Al since 3 functionf A B by definition Va EA,3E B s.t.f(a)=b.since B<Al then 3a t at s.t. f(a)=f(ar)(by pigeonhole principal)This is contradiction with the fact that f is a injection. (2)Assume B>Al since 3 functionf AB by definition a∈A,3b∈Bs.t.f(a)=b.3b∈Bs.t.there does not exist a E A satisfying f(a)=b This is contradiction with the fact that f is a surjection. (3)(1)&(2)→(3). 0 2
Counting: Function.For sets A,B. a function A → B is a relation between A and B. (a, f(a)) s.t. for each a ∈ A, ∃b ∈ B satisfying b = f(a) Injection(one to one function): if a 6= a 0 ,then f(a) 6= f(a 0 ). Surjection(onto) ∀b ∈ B, ∃a ∈ A, s.t.f(a) = b. Bijection(one to one correspondence) Injection & Surjection. Porpostion1. For sets A,B (1) if ∃ injection f : A → B then |A| ≤ |B|. (2) if ∃ surjection f : A → B then |A| ≥ |B|. (3) if ∃ bijection f : A → B then |A| = |B|. proof: (1) Assume |B| < |A| since ∃ functionf : A → B by definition ∀a ∈ A, ∃!b ∈ B s.t.f(a) = b. since |B| < |A| then ∃a 6= a0 s.t. f(a) = f(a0)(by pigeonhole principal) This is contradiction with the fact that f is a injection. (2) Assume |B| > |A| since ∃ functionf : A → B by definition ∀a ∈ A, ∃!b ∈ B s.t.f(a) = b. ∃b ∈ B s.t.there does not exist a ∈ A satisfying f(a) = b This is contradiction with the fact that f is a surjection. (3) (1)&(2) ⇒ (3). 2
Porpostion2: For sets X.Y.X]=n,Y [r].Let XY :={all functions f:Y X).Then XY=n". proof:Let B=fall vectors of length r over X}.define a function 9:Xy→B.f→(f1),,f) gis a injection since f≠f→(f(1),…,f(r)≠(f'(1),…,f'(r). g is a surjection.since∀(b1,·,b,）∈B.define f：Y→X,i→ bi(i.e.f(i)=bi)That is easy to get g(f)=(b1,..,b). →g is a bijection..→lXY1=lBl=n'. 0 Porpostion3: Let Y=[r],2Y :={all subsets of Y).then 2=2 proof:Let B=fall vectors of length r over (0,1)).define function f:2Y→B,A→f(A=(b,…,br) ae={老究 claim:f is a injection. claim:f is a surjection (b,…,b,)∈B define A={b:=1} →f(A)=(d,…,br) →f is a bijection.→Y|=lB=2". If is called as indicator(characteristic function)A is called as support of f(A)=(b1,·,b小
Porpostion2: For sets X,Y.|X| = n, Y = [r]. Let XY := {all functions f : Y → X}.Then |XY | = n r . proof: Let B={all vectors of length r over X}. define a function g : X Y → B. f 7→ (f(1), · · · , f(r)) g is a injection since f 6= f 0 ⇒ (f(1), · · · , f(r)) 6= (f 0 (1), · · · , f0 (r)). g is a surjection.since ∀(b1, · · · , br) ∈ B.define f : Y → X, i 7→ bi(i.e.f(i) = bi) That is easy to get g(f) = (b1, · · · , br). ⇒ g is a bijection.⇒ |XY | = |B| = n r . Porpostion3: Let Y = [r], 2 Y :={all subsets of Y }.then |2 Y | = 2r proof: Let B ={all vectors of length r over {0,1}}. define function f : 2Y → B, A → f(A) = (b1, · · · , br) where bi = 0, if i /∈ A; 1, if i ∈ A. claim:f is a injection. ∀A 6= A0 ,⇒ ∃i ∈ [r] s.t.i ∈ A, i /∈ A0 or i /∈ A, i ∈ A0 . ⇒ f(A) 6= f(A0 ). claim:f is a surjection. ∀(b1, · · · , br) ∈ B define A = {i|bi = 1} ⇒ f(A) = (b1, · · · , br) ⇒ f is a bijection.⇒ |Y | = |B| = 2r . [f is called as indicator(characteristic function) A is called as support of f(A) = (b1, · · · , br)]. 3
Binomial Coefficient: ·(（）份-fk-ofn ·ax=n(因）=k-bodts of(-() ·nl=n(n-1)…21. (n),=n(n-1)…(m-r-1) 0!=1. (Θ-1 (份=0>n Porpoaitiond(份)=a点o proof:Let B =fall vectors of length k over [n]consisting k dif- ferent elements.} (Double Counting) Way1:just directly count the number of vectors. Way2-Thre are(（)份）ysoe-fore-abat ,there are k!ways to order it to a vector. →B=(N →（份）=
Binomial Coefficient: • n k := #k−elements subsets of an n elements set. • a|X| = n, X k :={all k−subsets of X}. X k = n k . • n! = n(n − 1)· · · 2 · 1. (n)r := n(n − 1)· · ·(n − r − 1). 0! = 1. n 0 = 1. n k = 0 if k > n. Porposition4: n k = n! k!(n−k)! . proof: Let B ={all vectors of length k over [n] consisting k different elements.} (Double Counting) Way1:just directly count the number of vectors.|B| = n! k!(n−k)! . Way2:There are n k ways to choode k−subset of X.For each k−subset ,there are k! ways to order it to a vector. ⇒ |B| = n k k! ⇒ n k = n! k!(n−k)! . 4
Porposition5: @(因-(” ()(PTne)(图-(（么-）+(（：） proof: (1)trivial.(Hint:you can construct a bijection.) ·#料ak--(-）】 ·并ak-asog小-(（片)】 Combinating the two situations.then we prove(2)
Porposition5: (1) n k = n n − k . (2) (Pascal Triangle) n k = n − 1 k − 1 + n − 1 k . proof: (1) trivial.(Hint: you can construct a bijection.) (2) Separating X k into two parts. and find a fixed element t ∈ X. • #{all k−subsets containing t}= n − 1 k − 1 . • #{all k−subsets avoiding t}= n − 1 k . Combinating the two situations.then we prove (2). 5