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.

for one of them, we interrupt the mathematical discussion to relate a story about the young Carl Friedrich Gauss.{ At the age of seven, Gauss entered St. Katharine’s Volksschule in the duchy of Brunswick. One day his teacher, J. G. Bu¨ ttner, assigned Gauss’s class the problem of computing the sum 1 þ 2 þ Á Á Á þ 100: * Rediscovered many times, Theorem 1.5.2 can be found in Chu Shih-Chieh, Precious Mirror of the Four Elements, 1303. { Gauss (1777–1855) is one of the half-dozen greatest

replacement if order matters? (b) with replacement if order doesn’t matter? (c) without replacement if order doesn’t matter? (d) without replacement if order matters? 6 In how many ways can seven elements be chosen from a ten-element set (a) without replacement if order matters? (b) with replacement if order doesn’t matter? (c) without replacement if order doesn’t matter? 7 (d) with replacement if order matters? À Á n Show that multinomial coefficient nÀr;1;1;ÁÁÁ;1 ¼ Pðn; rÞ. 8 Compute the

þ ÀÀÀ xz3 þ Á Á Á þ z4 : 1.7.4 Example. What is the coefficient of xy in the expansion of ð1 þ x þ yÞ5 ? Solution: Because xy ¼ 13 xy, the multinomial theorem can be applied directly. À 5 Á The answer is 3;1;1 ¼ 20. Computing the coefficient of xy in ð2 þ x þ yÞ5 requires À 5 Þ ¼ 20. So, two steps. From the multinomial theorem, the coefficient of 23 xy is 3;1;1 5 3 the xy-term in the expansion of ð2 þ x þ yÞ is 20 Â 2 Â xy, and the coefficient we’re looking for is 20 Â 8 ¼ 160. 70 The

Prove Fermat’s ‘‘little theorem’’*, i.e., that np À n is an integer multiple of p. * After Pierre de Fermat (1601–1665). 1.7. Exercises 12 Give the (two-decision) inductive proof of the binomial theorem. 13 Write out all the terms of the minimal symmetric polynomial (a) M½6;4 ðx; y; zÞ 14 75 (b) M½5;5 ðx; y; zÞ Denote the coefficient of xr in ð1 þ x þ x2 þ Á Á Á þ xkÀ1 Þn by Ck ðn; rÞ. (a) Show that C2 ðn; rÞ ¼ Cðn; rÞ. (b) Compute C3 ð3; 3Þ. (c) If n > 1, show that Ck ðn; rÞ ¼

not disjoint, then oðA [ BÞ < oðAÞ þ oðBÞ, because oðAÞ þ oðBÞ counts every element of A \ B twice. (See Fig. 2.3.1.) Compensating for this double counting yields the formula oðA [ BÞ ¼ oðAÞ þ oðBÞ À oðA \ BÞ: What if there are three sets? Then oðA [ B [ CÞ ¼ oðA [ ½B [ CÞ ¼ oðAÞ þ oðB [ CÞ À oðA \ ½B [ CÞ: ð2:11Þ 142 The Combinatorics of Finite Functions A B Figure 2.3.1 Applying Equation (2.11) to oðB [ CÞ gives oðA [ B [ CÞ ¼ oðAÞ þ ½oðBÞ þ oðCÞ À oðB \ CÞ À oðA \ ½B [ CÞ: ð2:12Þ