Combinatorics
Russell Merris
Language: English
Pages: 576
ISBN: 047126296X
Format: PDF / Kindle (mobi) / ePub
A mathematical gem–freshly cleaned and polished
This book is intended to be used as the text for a first course in combinatorics. the text has been shaped by two goals, namely, to make complex mathematics accessible to students with a wide range of abilities, interests, and motivations; and to create a pedagogical tool, useful to the broad spectrum of instructors who bring a variety of perspectives and expectations to such a course.
Features retained from the first edition:
- Lively and engaging writing style
- Timely and appropriate examples
- Numerous well-chosen exercises
- Flexible modular format
- Optional sections and appendices
Highlights of Second Edition enhancements:
- Smoothed and polished exposition, with a sharpened focus on key ideas
- Expanded discussion of linear codes
- New optional section on algorithms
- Greatly expanded hints and answers section
- Many new exercises and examples
Student Solutions Manual for Stewart's Single Variable Calculus: Early Transcendentals (6th Edition)
rcrÀ1;k for all r, k ! 1. 24 Use Exercises 20(e) and 23 and the fact that gðrÞ ¼ 1 when n ¼ 2 to compute gð5Þ. 25 Let r and s be integers, 0 r < s, and let 0 Cðr; rÞ Cðr; r þ 1Þ B Cðr þ 1; rÞ Cðr þ 1; r þ 1Þ B C½r;s ¼ B .. .. @ . . Cðs; rÞ Cðs; r þ 1Þ 1 ÁÁÁ Cðr; sÞ Á Á Á Cðr þ 1; sÞ C C C: .. .. A . . ÁÁÁ Cðs; sÞ (a) Show that C½1;n ¼ Cn . (b) Exhibit C½2;6 . (c) Show that C½r;s is an ðs À r þ 1Þ-square matrix. (d) Show that the ði; jÞ-entry of C½r;s is Cðr þ i À 1; r þ j À 1Þ. (e)
with replacement where order matters, and 1003 ¼ 1 million different outcomes are possible. When the prizes are all the same (choosing with replacement when order doesn’t matter), the number of different outcomes is only Cð3 þ 100 À 1; 3Þ ¼ Cð102; 3Þ ¼ 171; 700. & The four ways to choose are summarized in Fig. 1.6.1. Because Cðr þ n À 1; rÞ ¼ Cðr þ n À 1; n À 1Þ 6¼ Cðr þ n À 1; nÞ, it is important to remember that in the last column of the table each entry takes the form CðÃ; rÞ, where r is the
From Example 2.1.18, Sð3; 2Þ ¼ 3, Sð4; 2Þ ¼ 7, and Sð4; 3Þ ¼ 6. Together with Sðm; 1Þ ¼ 1 ¼ Sðm; mÞ; m ! 1, this gives us a start at filling in some of the entries of Stirling’s triangle (Fig. 2.1.1). 2.1.20 Theorem. If m ! n ! 2, then Sðm þ 1; nÞ ¼ Sðm; n À 1Þ þ nSðm; nÞ. Theorem 2.1.20 allows us to fill in as many rows of Fig. 2.1.1 as we like, e.g., Sð5; 2Þ ¼ Sð4; 1Þ þ 2Sð4; 2Þ ¼1þ2Â7 ¼ 15 Sð5; 3Þ ¼ Sð4; 2Þ þ 3Sð4; 3Þ ¼7þ3Â6 ¼ 25; Sð5; 4Þ ¼ Sð4; 3Þ þ 4Sð4; 4Þ ¼6þ4Â1 ¼ 10: Thus, we obtain
urns U1 ; U2 ; . . . ; Un is the number of solutions to the equation u1 þ u2 þ Á Á Á þ un ¼ m in positive integers (no empty urns) or nonnegatve integers (empty urns allowed). The number of ways to distribute m unlabeled balls among n unlabeled urns is the number of n-part partitions of m (no empty urns) or the number of partitions of m into at most n parts (empty urns allowed). Details are left to the exercises. 2.2. 1 EXERCISES Confirm (a) Equation (2.4) when m ¼ 5. (b) Theorem 2.2.2 when m ¼
Polynomials Oriented Graphs Graphic Partitions Chapter 6 6.1. 6.2. 6.3. 6.4. Generating Functions Codes and Designs Linear Codes Decoding Algorithms Latin Squares Balanced Incomplete Block Designs 253 253 268 284 301 320 337 338 347 357 372 383 394 408 421 422 432 447 461 Appendix A1 Symmetric Polynomials 477 Appendix A2 Sorting Algorithms 485 Appendix A3 Matrix Theory 495 Bibliography 501 Hints and Answers to Selected Odd-Numbered Exercises 503 Index of Notation 541 Index
