Introduction to Enumerative Combinatorics (Walter Rudin Student Series in Advanced Mathematics)
Language: English
Pages: 544
ISBN: 007312561X
Format: PDF / Kindle (mobi) / ePub
Written by one of the leading authors and researchers in the field, this comprehensive modern text offers a strong focus on enumeration, a vitally important area in introductory combinatorics crucial for further study in the field. Miklós Bóna's text fills the gap between introductory textbooks in discrete mathematics and advanced graduate textbooks in enumerative combinatorics, and is one of the very first intermediate-level books to focus on enumerative combinatorics. The text can be used for an advanced undergraduate course by thoroughly covering the chapters in Part I on basic enumeration and by selecting a few special topics, or for an introductory graduate course by concentrating on the main areas of enumeration discussed in Part II. The special topics of Part III make the book suitable for a reading course.
This text is part of the Walter Rudin Student Series in Advanced Mathematics.
Hahn and Attaway Bundle: Matlab: A Practical Introduction to Programming and Problem Solving
Geometric Problems on Maxima and Minima
A Book of Set Theory (Dover Books on Mathematics)
Introduction to Genetic Algorithms
are not necessarily pairwise disjoint. Prove that 32. Prove that the Pigeonhole Principle holds, even if we do not assume that the sets AI, A 2 ,' .. ,Ak are pairwise disjoint. 33. + All points of the plane that have integer coordinates are colored red, blue, or green. Prove that there will be a rectangle whose vertices are all of the same color. 46 Chapter 1. Basic Methods 34. A computer program generated 175 positive integers at random, none of which had a prime divisor larger than 10.
boxes equally to the ends of the first k rows of the remaining shape. The obtained Ferrers shape will still have n boxes, and its kth row will be strictly longer than its (k + 1) st row since the former got a new box, and the latter did not. Its last row has at least k boxes since it could not be shorter than the removed row. Let this new shape be the Ferrers shape of f(s). We claim that f is indeed a bijection from S to T. We have seen in the previous paragraph that f (s) E T for all s E S. What
previous case. However, if s has exactly a parts, then all parts of s form a decreasing sequence of consecutive integers, so we must have s = (2a - 1, 2a - 2,·· ., a). In this case, the above definition of 9 does not work since there are not enough rows to distribute the boxes of the last row. So for this one exceptional case we will not define g. Note that in this case n = (2a - 1) + (2a - 2) + ... + a = a(3a - 1)/2, a pentagonal number, and one in which the minus sign is used. Note also that
our claim is proved. _1)0 Therefore, the left-hand side and the right-hand side count the same objects, so they are equal. <> See Exercise 31 for an alternative proof for part (b). An explicit formula for the numbers S(n, k) As an example for an application of the Inclusion-Exclusion Principle, assume that we have n different toys and that we want to distribute them among k children, where k ::::: n. However, we do not want to cause severe trauma to any children, therefore we insist that each
L 2 n2:0 3nxn - ~ L 2 n2:0 xn = L 3n - 1 xn. n2:0 2 The coefficient of xn in this power series is (3 n - 1)/2, so that is the coefficient of xn in (1-x)(1-3X)' Therefore, 3n - 1 [x n]A( x ) = an = 5 . 3n - --2-' (3.7) So this is the number of people wearing red hats after n hours. Chapter 3. Generating Functions 134 Remarks: 1. We could have used the fact that [ n] x x [ n-l] 1 (1 _ x) (1 - 3x) = x (1 - x) (1 - 3x) , and then we could have decomposed the latter into a sum of
