MATHEMATICS
CONTENTS INTRODUCTION PART I: BASICS FUNDAMENTAL COE?CIENTS ELEMENTARY COUNTING PRINCIPLES EXERCISES SUBSETS AND BINOMIAL COE?CIENTS SET-PARTITIONS AND STIRLING NUMBERS SN,K PERMUTATIONS AND STIRLING NUMBERS SN,K NUMBER-PARTITIONS LATTICE PATHS AND GAUSSIAN COE?CIENTS HIGHLIGHT: AZTEC DIAMONDS NOTES AND REFERENCES FORMAL SERIES AND IN?NITE MATRICES ALGEBRA OF FORMAL SERIES TYPES OF FORMAL SERIES IN?NITE SUMS AND PRODUCTS IN?NITE MATRICES AND INVERSION OF SEQUENCES PROBABILITY GENERATING FUNCTIONS HIGHLIGHT: THE POINT OF (NO) RETURN PART II: METHODS GENERATING FUNCTIONS SOLVING RECURRENCES EVALUATING SUMS THE EXPONENTIAL FORMULA NUMBER-PARTITIONS AND IN?NITE PRODUCTS HIGHLIGHT: RAMANUJAN’S MOST BEAUTIFUL FORMULA HYPERGEOMETRIC SUMMATION SUMMATION BY ELIMINATION INDE?NITE SUMS AND CLOSED FORMS RECURRENCES FOR HYPERGEOMETRIC SUMS HYPERGEOMETRIC SERIES HIGHLIGHT: NEW IDENTITIES FROM OLD SIEVE METHODS INCLUSION–EXCLUSION MÖBIUS INVERSION THE INVOLUTION PRINCIPLE THE LEMMA OF GESSEL–VIENNOT HIGHLIGHT: TUTTE’S MATRIX–TREE THEOREM ENUMERATION OF PATTERNS SYMMETRIES AND PATTERNS THE THEOREM OF PÓLYA–RED?ELD CYCLE INDEX SYMMETRIES ON N AND R HIGHLIGHT: PATTERNS OF POLYOMINOES PART III: TOPICS THE CATALAN CONNECTION CATALAN MATRICES AND ORTHOGONAL POLYNOMIALS CATALAN NUMBERS AND LATTICE PATHS GENERATING FUNCTIONS AND OPERATOR CALCULUS COMBINATORIAL INTERPRETATION OF CATALAN NUMBERS HIGHLIGHT: CHORD DIAGRAMS SYMMETRIC FUNCTIONS SYMMETRIC POLYNOMIALS AND FUNCTIONS HOMOGENEOUS SYMMETRIC FUNCTIONS SCHUR FUNCTIONS THE RSK ALGORITHM STANDARD TABLEAUX HIGHLIGHT: HOOK-LENGTH FORMULAS COUNTING POLYNOMIALS THE TUTTE POLYNOMIAL OF GRAPHS EULERIAN CYCLES AND THE INTERLACE POLYNOMIAL PLANE GRAPHS AND TRANSITION POLYNOMIALS KNOT POLYNOMIALS HIGHLIGHT: THE BEST THEOREM 10 MODELS FROM STATISTICAL PHYSICS 10 1 THE DIMER PROBLEM AND PERFECT MATCHINGS 10 2 THE ISING PROBLEM AND EULERIAN SUBGRAPHS 10 3 HARD MODELS 10 4 SQUARE ICE HIGHLIGHT: THE ROGERS–RAMANUJAN IDENTITIES SOLUTIONS TO SELECTED EXERCISES CHAPTER 1 CHAPTER 2 CHAPTER 3 CHAPTER 4 CHAPTER 5 CHAPTER 6 CHAPTER 7 CHAPTER 8 CHAPTER 9 CHAPTER 10 INTRODUCTION ENUMERATIVE COMBINATORICS ADDRESSES THE PROBLEM HOW TO COUNT THE NUMBER OF ELEMENTS OF A ?NITE SET GIVEN BY SOME COMBINATO- RIAL CONDITIONS WE COULD ASK, FOR EXAMPLE, HOW MANY PAIRS THE SET {1, 2, 3, 4} CONTAINS THE ANSWER IS 6, AS EVERYBODY KNOWS, BUT THE RESULT IS NOT REALLY EXCITING IT GIVES NO HINT HOW MANY PAIRS THE SETS {1, 2, , 6} OR {1, 2, , 100} WILL CONTAIN WHAT WE REALLY WANT IS A FORMULA FOR THE NUMBER OF PAIRS IN {1, 2, , N}, FOR ANY N A TYPICAL PROBLEM IN ENUMERATIVE COMBINATORICS LOOKS THEREFORE AS FOLLOWS: WE ARE GIVEN AN IN?NITE FAMILY OF SETS SN, WHERE N RUNS THROUGH SOME INDEX SET I (USUALLY THE NATURAL NUMBERS), AND THE PROBLEM CONSISTS IN DETERMINING THE COUNTING FUNCTION F : I ?N0, F (N) = |SN| THE SETS MAY, OF COURSE, HAVE TWO OR MORE INDICES, SAY SI,J , WITH F (I, J) = |SI,J| THERE IS NO STRAIGHTFORWARD ANSWER AS TO WHAT “DETERMINING” A COUNTING FUNCTION MEANS IN THE EXAMPLE OF THE NUMBER OF PAIRS, F (N) = N(N?1) , AND EVERYBODY WILL ACCEPT THIS AS A SATISFACTORY AN- SWER IN MOST CASES, HOWEVER, SUCH A “CLOSED” FORM IS NOT ATTAINABLE HOW SHOULD WE PROCEED THEN? SUMMATION SUPPOSE WE WANT TO ENUMERATE THE ?XED-POINT-FREE PERMUTATIONS OF {1, 2, , N}, THAT IS, ALL PERMUTATIONS ? WITH ?(I) ?I FOR ALL I LET DN BE THEIR NUMBER; THEY ARE CALLED THE DERANGEMENT NUMBERS, SINCE AFTER PERMUTING THEM NO ITEM APPEARS IN ITS ORIGINAL PLACE FOR N = 3, 1 2 2 3 AND 1 2 3 1 (?1)K K! SOMETIMES WE MIGHT EVEN PREFER A RECURRENCE TO A CLOSED FORMULA THE FIBONACCI INTRODUCTION NUMBERS FN ARE DE?NED BY F0 = 0, F1 = 1, FN = FN?1 +FN?2 (N ?2) WE WILL LATER DERIVE THE FORMULA FN = ( 1+ ? )N ?( 1? ?