GENERATINGFUNCTIONOLOGY
AN EASY TWO TERM RECURRENCE A SLIGHTLY HARDER TWO TERM RECURRENCE A THREE TERM RECURRENCE A THREE TERM BOUNDARY VALUE PROBLEM TWO INDEPENDENT VARIABLES ANOTHER 2-VARIABLE CASE EXERCISES FORMAL POWER SERIES THE CALCULUS OF FORMAL ORDINARY POWER SERIES GENERATING FUNCTIONS THE CALCULUS OF FORMAL EXPONENTIAL GENERATING FUNCTIONS POWER SERIES, ANALYTIC THEORY SOME USEFUL POWER SERIES DIRICHLET SERIES, FORMAL THEORY INTRODUCTION DE?NITIONS AND A QUESTION EXAMPLES OF EXPONENTIAL FAMILIES THE MAIN COUNTING THEOREMS PERMUTATIONS AND THEIR CYCLES SET PARTITIONS A SUBCLASS OF PERMUTATIONS INVOLUTIONS, ETC 2-REGULAR GRAPHS 3 10 COUNTING CONNECTED GRAPHS 3 11 COUNTING LABELED BIPARTITE GRAPHS 3 12 COUNTING LABELED TREES 3 13 EXPONENTIAL FAMILIES AND POLYNOMIALS OF ‘BINOMIAL TYPE ’ 3 14 UNLABELED CARDS AND HANDS 3 15 THE MONEY CHANGING PROBLEM 3 16 PARTITIONS OF INTEGERS 3 17 ROOTED TREES AND FORESTS 3 18 HISTORICAL NOTES GENERATING FUNCTIONS ?ND AVERAGES, ETC A GENERATINGFUNCTIONOLOGICAL VIEW OF THE SIEVE METHOD THE ‘SNAKE OIL’ METHOD FOR EASIER COMBINATORIAL IDENTITIES WZ PAIRS PROVE HARDER IDENTITIES GENERATING FUNCTIONS AND UNIMODALITY, CONVEXITY, ETC GENERATING FUNCTIONS PROVE CONGRUENCES THE CYCLE INDEX OF THE SYMMETRIC GROUP HOW MANY PERMUTATIONS HAVE SQUARE ROOTS? COUNTING POLYOMINOES 4 10 EXACT COVERING SEQUENCES THE LAGRANGE INVERSION FORMULA ANALYTICITY AND ASYMPTOTICS (I): POLES ANALYTICITY AND ASYMPTOTICS (II): ALGEBRAIC SINGULARITIES ANALYTICITY AND ASYMPTOTICS (III): HAYMAN’S METHOD SOLUTIONS CHAPTER (N ?1; F0 = 0; F1 = 1) THE SEQUENCE BEGINS WITH 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, THERE ARE EXACT, NOT-VERY-COMPLICATED FORMULAS FOR FN, AS WE WILL SEE LATER, IN EXAMPLE 2 OF THIS CHAPTER BUT, JUST TO GET ACROSS THE IDEA OF A GENERATING FUNCTION, HERE IS HOW A GENERATINGFUNCTIONOLOGIST MIGHT ANSWER THE QUESTION: THE NTH FIBONACCI NUMBER, FN, IS THE COE?CIENT OF XN IN THE EXPANSION OF THE FUNCTION X/(1 ?X ?X2) AS A POWER SERIES ABOUT THE ORIGIN YOU MAY CONCEDE THAT THIS IS A KIND OF ANSWER, BUT IT LEAVES A CERTAIN UNSATIS?ED FEELING IT ISN’T REALLY AN ANSWER, YOU MIGHT SAY, BECAUSE WE DON’T HAVE THAT EXPLICIT FORMULA IS IT A GOOD ANSWER? IN THIS BOOK WE HOPE TO CONVINCE YOU THAT ANSWERS LIKE THIS ONE ARE OFTEN SPECTACULARLY GOOD, IN THAT THEY ARE THEMSELVES ELEGANT, THEY ALLOW YOU TO DO ALMOST ANYTHING YOU’D LIKE TO DO WITH YOUR SEQUENCE, AND GENER- ATING FUNCTIONS CAN BE SIMPLE AND EASY TO HANDLE EVEN IN CASES WHERE EXACT FORMULAS MIGHT BE STUPENDOUSLY COMPLICATED HERE ARE SOME OF THE THINGS THAT YOU’LL OFTEN BE ABLE TO DO WITH GENER- ATING FUNCTION ANSWERS: (A) FIND AN EXACT FORMULA FOR THE MEMBERS OF YOUR SEQUENCE NOT ALWAYS NOT ALWAYS IN A PLEASANT WAY, IF YOUR SEQUENCE IS