The four-part treatment begins with a section on counting and listing that covers basic counting, functions, decision trees, and sieving methods. The following section addresses fundamental concepts in graph theory and a sampler of graph topics. The third part examines a variety of applications relevant to computer science and mathematics, including induction and recursion, sorting theory, and rooted plane trees. The final section, on generating functions, offers students a powerful tool for studying counting problems. Numerous exercises appear throughout the text, along with notes and references. The text concludes with solutions to odd-numbered exercises and to all appendix exercises.
The four-part treatment begins with a section on counting and listing that covers basic counting, functions, decision trees, and sieving methods. The following section addresses fundamental concepts in graph theory and a sampler of graph topics. The third part examines a variety of applications relevant to computer science and mathematics, including induction and recursion, sorting theory, and rooted plane trees. The final section, on generating functions, offers students a powerful tool for studying counting problems. Numerous exercises appear throughout the text, along with notes and references. The text concludes with solutions to odd-numbered exercises and to all appendix exercises.
Foundations of Combinatorics with Applications
480
Foundations of Combinatorics with Applications
480eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
Overview
The four-part treatment begins with a section on counting and listing that covers basic counting, functions, decision trees, and sieving methods. The following section addresses fundamental concepts in graph theory and a sampler of graph topics. The third part examines a variety of applications relevant to computer science and mathematics, including induction and recursion, sorting theory, and rooted plane trees. The final section, on generating functions, offers students a powerful tool for studying counting problems. Numerous exercises appear throughout the text, along with notes and references. The text concludes with solutions to odd-numbered exercises and to all appendix exercises.
Product Details
| ISBN-13: | 9780486151502 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 01/18/2013 |
| Series: | Dover Books on Mathematics |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 480 |
| File size: | 14 MB |
| Note: | This product may take a few minutes to download. |
Read an Excerpt
Foundations of Combinatorics with Applications
By Edward A. Bender, S. Gill Williamson
Dover Publications, Inc.
Copyright © 2006 Edward A. Bender and S. Gill WilliamsonAll rights reserved.
ISBN: 978-0-486-15150-2
CHAPTER 1
Basic Counting
Introduction
Before beginning, we must confront some matters of notation. Two words that we shall often use are set and list. Both words refer to collections of objects. There is no standard notation for lists. Some of those in use are
apple banana pear peach a list of four items ...
apple, banana, pear, peach commas added for clarity ...
and (apple, banana, pear, peach) parentheses added.
The notation for sets is standard: the items are separated by commas and surround by curly brackets as in
{apple, banana, pear, peach}.
The curly bracket notation for sets is so well established that you can normally assume it means a set—but beware, Mathematica® uses curly brackets for lists.
What is the difference between a set and a list? Quite a bit, and nothing. "Set" means a collection of distinct objects in which the order doesn't matter. Thus
{apple, peach, pear} and {peach, apple, pear}
are the same sets, and the set {apple, peach, apple} is the same as the set {apple, peach}. In other words, repeated elements are treated as if they occurred only once. Thus two sets are the same if and only if each element that is in one set is in both. In a list, order is important and repeated objects are usually allowed. Thus
(apple, peach) (peach, apple) and (apple, peach, apple)
are three different lists. Two lists are the same if and only if they have exactly the same items in exactly the same positions. Thus, sets and lists are different.
On the other hand, people talk about things like "unordered lists," "sets with repetition," and so on. In fact, a set with repetition is so common that it has a name: multiset. Two multisets are the same if and only if each item that occurs exactly k times in one of them occurs exactly k times in both. In summary
• list: an ordered sequence (repeats allowed),
• set: a collection of distinct objects where order does not matter,
• multiset: a collection of objects (repeats allowed) where order does not matter.
Thus, an ordered set with repetition allowed is a list and an unordered list of distinct elements is a set. Whenever we refer to a list, we will indicate whether the elements must be distinct. Unless we say otherwise, a list is ordered. An ordered list is sometimes called a string, a sequence or a word. A list is also called a sample or a selection, especially in probability and statistics. Lists are sometimes called vectors and the elements components.
The terminology "k -list" is frequently used in place of the more cumbersome "k long list." Similarly, we use k -set and k -multiset. Vertical bars (also used for absolute value) are used to denote the number of elements in a set or in a list. For example, if S is an n -set, then |S | = n.
We want to know how many ways we can do various things with a set. Here are some examples, which we illustrate by using the set S = {x, y, z}.
1. How many ways can we list, without repetition, all the elements of S? This means, how many ways can we arrange the elements of S in an (ordered) list so that each element of S appears exactly once in each of the lists. For the illustration, there are six ways: xyz, xzy, yxz, yzx, zxy and zyx. (These are all called permutations of S. People often use Greek letters like π and σ to indicate a permutation of a set.)
2. How many ways can we construct a k -list of distinct elements from the set? When k = |S|, this is the previous question. If k = 2 in the illustration, there are six ways: xy, xz, yx, yz, zx and zy.
3. If the list in the previous question is allowed to contain repetitions, what is the answer? There are nine ways for the illustration: xx, xy, xz, yx, yy, yz, zx, zy and zz.
4. If, in Questions 2 and 3, the order in which the elements appear in the list doesn't matter, what are the answers? For the illustration, the answers are three and six, respectively.
5. How many ways can the set S be partitioned into a collection of k pairwise disjoint nonempty smaller sets? With k = 2, the illustration has three such: {{x}, {y, z}}, {{x, y}, {z}} and {{x,z}, {y}}.
We'll learn how to answer these questions without going through the time-consuming process of constructing (listing) all the items in question as we did for our illustration. Our answer to the last question will be somewhat unsatisfactory. Other answers to it will be discussed in later chapters.
1.1 Lists with Repetitions Allowed
How many ways can we construct a k -list (repeats allowed) using an n-set? Look at our illustration in Question 3 above. The first entry in the list could be x, y or z. After any of these there were three choices (x, y or z) for the second entry. Thus there are 3 × 3 = 9 ways to construct such a list. The general pattern should be clear: There are n ways to choose each list entry. Thus
Theorem 1.1There are nkways to construct a k-list from an n-set.
This calculation illustrates an important principle:
Theorem 1.2 Rule of ProductSuppose structures are to be constructed by making a sequence of k choices such that, (i) the ith choice can be made in ci ways, a number independent of what choices were made previously, and (ii) each structure arises in exactly one way in this process. Then, the number of structures is c1 × ... × ck.
"Structures" as used above can be thought of simply as elements of a set. We prefer the term structures because it emphasizes that the elements are built up in some way; in this case, by making a sequence of choices. In the previous calculation, the structures are lists of k things which are built up by adding one thing at a time. Each thing is chosen from a given set of n things and c1 = c2 = ... = ck = n.
Definition 1.1 Cartesian ProductIf C1, ..., Ck are sets, theCartesian productof the sets is written C1 × ... × Ck and consists of all k-lists (x1, ..., xk) with xi [member of] Ci for 1 ≤ i ≤ k.
A special case of the Rule of Product is the fact that the number of elements in C1 × ... × Ck is the product |C1| ... |Ck|. Here Ci is the collection of ith choices and ci = |Ci|. This is only a special case because the Rule of Product would allow the collection Cito depend on the previous choices x1, ..., xi-1 as long as the number ci of possible choices does not depend on x1, ..., xi-1. The last example in Appendix A gives a proof of this special case of the Rule of Product. In fact, that proof can be altered to give a proof of the general case of the Rule of Product. We will not do so.
Here is a property associated with Cartesian products that we will find useful in our later discussions.
Definition 1.2 Lexicographic OrderIf C1, ..., Ck are ordered lists of distinct elements, we may think of them as sets and form the Cartesian product P = C1 × ... × Ck. Thelexicographic orderon P is defined by saying that a1 ... ak< b1 ... bkif and only if there is some t ≤ k such that ai = bi for i < t and at< bt.
Often we say lex order instead of lexicographic order. If all the Ci' s equal (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), then lex order is simply numerical order of k digit integers with leading zeroes allowed. Suppose that all the Ci' s equal (
Example 1.1 A simple count The North-South streets in Rectangle City are named using the numbers 1 through 12 and the East-West streets are named using the letters A through H. Thus, the most southwesterly intersection occurs where First and A streets meet. How many blocks are within the city?
We may think of the city of as consisting of rows of blocks. Each row contains the blocks encountered as we cross the city from East to West. The number of rows is the number of rows of blocks encountered as we cross the city from North to South. This is much like the rows and columns of a matrix. We can apply the Rule of Product: Choose a row and then choose a block in that row. What answer does this give? If you think it is 12 × 8 = 96, you're almost correct. Read on.
Each block can be labeled by the streets at its southwesterly corner. These labels have the form (x,y) where x is between 1 and 11 inclusive and y is between A and G. (If you don't see why 12 and H are missing, draw a picture and look at southwesterly corners.) By the Rule of Product there are 11 × 7 = 77 blocks. In this case the structures can be taken to be the descriptions of the blocks. Each description has two parts: the names of the north-south and East-West streets at the block's southwest corner.
Example 1.2 Counting names We now return to the faraway galaxy that was mentioned in Example 2 (p. 1).
The possible positions for the two vowels are (2, 4), (2, 5) and (3, 5). Each of these results in two isolated consonants and two adjacent consonants. Thus the answer is the product of the following factors:
• choose the vowel locations (3 ways);
• choose the vowels (2 × 2 ways);
• choose the isolated consonants (3 × 3 ways);
• choose the adjacent consonants (3 × 2 ways).
The answer is 648. This construction can be interpreted as a Cartesian product as follows. C1 is the set of lists of possible positions for the vowels, C2 is the set of lists of vowels in those positions, and C3 and C4 are sets of lists of consonants. Thus
C1 = {(2, 4), (2, 5), (3, 5)}
C2 = {AA, AI, IA, II}
C3 = {LL, LS, LT, SL, SS, ST, TL, TS, TT}
C4 = {LS, LT, SL, ST, TL, TS}.
For example, ((2,5), IA, SS, ST) in the Cartesian product corresponds to the word SISTAS.
Here's another important principle, the proof of which is self evident:
Theorem 1.3 Rule of SumSuppose a set T of structures can be partitioned into sets T1, ..., Tjso that each structure in T appears in exactly one Ti, then
|T | = |T1| + ... +|Tj|.
Example 1.3 Counting names (revisited) We'll redo the previous example using this principle.
The possible vowel (V) and consonant (C) patterns for names are CCVCVC, CVCCVC and CVCVCC. Since these patterns are disjoint and cover all cases, we must compute the number of names of each type and add the results together. For the first pattern we have a product of six factors, one for each choice of a letter: 3 × 2 × 2 × 3 × 2 × 3 = 216. The other two patterns also give 216, for a total of 648 names.
This approach has a wider range of applicability than the method we used in the previous example. We were only able to avoid the Rule of Sum in the first method because each pattern contained the same number of vowels, isolated consonants and adjacent consonants. Here's an example that requires the Rule of Sum. Suppose a name consists of only four letters, namely two vowels and two consonants, constructed so that the vowels are not adjacent and, if the consonants are adjacent, then they are different. There are four patterns: CVCV, VCVC, VCCV. By the Rule of Product, the first two are each associated with 36 names, but VCCV is associated with only 24 names because of the adjacent consonants. Hence, we cannot choose a pattern and then proceed to choose vowels and consonants. On the other hand, we can apply the Rule of Sum to get a total of 96 names.
Example 1.4 Smorgasbord College committees Smorgasbord College has four departments which have 6, 35, 12 and 7 faculty members. The president wishes to form a faculty judicial committee to hear cases of student misbehavior. To avoid the possibility of ties, the committee will have three members. To avoid favoritism the committee members will be from different departments and the committee will change daily. If the committee only sits during the normal academic year (165 days), how many years can pass before a committee must be repeated?
If T is the set of all possible committees, the answer is |T|/165. Let Ti be the set of committees with no members from the ith department. By the Rule of Sum |T| = |T1| + |T2| + |T3| + |T4|. By the Rule of Product
|T1| = 35 × 12 × 7 = 2940 | T3| = 35 × 6 × 7 = 1470
|T2| = 6 × 12 × 7 = 504
|T4| = 35 × 12 × 6 = 2520.
Thus the number of years is 7434/165 = 45+. Due to faculty turnover, a committee need never repeat—if the president's policy lasts that long.
Using the Rules of Sum and Product
Whenever we encounter a new technique, there are two questions that arise:
• When is it used?
• How is it used?
For the Rules of Sum and Product, the answers are intertwined:
Technique Rules for AND and ORSuppose you wish to count the number of structures in a set and that you can describe how to construct the structures in terms of subconstructions that are connected by "ands" and "ors." If this leads to the construction of each structure in a unique way, then the Rules of Sum and Product apply. To use them, replace "ands" by products and "ors" by sums. Whenever you write something like "Do A AND do B," it should mean "Do A AND THEN do B" because the Rule of Product requires that the choices be made sequentially. We will usually omit "then".
Example 1.5 Applying the technique To see how this technique is applied, let's look back at Example 1.4. A committee consists of either
• One person from Dept. 1 AND one person from Dept. 2 AND one person from Dept. 3, OR
• One person from Dept. 1 AND one person from Dept. 2 AND one person from Dept. 4, OR
• One person from Dept. 1 AND one person from Dept. 3 AND one person from Dept. 4, OR
• One person from Dept. 2 AND one person from Dept. 3 AND one person from Dept. 4.
The number of ways to choose a person from a department equals the number of people in the department.
Until you become comfortable using the Rules of Sum and Product, look for "and" and "or" in what you do. This is an example of the divide and conquer tactic: break the problem into parts and work on each piece separately. Here the first part is getting a phrasing with "ands" and "ors;" the second part is calculating each of the individual pieces; and the third part is applying the Rules of Sum and Product.
Example 1.6 Palindromes A palindrome is a list that reads the same from right to left as it does from left to right. For example, ignoring capitalization, punctuation and spaces, "Madam I'm Adam." becomes the palindrome madamimadam.
How many k -long palindromes can be formed from an n -set? The first [k/2] list elements are arbitrary and the remaining elements are determined.a Thus the answer is n[k/2].
Imagine a necklace of beads with a clasp. How many k-bead necklaces can be formed if we are given n different colors of round beads. When the necklace is worn we can tell the end of the necklace because of the clasp, but we can't distinguish distinguish a left end versus a right end. We can think of this as k-long lists where we consider two lists the same if one can be obtained from the other by reversing the list. If a list is a palindrome, it contributes one to the count. If a list is not a palindrome, the list and its reversal together contribute one to the count.
(Continues...)
Excerpted from Foundations of Combinatorics with Applications by Edward A. Bender, S. Gill Williamson. Copyright © 2006 Edward A. Bender and S. Gill Williamson. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
PrefacePart I Counting and Listing
Preliminary Reading
1 Basic Counting
Introduction
1.1 Lists with Repetitions Allowed
Using the Rules of Sum and Product
Exercises
1.2 Lists with Repetitions Forbidden
Exercises
1.3 Sets
Error Correcting Codes
Exercises
1.4 Recursions
Exercises
1.5 Multisets
Exercises
Notes and References
2 Functions
Introduction
2.1 Some Basic Terminology
Terminology for Sets
What are Functions?
Exercises
2.2 Permutations
Exercises
2.3 Other Combinatorial Aspects of Functions
Monotonic Functions and Unordered Lists
Image and Coimage
The Pigeonhole Principle
Exercises
2.4 Boolean Functions
Exercises
Notes and References
3 Decision Trees
Introduction
3.1 Basic Concepts of Decision Trees
Exercises
3.2 Ranking and Unranking
Calculating RANK
Calculating UNRANK
Gray Codes
Exercises
3.3 Backtracking
Exercises
Notes and References
4 Sieving Methods
Introduction
Structures Lacking Things
Structures with Symmetries
4.1 The Principle of Inclusion and Exclusion
Exercises
Bonferroni's Inequalities
Partially Ordered Sets
Exercises
4.2 Listing Structures with Symmetries
Exercises
4.3 Counting Structures with Symmetries
Proofs
Exercises
Notes and References
Part II Graphs
5 Basic Concepts in Graph Theory
Introduction
5.1 What is a Graph?
Exercises
5.2 Equivalence Relations and Unlabeled Graphs
Exercises
5.3 Paths and Subgraphs
Exercises
5.4 Trees
Exercises
5.5 Directed Graphs (Digraphs)
Exercises
5.6 Computer Representations of Graphs
Exercises
Notes and References
6 A Sampler of Graph Topics
Introduction
6.1 Spanning Trees
Minimum Weight Spanning Trees
Lineal Spanning Trees
Exercises
6.2 Coloring Graphs
Exercises
6.3 Planar Graphs
Euler's Relation
Exercises
The Five Color Theorem
Exercises
Algorithmic Questions
Exercises
6.4 Flows in Networks
The Concepts
An Algorithm for Constructing a Maximum Flow
Exercises
Cut Partitions and Cut Sets
Exercises
6.5 Probability and Simple Graps
Exercises
6.6 Finite State Machines
Turing Machines
Finite State Machines and Digraphs
Exercises
Notes and References
Part III Recursion
7 Induction and Recursion
Introduction
7.1 Inductive Proofs and Recursive Equations
Exercises
7.2 Thinking Recursively
Exercises
7.3 Recursive Algorithms
Obtaining Information: Merge Sorting
Local Descriptions
Computer Implementation
Exercises
7.4 Divide and Conquer
Exercises
Notes and References
8 Sorting Theory
Introduction
8.1 Limits on Speed
Motivation and Proof of the Theorem
Exercises
8.2 Software Sorts
Binary Insertion Sort
Bucket Sort
Merge Sorts
Quicksort
Heapsort
Exercises
8.3 Sorting Networks
8.3.1 Speed and Cost
Parallelism
How Fast Can a Network Be?
How Cheap Can a Network Be?
Exercises
8.3.2 Proving That a Network Sorts
The Batcher Sort
Exercises
Notes and References
9 Rooted Plane Trees
Introduction
9.1 Traversing Trees
Depth First Traversals
Exercises
9.2 Grammars and RP-Trees
Exercises
9.3 Unlabeled Full Binary RP-Trees
Exercises
Notes and References
Part IV Generating Functions
10 Ordinary Generating Functions
Introduction
10.1 What are Generating Functions?
Exercises
10.2 Solving a Single Recursion
Exercises
10.3 Manipulating Generating Functions
Obtaining Recursions
Derivatives, Averages and Probability
Exercises
10.4 The Rules of Sum and Product
Exercises
Notes and References
11 Generating Function Topics
Introduction
11.1 Systems of Recursions
Exercises
11.2 Exponential Generating Functions
The Exponential Formula
Exercises
11.3 Symmetries and Pólya's Theorem
Exercises
11.4 Asymptotic Estimates
Recursions
Sums of Positive Terms
Generating Functions
Exercises
Notes and References
Appendix A Induction
Exercises
Appendix B Rates of Growth and Analysis of Algorithms
B.1 The Basic Functions
Exercises