Pearls of Discrete Mathematics

by Martin Erickson

Methods Used to Solve Discrete Math Problems
Interesting examples highlight the interdisciplinary nature of this area Pearls of Discrete Mathematics presents methods for solving counting problems and other types of problems that involve discrete structures. Through intriguing examples, problems, theorems, and proofs, the book illustrates the relationship of these structures to algebra, geometry, number theory, and combinatorics. Each chapter begins with a mathematical teaser to engage readers and includes a particularly surprising, stunning, elegant, or unusual result. The author covers the upward extension of Pascal’s triangle, a recurrence relation for powers of Fibonacci numbers, ways to make change for a million dollars, integer triangles, the period of Alcuin’s sequence, and Rook and Queen paths and the equivalent Nim and Wythoff’s Nim games. He also examines the probability of a perfect bridge hand, random tournaments, a Fibonacci-like sequence of composite numbers, Shannon’s theorems of information theory, higher-dimensional tic-tac-toe, animal achievement and avoidance games, and an algorithm for solving Sudoku puzzles and polycube packing problems. Exercises ranging from easy to challenging are found in each chapter while hints and solutions are provided in an appendix. With over twenty-five years of teaching experience, the author takes an organic approach that explores concrete problems, introduces theory, and adds generalizations as needed. He delivers an absorbing treatment of the basic principles of discrete mathematics.

280 pages, Paperback

First published January 1, 2009

Reviews

[Golven Leroy · Rating 5 out of 5]

Excellent. A fun reference to have, the exercises are interesting and demonstrate the concepts well. I will not remove stars for lack of depth in certain areas, because the whole point of the book is to make you curious, and to get you to do your own research. I will be keeping this one in my math bookshelf for sure!

[Maurizio Codogno · Rating 5 out of 5]

Quando si è piccoli si pensa che la matematica sia fatta solo di numeri (interi positivi, aggiungiamo poi quando cresciamo; al più ammettiamo lo zero). Poi crescendo si scoprono geometria, algebra, analisi... In tanti decidono che la matematica sia qualcosa di totalmente alieno: ma soprattutto ritengono che i numeri siano cose da bambini, e che con le scuole elementari si sia imparato tutto.

Nulla di più falso, naturalmente, come Martin Erickson mostra in questo bel libro. A parte la combinatorica (il modo per esempio di calcolare quante combinazioni diverse ci sono nel Superenalotto) i vari capitoli del libro mostrano svariate parti della matematica che fondamentalmente usano numeri interi, dalla teoria dei grafi a quella delle partizioni, dalle funzioni generatrici ai ricoprimenti esatti. Ciascun capitolo inizia con un teaser, cioè una (spesso buffa) affermazione che verrà dimostrata nel corso del capitolo stesso: si scoprono così teoremi "probabilisti" di esistenza (se c'è una probabilità maggiore di zero di avere una configurazione valida all'interno di un insieme di configurazioni, allora ce ne deve essere almeno una), e algoritmi che permettono di risolvere un sudoku... usando una matrice 729×324 con tutti 0 e 1.

Ogni capitolo termina con una serie di esercizi, sia puramente teorici che pratici (nel senso che per risolverli ci vuole un computer): fortunatamente al termine del libro ci sono gli aiuti (e qualche soluzione) :-)

[James Swenson · Rating 4 out of 5]

A good selection of interesting topics, and a very nice supply of problems (unfortunately, somewhat beyond the level of the introductory discrete-math course I often teach).