 Shopping Bag ( 0 items )

All (8) from $31.95

New (5) from $34.42

Used (3) from $31.95
More About This Textbook
Overview
Editorial Reviews
Ruth Michler
Combinatorics: A Problem Oriented Approach is a book on Combinatorics that mainly focuses on counting problems and generating functions. By restricting himself to an accomplishable goal, without attempting to be encyclopedic, the author has created a wellfocused, digestible treatise on the subject. ...The choice of topics is excellent. This book is one of the few that treats the PólyaRedfield counting method and recurrence relations.—MAA Online
Product Details
Related Subjects
Read an Excerpt
Strings
A string is a list, or sequence, of elements in a particular order. For the time being, we will concern ourselves with finite strings only.
Examples (1,3,0,112) is a string of integers. (X,Q,R,Z,X) is a string of letters from the usual alphabet {A,B, C,...,Z}
Notice that the same element can appear more than once in a string.
When no confusion results, we will usually leave out the parentshes and commas in the representation of a string. The latter example above can be written more easily as XQRZX. This fiveletter string can also be though of as a "word" that uses letters from the alphabet {A,...,Z}. The terms string, sequence, and word will be used interchangeably.
Example Any positive integer can be represented by a string of digits from the set {0,1,2,...,9}. This is the usual base 10 representation. In the binary system, any positive integer is represented by a string of digits (called bits in this case) from the set {0,1}.
Counting Strings
Continuing with the example above, consider all of the integers from 0 to 999. Each one of these can these can be represented by a 3digit string using digits from 0 to 9; 0 is represented as 000, 1 as 001, etc. We know that there are 1000 of these integers (0 to 999), and the same result can be obtained can be obtained by counting 3digit strings: The first digit can be selected in 10 different ways, and for each of 100, easy to select the first two digits. Finally, each of these 100 choice can be combined with one of the 10 choices for the third digit. The result is 1000 different threedigit strings.
Here are some problems for you to try.
A1 By counting choices as in the examples above, determine the number of different fivebit strings, which are strings of 0s and 1s each consisting of five bits. What does this have to do with the binary representation of integers?
A2 Find the number of five letter words using letters of the alphabet {A,B,C,...,Z}
These are instances of a more general problem, which can be summarized as follows.
Standard Problem #1
Find the number of strings of a given length that use elements from a given set.
The length of a string means the number of terms, or elements in the string. The answer to Standard Problem #1 is nk, where k is the length of the string and n is the number of elements in the set from which the terms are selected.
Next, we look at some variations on this standard problem. Suppose we want to count threeletter words that use letters from the usual alphabet, but with the condition that no letter can occur more than once in each word. Again, A2 there are 26 choice for the first letter. For each such choice there are only 25 letters that can be placed in the second position, because the letter used in the first position cannot be repeated. This 25o26 ways to place two different letters in the first two positions, and each of these choices can be combined with one of the remaining 24 letters in the third positions. The resulting number of threeletter words is 26o25o24.
A3 Find the number of five digit strings using digits from {0,1,21...,9} if no digit appears more than once in the string.
Table of Contents
Part I Basics
Section A: Strings
Section B: Combinations
Section C: Distributions
Section D: Partitions
Part II Special Counting Methods
Section E: Inclusion and Exclusion
Section F: Recurrence Relations
Section G: Generating Functions
Section H: The PolyaRedfield Mathod
List of Standard Problems
Dependence of Problems
Answers to Selected Problems
Index