Combinatorics,2017 Fall,USTC Week 3 Note 2 2017.9.29,Friday Given(an},we know GF∑ant"and EGF∑台zn. Def:Dirichlet series of{an}品1isa)=∑=号+器++… Letb(=E=,cy=alr)-E+.Thenc=∑arb,=∑aab whereover all potivefctors ofn Facts: (1)is commutative,associative and distributive with+. (2)All real sequences form a ring under and+ 网a-={&5 .Ched1= 1⊙f= (④ffog=I,we say f is the D-inverse o时g. Lemma 1.f=f(n)}is D-invertiblefff(1 ()suclh.So ”←”f)≠0.We want to prove3g={gmj}such that=L,ie. ∑9@={>1 That is f1)g(1)=1 、工公f9a④+f0gm=0n>1
Combinatorics, 2017 Fall, USTC Week 3 Note 2 2017.9.29,Friday Given {an}, we know GF Panx n and EGF P an n! x n. Def: Dirichlet series of {an}∞ n=1 is a(x) = P n ≥ 1 an nx = a1 1 + a2 2 x + a3 3 x + · · · . Let b(x) = P n ≥ 1 bn nx , c(x) = a(x)b(x) = P n ≥ 1 cn nx . Then cn = P rs = n arbs = P d | n adb n d , where P d | n means d runs over all positive factors of n. Dirichlet Convolution Def: The Dirichlet Convolution of f = {f(n)}∞ 1 and g = {g(n)}∞ 1 is a sequence f g, where f g(n) = P rs = n f(r)g(s) = P d | n f( n d )g(d). Facts: (1) is commutative, associative and distributive with +. (2) All real sequences form a ring under and +. (3) Identity is I = {I(n)} with I(n) = 1 n = 1, n = 1 0, n > 1 . Check f I = I f = f, ∀f. (4) If f g = I, we say f is the D-inverse of g. Lemma 1. f = {f(n)} is D-invertible iff f(1) 6= 0. Proof: ”⇒” f is D-invertible means ∃g = {g(n)} such that f g = I. So 1 = I(1) = (f g)(1) = f(1)g(1) ⇒ f(1) 6= 0. ”⇐” f(1) 6= 0. We want to prove ∃g = {g(n)} such that f g = I, i.e. X d | n f( n d )g(d) = 1, n = 1 0, n > 1 . That is f(1)g(1) = 1 P d | n d 6= n f( n d )g(d) + f(1)g(n) = 0, n > 1 . 1
We can define g(n)inductively,(1)and 9=高三9a.n>1 ◇ Invertible Formula:Assume a=1,then f例=∑a(宁g④→9网=∑（导回 Poo时f=aog←=g=b⊙f ◇ Mobius Fun.ction亚：μ={u(n)}°，where n=1 4(m) {ramuame others Theorem 1.Let e=fe(n))=(1).Then uoe=1,that is -{5 Proof:n=1,true. n 1,write n=pp,where p...r are distinct primes,0.If dn but d I p,then u(d)=0.So 朵o￡w=E-m-20-r=0 Mobius Inverse Formula For any two sequencesf(n)}and g(n)).we have f)=∑g(④=9(m)=∑“（信f Recalla:Euler function()=tm∈问l:gcd(m,m）=l. Write n=pf..p,then (n)=n.II(1). 2
We can define g(n) inductively, g(1) = 1 f(1) and g(n) = − 1 f(1) X d | n d 6= n f( n d )g(d), n > 1. Invertible Formula: Assume a b = I, then f(n) ≡ X d|n a( n d )g(d) ⇐⇒ g(n) ≡ X d|n b( n d )f(d) Proof: f = a g ⇐⇒ g = b f. Mobius F unction ¨ : µ = {µ(n)}∞ 1 , where µ(n) = 1 n = 1 (−1)k n is a product of k distinct primes 0 others . Theorem 1. Let e = {e(n)}∞ 1 = {1}∞ 1 . Then µ e = I, that is X d|n µ(d) = 1 n = 1 0 n > 1 . Proof: n = 1, true. n > 1, write n = p k1 1 · · · p kr r , where p1, . . . , pr are distinct primes, ki > 0. If d | n but d - Qr i=1 pi , then µ(d) = 0. So X d|n µ(d) = X d | Qr i=1 pi µ(d) = X I ⊆ [r] (−1)|I| = Xr i=0 r i (−1)i = 0 Mobius Inverse F ormula ¨ : For any two sequences {f(n)} and {g(n)}, we have f(n) ≡ X d|n g(d) ⇐⇒ g(n) ≡ X d|n µ( n d )f(d) Recall: Euler function ϕ(n) = ]{m ∈ [n] : gcd(m, n) = 1}. Write n = p k1 1 · · · p kr r , then ϕ(n) = n · Qr i=1 (1 − 1 pi ). 2
Theorem 2.Let N=[N(n))=(1.2.3...).Then ()p=Noh,im=④. (剧N=pog,ie.n=∑p(d. Poo哑：()n=…映，them o-a-动王 学宝学名亦 (2)By Movius Inverse Formula. Lemma 2.(1)V tuo sequences f.g,(N)(Ng)=N(g (2)If fog=I,then (Nf)o(Ng)=I. Theorem3.No(N4=I,p⊙(Nμ⊙e)=I Arrangements in a cycle(without seat number) Ifno repetitio n,it is =(n-1)1. Queio :Le t Cm(n) Suppose we have an cycle of the smallest period p(here p) e n-cycle a1a2..apa1a2...0p..a1a2..ap- Cut it into lines,then we have p different lines: (apa1...ap-1)(apa1...ap-1)...(apa1...ap-1) Let L(p)be ines of periodp,M(p)be cycles of period p.Ther L(p)=pM(p). 3
Theorem 2. Let N = {N(n)} = {1, 2, 3, · · · }. Then (1) ϕ = N µ, i.e. ϕ(n) = P d|n n d µ(d). (2) N = ϕ e, i.e. n = P d|n ϕ(d). Proof: (1) n = p k1 1 · · · p kr r , then 1 n ϕ(n) = Yr i=1 (1 − 1 pi ) = X I ⊆ [r] (−1)|I| 1 Q i∈I pi , X d|n µ(d) d = X d | Qr i=1 pi µ(d) d = X I ⊆ [r] (−1)|I| 1 Q i∈I pi (2) By Mobius Inverse F ormula ¨ . Def(Itemwise Product): The itemwise product of a = {an} and b = {bn} is a sequence ab, where (ab)(n) = a(n)b(n). E.g. NI = I, Ne = N. Lemma 2. (1) ∀ two sequences f, g, (Nf) (Ng) = N(f g). (2) If f g = I, then (Nf) (Ng) = I. Theorem 3. N (Nµ) = I, ϕ (Nµ e) = I. Arrangements in a cycle(without seat number) If no repetition, it is n! n = (n − 1)!. Question: Let Cm(n) = ] cycles of length n over [m]. Find Cm(n). Consider how many lines of length n corresponds to the same n-cycle. Suppose we have an n-cycle of the smallest period p(here p | n): a1a2 . . . apa1a2 . . . ap . . . a1a2 . . . ap. Cut it into lines, then we have p different lines: a1a2 . . . apa1a2 . . . ap . . . a1a2 . . . ap (a2 . . . apa1)(a2 . . . apa1). . .(a2 . . . apa1) . . . (apa1 . . . ap−1)(apa1 . . . ap−1). . .(apa1 . . . ap−1) Let L(p) be ]lines of period p, M(p) be ]cycles of period p. Then L(p) = pM(p). 3
Theorem4cn=(3m ▣ Theorem 5.C(n))m4. Exercise:Compute Cio(9)=111111340
Theorem 4. Cm(n) = P p|n 1 p P d|p µ( p d )md . Proof: Cm(n) = P p|n M(p), mn = P p|n L(p), then use Mobius Inverse F ormula ¨ . Theorem 5. Cm(n) = 1 n P d|n ϕ( n d )md . Proof: Let C = {Cm(n)}, M = {M(n)}, L = {L(n)}, f = {f(n)} = {mn}. Then C = M e, f = L e =⇒ L = f µ, L = NM. So NC = N(M e) = (NM) (Ne) = L N = f µ N = f ϕ. Exercise: Compute C10(9) = 111111340. 4
Combinatorics,2017 Fall,USTC Week 3 Note 3 2017.9.30,Saturday (1)Reftectivity:x<; (②Antisymmetry:fx≤割andy≤工，then z=; (3)Transitivity::fx≤yand y≤名，then x≤z E.g. (1)(亿2o,<,"less than”relation. (2)(亿>0，≤)，divisor poset,.a≤b÷a|b. (3)③(2x,≤)，incusion etio,A≤B台AsB Definition2.P-(X,≥，the incidence algebr of Pis A(P)={f:p2→Rf(,)=0,whenever本 E.g. (1)0(x,)=0. (Kroedker delta function:. 间zma《e-{&影 Facts: ()j,g∈A(P)→f+geA(P). (②f∈A(P)→cf∈A(P),ceR
Combinatorics, 2017 Fall, USTC Week 3 Note 3 2017.9.30, Saturday Definition 1. A partially ordered set(poset) P = (X, ≤) is a set X with a relation ”≤” on X, s.t. (1) Reflectivity: x ≤ x; (2) Antisymmetry: If x ≤ y and y ≤ x, then x = y; (3) Transitivity: If x ≤ y and y ≤ z, then x ≤ z. E.g. (1) (Z≥0, <), ”less than” relation. (2) (Z>0, ≤), divisor poset, a ≤ b ⇔ a | b. (3) (2X, ≤), inclusion relation, A ≤ B ⇔ A ⊆ B. Definition 2. P = (X, ≥), the incidence algebra of P is A(P) = {f : P 2 → R|f(x, y) = 0, whenever x y} E.g. (1) 0(x, y) = 0. (2) Kronecker delta function: δ(x, y) = 1, x = y 0, x 6= y . (3) Zeta function: ζ(x, y) = 1, x ≤ y 0, x y . Facts: (1) f, g ∈ A(P) ⇒ f + g ∈ A(P). (2) f ∈ A(P) ⇒ cf ∈ A(P), ∀c ∈ R. 1