A brief journey in discrete mathematics

Acknowledgments......Page 7
Contents......Page 9
1 Introduction......Page 12
2 Let Me Count the Ways......Page 14
 2.1 Permutations: With and Without Replacement......Page 15
  2.1.1 Dearrangements......Page 18
 2.2 Combinations: Without Replacement......Page 20
  2.2.1 Binomial Identities......Page 21
 2.3 Combinations with Replacement......Page 27
  2.3.1 Binomial-R Identities......Page 29
  2.3.2 Polynomial Solutions to Combinatorial Problems......Page 31
 2.4 Transforms and Identities......Page 34
3 Syntax Precedes Semantics......Page 38
 3.1 Stirling Numbers of the First Kind......Page 40
 3.2 Stirling Numbers of the Second Kind......Page 43
  3.2.1 The Stirling Transform and Inverse......Page 46
 3.3 Combinatorial Interpretation......Page 47
4 Fearful Symmetry......Page 50
  4.1.1 Simple Polynomials......Page 51
  4.1.2 The Quadratic Equation......Page 52
  4.1.3 Equation of the Minimum Distance Line......Page 53
  4.1.4 The Pythagorean Theorem......Page 55
  4.1.5 Cubic Polynomials......Page 56
 4.2 Elementary Symmetric Polynomials......Page 59
  4.2.1 Newton–Girard Formula......Page 62
  4.2.2 Identities and Combinatorial Coefficients......Page 63
  4.2.3 Inclusion–Exclusion......Page 66
 4.3 Fundamental Theorem of Symmetric Polynomials......Page 68
 4.4 Galois' Theorem and Numerical Solutions......Page 70
 5.1 The Golden Ratio......Page 73
  5.1.1 Fibonacci Numbers......Page 75
  5.1.2 A Closed Form Solution......Page 77
 5.2 An Alternate Derivation......Page 82
 5.3 Generalized Fibonacci Numbers......Page 83
 5.4 k-Bonacci Numbers......Page 84
 5.5 Generalization of the Fibonacci Recurrence......Page 86
 6.1 The Mathematical Model......Page 88
  6.1.1 Games That End Even......Page 90
  6.1.2 Catalan Numbers......Page 91
  6.1.3 Non-intuitive Results......Page 93
 6.2 The Correct Insight......Page 99
 6.3 Particular Sequences......Page 100
 6.4 Conclusions......Page 101
7 Sums of the Powers of Successive Integers......Page 102
 7.1 A General Equation......Page 103
  7.1.1 Iterative Approach......Page 109
 7.2 Triangular Numbers......Page 111
 7.3 Cauchy's Theorem......Page 116
 8.1 Modular Arithmetic......Page 118
 8.2 Fermat's Little Theorem......Page 121
 8.3 Lagrange's Theorem......Page 123
 8.4 Wilson's Theorem......Page 124
 8.5 Cryptography......Page 126
 9.1 Properties of Prime Numbers......Page 128
  9.1.1 Properties of Integer Divisors......Page 131
 9.2 The Prime Counting Function......Page 133
 9.3 There Is Always a Prime Between n and 2n......Page 136
  9.3.1 The Prime Number Theorem with a Controversy......Page 140
10 Running Off the Page......Page 142
 10.1 Simple Continued Fractions......Page 143
  10.1.1 Periodic Simple Continued Fractions......Page 148
  10.1.2 Summary of Results......Page 149
 10.2 General Method to Create a Continued Fraction......Page 151
  10.2.1 Integer Quadratics and Quadratic Surds......Page 152
 10.3 Approximations Using Continued Fractions......Page 159
  10.3.1 Best Approximations......Page 165
 10.4 Lagrange's Theorem and Historical Review......Page 167
 A.1 Recurrence Relationships......Page 169
 A.2 Adding Zero to an Equation......Page 171
 A.3 Induction......Page 174
 A.4 Contradiction......Page 177
 A.5 Order of Summations......Page 179
B Notation and Identities Derived in the Book......Page 181
Bibliography......Page 188
Index......Page 189