“mcs”一2018/6/6一13：43一page vi-#6 公 Contents 13.5 Returning to Ks and K3.3 588 13.6 Coloring Planar Graphs 589 13.7 Classifying Polyhedra 591 13.8 Another Characterization for Planar Graphs 594 III Counting Introduction 603 14 Sums and Asymptotics 605 14.1 The Value of an Annuity 606 14.2 Sums of Powers 612 14.3 Approximating Sums 614 14.4 Hanging Out Over the Edge 618 14.5 Products 624 14.6 Double Trouble 627 14.7 Asymptotic Notation 630 15 Cardinality Rules 655 15.1 Counting One Thing by Counting Another 655 15.2 Counting Sequences 656 15.3 The Generalized Product Rule 659 15.4 The Division Rule 663 15.5 Counting Subsets 665 15.6 Sequences with Repetitions 667 15.7 Counting Practice:Poker Hands 671 15.8 The Pigeonhole Principle 676 15.9 Inclusion-Exclusion 685 15.10 Combinatorial Proofs 690 15.11 References 694 16 Generating Functions 735 16.1 Infinite Series 735 16.2 Counting with Generating Functions 737 16.3 Partial Fractions 743 16.4 Solving Linear Recurrences 746 16.5 Formal Power Series 751 16.6 References 754“mcs” — 2018/6/6 — 13:43 — page vi — #6 Contentsvi 13.5 Returning to K5 and K3;3 588 13.6 Coloring Planar Graphs 589 13.7 Classifying Polyhedra 591 13.8 Another Characterization for Planar Graphs 594 III Counting Introduction 603 14 Sums and Asymptotics 605 14.1 The Value of an Annuity 606 14.2 Sums of Powers 612 14.3 Approximating Sums 614 14.4 Hanging Out Over the Edge 618 14.5 Products 624 14.6 Double Trouble 627 14.7 Asymptotic Notation 630 15 Cardinality Rules 655 15.1 Counting One Thing by Counting Another 655 15.2 Counting Sequences 656 15.3 The Generalized Product Rule 659 15.4 The Division Rule 663 15.5 Counting Subsets 665 15.6 Sequences with Repetitions 667 15.7 Counting Practice: Poker Hands 671 15.8 The Pigeonhole Principle 676 15.9 Inclusion-Exclusion 685 15.10 Combinatorial Proofs 690 15.11 References 694 16 Generating Functions 735 16.1 Infinite Series 735 16.2 Counting with Generating Functions 737 16.3 Partial Fractions 743 16.4 Solving Linear Recurrences 746 16.5 Formal Power Series 751 16.6 References 754