18 312 Algebraic Combinatorics Lionel Levine Lecture 4 Lecture date Feb 10 2011 1 Notes by Minseon Shin Stirling Numbers In the previous lecture the signless Stirling number of the first kind c n k was defined to be the number of permutations Sn with exactly k cycles c n k satisfies the linear recurrence c n k n 1 c n 1 k c n 1 k 1 Lemma 1 n X c n k xk x x 1 x n 1 k 1 Proof Induction on n Check that c 1 1 x x Then x x 1 x n 1 n 1 X k 1 n 1 X c n 1 k xk x n 1 c n 1 k x k 1 n 1 X c n 1 k n 1 xk k 1 k 1 n 1 X c n 1 k n 1 c n 1 k xk 1 k 1 n X c n k xk k 1 2 Corollary 2 Sn has an even number of cycles Sn has an odd number of cycles P Proof Plugging in x 1 into Lemma 1 we obtain nk 1 c n k 1 k 0 on the LHS the sum of terms with positive coefficient is equal to the number of permutations with an even number of cycles and the sum of terms with negative coefficient is equal to the number of permutations with an odd number of cycles 2 4 1 1 n of cycles in sgn and the set Sn sgn 1 is called the alternating group An By Corollary 2 An n 2 Corollary 3 The total number of cycles in all permutations in Sn is equal to n 11 12 n1 Pn Proof The total number of cycles in all permutations in S is equal to n k 1 k c n k Pn k 0 1 Cn x x x which is equal to Cn 1 where Cn x k 1 c n k x By Lemma 1 x n 1 so Cn0 x can also be written Cn0 x Cn x evaluated at x 1 is n 11 21 n1 2 1 x 1 x n 1 which From Corollary 3 it follows that the average number of cycles in all permutations in Sn is 1 1 1 1 2 n ln n Corollary 4 If p is prime then c p k is divisible by p for 1 k p Proof The polynomial x x 1 x n 1 considered modulo p has 0 1 p 1 as roots By Fermat s little theorem xp x has these same roots therefore their coefficients must be equal modulo p from which it follows that xk x x 1 x n 1 xk xp x for all k 2 Definition 5 S n k the Stirling number of the second kind is defined to be the number of partitions of n into exactly k nonempty subsets We have S n 1 1 S n 2 2n 2 2 S n n 1 n 2 and S n n 1 Lemma 6 S n k satisfies the recurrence S n k kS n 1 k S n 1 k 1 Proof Given a partition of n 1 there are 2 ways to construct a partition of n with k subsets either by adding n into a part of a partition of n 1 with k subsets or by adding the set n as a new part into a partition of n 1 with k 1 subsets 2 If f n k is a surjective function then the preimages f 1 1 f 1 k partition n There are k bijective mappings from parts of a partition with k parts to k Thus k S n k equals the number of surjective functions f n k 4 2 Using inclusion exclusion we find another formula for S n k let S be the set of all mappings f n k and Ei f i 6 im f Then S n k S i Ei k If I n with I r then i Ei k r n so using the notation in Lecture 2 X k n k r k r n nr r I n I r and n 1 X k S n k k i n 1 i k i i 0 Convention for all k 6 n we let S n k 0 Lemma 7 n X S n k x x 1 x k 1 xn k 1 Proof It suffices to check the identity for all x N xn all maps f n x n X all maps f n x such that im f k k 1 n X x surjective maps f n k k k 1 n X x k S n k k k 1 n X x x 1 x k 1 S n k k 1 2 Theorem 8 Let s n k 1 n k c n k and mn m X 1 0 S m k s k n mn k n 4 3 if m n Then else Proof We prove an alternative formulation of Theorem 8 Define the n n matrices M s j i and N S j i Since s j i S j i 0 if j i M and N are upper triangular Our goal is to prove that s 1 1 s 2 1 s n 1 S 1 1 S 2 1 S n 1 s 2 2 s n 2 S 2 2 S n 2 M N In s n n S n n We prove that M and N are change of basis matrices between two particular bases E F of the vector space Vn polynomials in x of degree at most n with constant term 0 where E e1 e2 en with ei xi F f1 f2 fn with fi x x 1 x i 1 In Lemma 1 we substitute x for x and multiply both sides of the equation by 1 n to obtain i X fi ek s i k for all i F EM k 1 thus M is the change of basis matrix from E to F By Lemma 7 we have ei i X fk S i k for all i E FN k 1 so N is the change of basis matrix from F to E This concludes the proof 2 2 Linear Recurrences d on the set of differentiable functions Linear operators such as the derivative operator dt f R R have discrete analogues Let V be the set of sequences s of all real numbers Then the identity I V V maps I s0 s1 s2 s0 s1 s2 the shift operator E V V maps E s0 s1 s2 s1 s2 s3 the difference operator is D E I discrete derivative The Fibonacci sequence F n is defined by F1 F2 1 and Fn 2 Fn 1 Fn for n 1 Fn is equal to the number of domino tiliings of a 2 n 1 rectangle and also to the number of sequences a1 an …