Pearls of Discrete Mathematics

by Erickson; Martin

• ISBN13: 9781439816165
• ISBN10: 1439816166
• Edition: 1st
• Format: Nonspecific Binding
• Copyright: 2009-09-16
• Publisher: CRC Press

Summary

This book presents intriguing examples, facts, theorems, and proofs from the world of discrete mathematics. The author presents special topics that are not found elsewhere, including the upward extension of Pascal's triangle, the problem of counting Rook paths and Queen paths, higher-dimensional tic-tac-toe, recurrence relations and generating functions, the pigeonhole principle, information theory and codes, and game theory. He also explores connections between discrete structures and other branches of mathematics, such as combinatorics and algebra. The text includes examples, exercises, and appendices containing Mathematica ® calculations and related Internet resources.

Table of Contents

Counting: Basic	p. 1
Subsets of a Set	p. 3
Pascal's Triangle	p. 5
Binomial Coefficient Identities	p. 11
Counting: Intermediate	p. 19
Finding a Polynomial	p. 21
The Upward-Extended Pascal's Triangle	p. 25
Recurrence Relations and Fibonacci Numbers	p. 27
Counting: Advanced	p. 37
Generating Functions and Making Change	p. 39
Integer Triangles	p. 49
Rook Paths and Queen Paths	p. 53
Discrete Probability	p. 65
Probability Spaces and Distributions	p. 67
Markov Chains	p. 81
Random Tournaments	p. 91
Number Theory	p. 95
Divisibility of Factorials and Binomial Coefficients	p. 97
Covering Systems	p. 103
Partitions of an Integer	p. 109
Information Theory	p. 121
What Is Surprise?	p. 123
A Coin-Tossing Game	p. 133
Shannon's Theorems	p. 139
Games	p. 153
A Little Graph Theory Background	p. 155
The Ramsey Game	p. 165
Tic-Tac-Toe and Animal Games	p. 173
Algorithms	p. 181
Counters	p. 183
Listing Permutations and Combinations	p. 187
Sudoku Solving and Polycube Packing	p. 193
Hints and Solutions to Exercises	p. 201
Notation	p. 259
Bibliography	p. 261
Index	p. 263
Table of Contents provided by Ingram. All Rights Reserved.