onvolution of f and g is f*ge E.g. ()f*0(红，)=0. (②(f*6)(红，)=fz,)6(,)=f红，别=(6*f)(红，，5o6 is the identity.. 周60a=2.sfa Exercise:is commutative?(N)associative?(Y)distributive?(Y) Definition 4.ffg=6,we sayf is inuertible. f*h=2*f=6→91=2 Theorem1.f∈A(P),then f is invertible←一fz,x)≠0，红∈P. ∈Mtf9=.0≠1=6=9 (fe,)9红，)=（红，）=1 →gc= {,功=功=0 Then f红，xg(红，)+∑f红，9(2，)=0， <#≤制 ∑f红，2g(a,g)=0,by recursion. Note:ieg*f=d,thea r,g)=-7g/e.） a≤<w Definition 5.Mibius Function over Pisp=,where p(红，= else 2
Definition 3. Let f, g ∈ A(P), the Dedekind convolution of f and g is f ∗ g ∈ A(P), where (f ∗ g)(x, y) = P z : x ≤ z ≤ y f(x, z)g(z, y). E.g. (1) (f ∗ 0)(x, y) = 0. (2) (f ∗ δ)(x, y) = f(x, y)δ(y, y) = f(x, y) = (δ ∗ f)(x, y), so δ is the identity. (3) (f ∗ ζ)(x, y) = P z : x ≤ z ≤ y f(x, z) Exercise: ∗ is commutative?(N) associative?(Y) distributive?(Y) Definition 4. If f ∗ g = δ, we say f, g is invertible. f ∗ g1 = g2 ∗ f = δ ⇒ g1 = g2. Theorem 1. f ∈ A(P), then f is invertible ⇐⇒ f(x, x) 6= 0, ∀x ∈ P. Proof. ”⇒” ∃g ∈ A(P), s.t. f ∗ g = δ. 0 6= 1 = δ(x, x) = (f ∗ g)(x, x) = f(x, x)g(x, x). ”⇐” Find g ∈ A(P), s.t. f ∗ g = δ. f(x, x)g(x, x) = δ(x, x) = 1 =⇒ g(x, x) = 1 f(x,x) , ∀x P z x ≤ z ≤ y f(x, z)g(z, y) = δ(x, y) = 0 x 6= y . Then f(x, x)g(x, y) + X z x < z ≤ y f(x, z)g(z, y) = 0, i.e. g(x, y) = − 1 f(x,x) P z x < z ≤ y f(x, z)g(z, y) = 0, by recursion. Note: If use g ∗ f = δ, then g(x, y) = − 1 f(y,y) P z x ≤ z < y g(x, z)f(z, y) . Definition 5. Mobius F unction ¨ over P is µP = ζ −1 , where µP (x, y) = 1, x = y − P x < z ≤ y µP (z, y) = − P x ≤ z < y µP (x, z), x < y 0, else . 2
n()-∑c(a,yeP .Sw then c(=∑n(a)p(a,). The converse is also true. Proof.Let m be the minimal element of P.(P)as the following e动-{&动-{8外 营 色'g=f*(f=9*阳 Theorem3.-(亿0，≤）isthe divisor poset,hena(c,)=μ()ifaly. Proof.)Show ug(红，y）=n(L,￥)fz|y.Prove by induction on the#prime facte (2)Show d)=u(d).Prove by induction on the prime factors of d g(1,1)=(1) 4a(1,p2)=-((1,1)+4a(L,p)+4a(1,2》=1=4(p2 4(1,p)=0=4(p). Assume u(（L,d=μ(id has≤prime factors.. Case1:d=m…p跳+1 m1④=-，五，4ma,=-含(-=(-I+1=@ 3
Theorem 2. (Inverse Formula I) Suppose P has a unique minimal element. Let e : P → R be a function. If we have n : P → R s.t. n(y) = X z ≤ y e(z), ∀y ∈ P, then e(y) = X z ≤ y n(z)µP (z, y). The converse is also true. Proof. Let m be the minimal element of P. Define f, g ∈ A(P) as the following: f(x, y) = e(y), x = m 0, x 6= m , g(x, y) = n(y), x = m 0, x 6= m . We want to prove g = f ∗ ζ. g(m, y) = n(y) = P z ≤ y e(z) = P z ≤ y f(m, z) = P m ≤ z ≤ y f(m, z)ζ(z, y) = (f ∗ ζ)(m, y). ∀x 6= m, g(x, y) = 0 = (f ∗ ζ)(x, y) =⇒ g = f ∗ ζ =⇒ f = g ∗ µP =⇒ e(y) = f(m, y) = P m ≤ z ≤ y g(m, z)µP (z, y) = P z ≤ y n(z)µP (z, y). Theorem 3. Ω = (Z>0, ≤) is the divisor poset, then µΩ(x, y) = µ( y x ) if x | y. Proof. (1) Show µΩ(x, y) = µΩ(1, y x ) if x | y. Prove by induction on the ]prime factors of y x . If y x = 1, µΩ(x, y) = µΩ(1, 1) = 1. Assume µΩ(x, y) = µΩ(1, y x ) if y x has ≤ k prime factors. Take x | y and y x has k + 1 prime factors. µΩ(x, y) = − X x ≤ z < y µΩ(x, z) = − X x ≤ z < y µΩ(1, z x ), µΩ(1, y x ) = − X 1 ≤ z < y x µΩ(1, z) = − X x ≤ zx < y µΩ(1, z). (2) Show µΩ(1, d) = µ(d). Prove by induction on the ]prime factors of d. µΩ(1, 1) = µ(1), µΩ(1, p) = − X 1 ≤ z < p µΩ(1, z) = −1 = µ(p), µΩ(1, p1p2) = −(µΩ(1, 1) + µΩ(1, p1) + µΩ(1, p2)) = 1 = µ(p1p2), µΩ(1, p2 ) = 0 = µ(p 2 ). Assume µΩ(1, d) = µ(d) if d has ≤ k prime factors. Case 1: d = p1 · · · pk+1 µΩ(1, d) = − P 1 ≤ z < d µΩ(1, z) = − P k i=0 k+1 i (−1)i = (−1)k+1 = µ(d). 3
Case2:d=.…,1+…k=k+1amdk≥2 for somei∈问 u(d). Corollary1.gm=Xfa一fa）-()g@. then e(a)=∑up(c,n(a) Proof.Erercise! ◇ Theorem 5.X=n P.=(2x,<)with "C"relation.Then BP.(A.B)=(-1),ifAs B Proof.Prove by induction on B\Al(Erercise!) ◇ Corollary 2.( PaX=R=e,ag”mmn n:Pa→Rasn(0=A川=|Al e:P→Rasn(D=4n(2,4l ,名n0.nage sen Theorem4 --n Particwlarts.1 ◇ 4
Case 2: d = p k1 1 · · · p kr r , k1 + · · · kr = k + 1 and ki ≥ 2 for some i ∈ [r] µΩ(1, d) = − P 1 ≤ z < d µΩ(1, z) by induction ========== − P 1 ≤ z ≤ p1 · · · pr µΩ(1, z) = 0 = µ(d). Corollary 1. g(n) = P d|n f(d) ⇐⇒ f(n) = P d|n µ( n d )g(d). Theorem 4. (Inverse Formula II) Suppose P has a unique maximal element. Let e : P → R be a function. If we have n : P → R s.t. n(x) = X x ≤ z e(z), then e(x) = X x ≤ z µP (x, z)n(z). Proof. Exercise! Theorem 5. |X| = n Pn = (2X, ≤) with ”⊆” relation. Then µPn (A, B) = (−1)|B\A| , if A ⊆ B. Proof. Prove by induction on |B \ A|(Exercise!) Corollary 2. (IEP) |Ac 1 ∩ · · · ∩ Ac n | = P I ⊆ [n] (−1)|I| |AI |. Proof. Let X = [n], Pn = (2X, ≤) with ”⊆” relation. Define n : Pn → R as n(|I|) = |AI | = | ∩ i∈I Ai |, e : Pn → R as n(|I|) = |AI ∩ ( ∩ j /∈I A c j )|. Then n(J) = P J ⊆ I ⊆ [n] e(I). Since Pn has a unique maximal element [n], by Theorem 4 e(J) = X J ⊆ I ⊆ [n] µPn (J, I)n(I) = X J ⊆ I ⊆ [n] (−1)|I\J| |AI |. Particularly, e(∅) = |Ac 1 ∩ · · · ∩ Ac n | = P I ⊆ [n] (−1)|I| |AI |. 4
Combinatorics 2017 Fall week4 note Teaching by:Professor Xiande Zhang 2017.10.10 Polya Counting Theorem: Group Finite group Subgroups ou can find them in any Algebra book.We just give some exam- ples. Grop(R,),(,,(Z0,+),(亿0， is over n). Subgroup:(2Z,+)≤（亿，+）.(2Z,）(R,) Coset:G=(亿，+)，H=(3Z,+),H≤G. 0+H={…,-6,-3,0,3,6,…}=3+H. 1+H={…,-5,-2,1,4,7,…}=4+H 2+H={…,-4.-1,2.5,8.…}=5+H Fact:H≤(G,) (I)s∈G,sH=H.ifs∈H (2)Vs,t EG either sH=tH or (sH)(tH)=. 1
Combinatorics 2017 Fall week4 note Teaching by: Professor Xiande Zhang 2017.10.10 Polya Counting Theorem: Group Finite group Subgroups Coset You can find them in any Algebra book. We just give some examples. Group: (R, ·),(Z, ·),(Z>0, +),(Z>0, ·). Finite groups: Z/nZ := 0, 1, 2, · · · , n − 1,((Z/nZ) × , +),Sn ={all permutations over [n]}. Subgroup: (2Z, +) ≤ (Z, +).(2Z, ·) (R, ·). Coset: G = (Z, +), H = (3Z, +), H ≤ G. 0 + H = {· · · , −6, −3, 0, 3, 6, · · · } = 3 + H. 1 + H = {· · · , −5, −2, 1, 4, 7, · · · } = 4 + H. 2 + H = {· · · , −4, −1, 2, 5, 8, · · · } = 5 + H. Fact: H ≤ (G, ·) (1) ∀s ∈ G, sH = H. iff s ∈ H (2) ∀s, t ∈ G either sH = tH or (sH) ∩ (tH) = φ. 1
(3)G=...UgnH (4)VsH,sH=H just for finite group. (5)n.H=Gl denote n =[G:H].just for finite group. Group action:finite group(G,),X is aset,a group action is a map,denote X) (1)e*x=x,where e is id of G,Vr E X. (2)g,h∈G,z∈X,9*(h*x)=(g·h)*x. E.g. (1)(Sn,),[n],define a group action by(i)=a(i). (2)(G.),set G,define a group action by gh=gh,vg,hG. Def(G,）,X group action*,x∈X. 1.orbit of r,Orb(r)={g*r Vg EG). 2.stabilizer of Stab(r)=g EG:g*x=x}. 3.fixed points of g∈G,Fiz(g)={x∈X:g*x=x. Ex:Stab(r)≤(G,) Fact:X Orb(r1)U...UX=Orb(Fk).where Orb(i)nOrb(j)= 8系g286,2-ge8的. ①，1手1 =(132)(45),Z (1)(23)(4)(5).G 8r8=经卧.or0=or句=.om0=oo-
(3) G = g1H ∪ g2H ∪ · · · ∪ gnH (4) ∀s ∈ H, |sH| = |H|. just for finite group. (5) n · |H| = |G| denote n = [G : H].just for finite group. Group action: finite group (G, ·),X is a set,a group action is a map,denote by (G, X). ∗ : G × X → X,s.t. (1) e ∗ x = x,where e is id of G, ∀x ∈ X. (2) ∀g, h ∈ G, ∀x ∈ X, g ∗ (h ∗ x) = (g · h) ∗ x. E.g. (1) (Sn, ◦), [n], define a group action by σ ∗ (i) = σ(i). (2) (G, ·), set G,define a group action by g ∗ h = g · h, ∀g, h ∈ G. Def:(G, ·), X group action ∗, ∀x ∈ X. 1. orbit of x, Orb(x) = {g ∗ x : ∀g ∈ G}. 2. stabilizer of x, Stab(x) = {g ∈ G : g ∗ x = x}. 3. fixed points of g ∈ G, F ix(g) = {x ∈ X : g ∗ x = x}. Ex:Stab(x) ≤ (G, ·). Fact:X = Orb(x1)∪ · · · ∪ X = Orb(xk). where Orb(xi)∩ Orb(xj ) = φ, i 6= j. E.g.X = [5], Z = (123)(45) then Z 2 = (132)(4)(5), Z3 = (1)(2)(3)(45), Z4 = (123)(4)(5), Z5 = (132)(45), Z6 = (1)(2)(3)(4)(5).G =< Z > . Orb(1) = {1, 2, 3}, Orb(4) = Orb(5) = {4, 5}, Orb(1) = Orb(2) = Orb(3) = {1, 2, 3}. 2