18 312 Algebraic Combinatorics Lionel Levine Lecture 2 Lecture date Feb 3 2011 1 Notes by Jacob Bower Binomial Coefficients We begin by taking two variables x and y and looking at their sum to the nth power We write n n n n 1 1 n n 2 2 n n n n 1 n 1 x y x x y x y x y y 0 1 2 n 1 n n k Definition 1 We call the coefficients of this expansion the binomial coefficients We commonly write this in summation form as n x y n X n k 0 k xk y n k Examining x y n using subsets gives X x y n xn S y S S n This leads us to the observation that n of k element subsets of n k The value of the the binomial coefficient nk is n n k k n k Question 2 Find the value of n X n k k 0 2 1 Answer 3 We can write n X n k 0 k n X n 1 k 1 p k k k 0 In this way we see the sum is simply the expansion of x y n with x 1 and y 1 This means n X n 1 1 n 2n k k 0 Question 4 Find the value of n X n 1 k k k 0 Answer 5 We can write n X n k k 0 k 1 n X n k k 0 1 k 1 p k In this way we see the sum is simply the expansion of x y n with x 1 and y 1 This means n X n 1 k 1 1 n 0 k k 0 2 Pascal s Triangle An interesting topic related to the binomial coefficients is Pascal s triangle The nth row of the triangle displays the n binomial coefficients The first five rows of the triangle are 1 0 2 3 0 4 0 0 1 1 2 3 1 4 0 0 1 1 3 2 4 2 2 3 3 4 2 3 Putting the actual values into the triangle gives 1 1 1 1 1 1 2 3 4 1 3 6 2 2 1 4 1 4 4 This picture show that for the first five rows any non side entry of the triangle is equal to to the sum of the values it lies between in the row above That is we see that nk n 1 n 1 for our first 5 rows We may wish to know if this is true in general k 1 k Theorem 6 We wish to prove n n 1 n 1 k k 1 k Proof For a set X let X S X S n n m With this definition we know that if X m then X n n We then let X n and Y n 1 a X Y S X S k and n S k k Here is the symbol for the union of two disjoint sets Looking at the sizes of these sets gives n X Y Y n 1 n k k k k 1 k k 1 2 3 Inclusion Exclusion The goal of inclusion exclusion is count the number of elements in a set that are not in some other collection of sets where these other sets may have elements in common To begin the discussion of inclusion exclusion work we define the following n r N S is a set with S n and E1 Er S In this setting the goal of inclusion exclusion is then to count S ri 1 Ei Before we continue we define one more quantity X nk i I Ei I r I k 2 3 Theorem 7 We wish to prove S ri 1 Ei n n1 n2 n3 n4 1 r nr Proof To begin we write the sum of n s in set notation X 1 I i I Ei n ni n2 n3 n4 1 r nr I r Next we introduce an indicator function defined as 1 if x I Ei fI x 0 else Using this formula we write X X X 1 I i I Ei 1 I fI x I r x S I r XX 1 I fI x x S I r n XX X 1 k fI x x S k 0 I k But on examination we see X I k Jx jx fI x I r I k x EI k k We then have r n ni n2 n3 n4 1 nr n XX x S k 0 jx 1 k k Based on the results of Question 2 we know jx 0 if jx 6 0 1 if jx 0 k This means n ni n2 n3 n4 1 r nr x S x Ei 2 2 4 i 4 Drunken Mailman Problem The first example of using Inclusion Exclusion we look at will be the drunken mailman problem This problem presents us with a drunken mailman who has n distinct pieces of mail one for each of n distinct mailboxes Because the mailman is drunk he does not look at the addresses on the mail but instead simply puts one random piece of mail in each mailbox We want to figure out the probability that the mailman gets no pieces of mail in the correct mailbox To begin we need a few definitions Definition 8 A bijection f is a mapping of two sets f X Y that is both injective oneto one and surjective onto That is f has the properties f x f y x y injective y Y x X st f x y surjective Definition 9 A permutation of 1 2 n is a bijection where n n Definition 10 The symmetric group Sn is the group of all permutations of n Definition 11 A derangement is a permutation with no fixed points i 6 i i To begin our analysis of the problem let us note that Sn n because if we count the total number of permutations we see that to start we can map 1 to any n then we can map 2 to any of the remaining n 1 elements and so on Now in terms of the definitions above our drunken mailman problem becomes a question about permutation and derangements Each possible way the mailman can pass out mail is a permutation of n so the mailman has a total of n total ways to pass out mail If a mailman gets no pieces of mail in the correct mailbox than his permutation is a derangement We then want to count the number of possible derangements To do this we use inclusion exclusion We first define the sets S Sn and Ei i i Next we define X Nk i IEi I n I k Under inclusion exclusion we then have dn derangements of 1 n S ri 1 Ei N N1 N2 1 k Nk Because we have n total permutations we know N n 2 5 Look at …