Stephan Wagner Version: July 2011 - Stellenbosch …

1 CombinatoricsStephan WagnerVersion: july 2011 Contents1 Elementary enumeration Problems ..72 Properties of binomial coefficients, combinatorial The recursion .. The binomial theorem and its applications .. Bijections and the Catalan numbers .. Additional problems ..163 The principle of inclusion and A simple example .. The general formula .. Applications .. Additional problems ..234 Enumeration by means of A first example .. Finding and solving linear recursions .. Generating functions .. Additional problems ..365 The pigeonhole The principle and a first example .. Various applications .. Additional problems ..416 Potential functions and Invariants .. Potential functions .. Additional problems.

2 497 some concepts in graph Definitions .. Eulerian and Hamiltonian cycles .. Plane graphs and Euler s polyhedron formula .. Ramsey numbers .. Additional problems ..578 Induction proofs in combinatorics .. Combinatorial geometry .. Mathematical games .. The principle of double counting .. Additional problems ..65 PrefaceThese notes are aimed at advanced participants in mathematical olympiads and theircoaches. some of the parts cover more than what is usually needed in mathematical com-petitions. For example, the parts of Chapter 2 that follow Corollary or the treatmentof generating functions in Section are mostly aimed at particularly interested far as graph theory (Chapter 7) is concerned, it should be mentioned that general un-derstanding of the main concepts is more important for the solution of olympiad problemsthan the actual theory that is usually not needed at comments, suggestions, corrections, etc.

3 Can be directed to me via wish everyone a pleasant journey through the world of combinatorics, and I hope thatyou will find these notes 1 Elementary enumeration principlesSequencesTheorem arenkdifferent sequences of lengthkthat can be formed from ele-ments of a setXconsisting ofnelements (elements are allowed to occur several times ina sequence).Proof:For every element of the sequence, we have exactlynchoices. Therefore, there aren n .. n ktimes=nkdifferent possibilities. Example:Given an alphabet ofnletters, there are exactlynkk-letter words. Forinstance, there are 8 three-digit words (not necessarily meaningful) that can be formedfrom the lettersSandO:SSS, SSO, SOS, OSS, SOO, OSO, OOS, number of 100-letter words over the alphabet A,C,G,T is 4100, which is a 61-digitnumber; DNA strings as they occur in cells of living organisms are much longer, of course.

4 PermutationsTheorem number of possibilities to arrangen(distinguishable) objects in a row(so-calledpermutations) isn! =n (n 1) .. 3 2 :There are obviouslynchoices for the first position, thenn 1 remaining choicesfor the second position (as opposed to the previous theorem),n 2 for the third position,etc. Therefore, one obtains the stated formula. Example:There are 6 possibilities to arrange the letters A,E,T in a row:4 CHAPTER 1. ELEMENTARY ENUMERATION PRINCIPLES5 AET, ATE, EAT, ETA, TAE, :By definition,n! satisfies the equationn! =n (n 1)!, which remains true ifone defines 0! = 1 (informally, there is exactly one possibility to arrange 0 objects, andthat is to do nothing at all).Example:In how many ways can eight rooks be placed on an 8 8-chessboard insuch a way that no horizontal or vertical row contains two rooks?

5 In order to solve this problem, let us assign coordinates (a-h and 1-8 respectively) tothe squares of the chessboard. A possible configuration would then be a3, b5, c1, d8, e6, f2,g4, h7 (for instance). Generally, there must be exactly one rook on each vertical row (a-h),and analogously one rook on each horizontal row (1-8). Each permutation of the numbers1 to 8 corresponds to exactly one feasible configuration (in the above case, 3-5-1-8-6-2-4-7),and so there are exactly 8! = 40320 without repetitionsTheorem number of sequences of lengthkwithout repetitions whose elements aretaken from a setXcomprisingnelements isnk=n (n 1) (n 2) ..(n k+ 1) =n!(n k)!.Proof:The proof is essentially the same as for Theorem : for the first element, therearenpossible choices, thenn 1 for the second element, etc. For the last element, therearen k+ 1 choices left.

6 Remark:The case of permutations is clearly a special case of Theorem , corre-sponding tok= called afalling factorial(read: nto thekfalling ).Choosing a subsetTheorem number of possibilities to choose a subset ofkelements from a set ofnelements (the order being irrelevant) is(nk)=n!k!(n k)!.Proof:Letxbe the number of possibilities that we are looking for. Once thekelementshave been chosen (for which there arexpossible ways), one hask! possibilities (by Theo-rem ) to arrange them in a sequence. Therefore,x k! is exactly the number of possiblesequences ofkdistinct elements, for which we have the formulax k! =n!(n k)!CHAPTER 1. ELEMENTARY ENUMERATION PRINCIPLES6by Theorem , so thatxis obtained immediately. Remark:The difference between Theorem and Theorem lies in the fact thatthe order plays a role in the former, which is does not in the latter.

7 Each subset corre-sponds to exactlyk! sequences: for instance, the subset{A,E,T}of the set{A,B,..,Z}corresponds to the sequencesAET, ATE, EAT, ETA, TAE, formula for the binomial coefficient only makes sense if 0 k n. This is also quiteintuitive as no subset can comprise more elements than the original set. It is often usefulto define(nk)= 0 if eitherk <0 ork > n. Later we will also give a more general definitionfor the binomial :The number of six-element subsets of{1,2,..,49}(Lotto) is(496)=49!6! 43!= :An obvious property of(nk)is the identity(nk)=(nn k),which follows immediately from the formula. However, it also has a combinatorial meaning:choosingkelements is equivalent to not choosingn kelements. The generalisation ofthis principle leads us to the so-calledmultinomial a set into groupsTheorem number of possibilities to divide a setXinto groupsX1,X2.

8 ,Xrwhose sizes are prescribed to bek1,k2,..,krrespectively (wherek1+k2+..+kr=n) isgiven by(nk1,k2,..,kr)=n!k1! k2! .. kr!.Proof:By induction onr; forr= 1, the statement is trivial. Forr 2, one has(nk1)choices for the elements ofX1, and by the induction hypothesis,(n k1)!k2!k3!..kr!possible ways to divide the remainingn k1elements. Therefore, we have exactly(nk1) (n k1)!k2!k3!..kr!=n!k1!(n k1)! (n k1)!k2!k3!..kr!=n!k1! k2! .. kr!possibilities, as claimed. CHAPTER 1. ELEMENTARY ENUMERATION PRINCIPLES7 Choosing a multisetTheorem number of ways to choosekelements from a set ofnelements, repe-titions allowed, is(n+k 1k).Proof:LetX={x1,x2,..,xn}be the set. A choice is characterised by the numberof times that each of the elements is selected. Iflidenotes the multiplicity ofxiin ourcollection, then the problem is equivalent to determining the number of solutions ofl1+l2+.

9 +ln=k,wherel1,l2,..,lnhave to be non-negative integers. Equivalently, we can writemi=li+ 1and ask for the number of positive integer solutions to the equationm1+m2+..+mn=k+n.( )Let us imaginek+ndots in a row. Each solution to the equation ( ) corresponds toa way of separating the dots by insertingn 1 bars at certain places (Figure ). Sincethere aren+k 1 positions for the bars, one has(n+k 1n 1)=(n+k 1k)possible ways to place the bars. | | | | Figure : Dots and :A finite sequencem1,m2,..,mkof positive integers summing ton(that is,n=m1+m2+..+mk) is called acompositionofn; the above argument ( dots and bars )shows that every positive integernhas exactly(n 1k 1)compositions ProblemsProblem 1 How many Lotto-combinations (6 numbers out of{1,2,..,49}) contain twoconsecutive numbers?Problem 2 King Arthur chooses three of the 25 knights sitting around his table to fighta fearsome dragon.

10 How many possible choices are there, if no two of the chosen knightsshould sit next to each other?Problem 3 How many possible ways are there to form five-letter words using only theletters A,B,C,D,E,F,G,H? How many such words are there that do not contain a lettertwice?CHAPTER 1. ELEMENTARY ENUMERATION PRINCIPLES8 Problem 4In how many possible orders can the letters of the word MATHEMATICS bearranged?Problem 5At a sokkie, there are 20 girls and 20 boys. How many ways are there to form20 pairs?Chapter 2 Properties of binomial coefficients,combinatorial identitiesIt has already been mentioned that(nk)=(nn k). This is just one of a huge numberof identities that are satisfied by the binomial coefficients. some of them are presentedhere mostly because the proofs are instructive and the methods can be used frequentlyin different The recursionTheorem binomial coefficients satisfy the recursion(nk)=(n 1k 1)+(n 1k)(0 k n).