Combinatorics (eBook)
John Wiley & Sons (Verlag)
978-1-118-40748-6 (ISBN)
Bridges combinatorics and probability and uniquely includes detailed formulas and proofs to promote mathematical thinking
Combinatorics: An Introduction introduces readers to counting combinatorics, offers examples that feature unique approaches and ideas, and presents case-by-case methods for solving problems.
Detailing how combinatorial problems arise in many areas of pure mathematics, most notably in algebra, probability theory, topology, and geometry, this book provides discussion on logic and paradoxes; sets and set notations; power sets and their cardinality; Venn diagrams; the multiplication principal; and permutations, combinations, and problems combining the multiplication principal. Additional features of this enlightening introduction include:
- Worked examples, proofs, and exercises in every chapter
- Detailed explanations of formulas to promote fundamental understanding
- Promotion of mathematical thinking by examining presented ideas and seeing proofs before reaching conclusions
- Elementary applications that do not advance beyond the use of Venn diagrams, the inclusion/exclusion formula, the multiplication principal, permutations, and combinations
Combinatorics: An Introduction is an excellent book for discrete and finite mathematics courses at the upper-undergraduate level. This book is also ideal for readers who wish to better understand the various applications of elementary combinatorics.
THEODORE G. FATICONI, PhD, is Professor in the Department of Mathematics at Fordham University. His professional experience includes forty research papers in peer-reviewed journals and forty lectures on his research to colleagues.
THEODORE G. FATICONI, PhD, is Professor in the Department of Mathematics at Fordham University. His professional experience includes forty research papers in peer-reviewed journals and forty lectures on his research to colleagues.
Preface xiii
1 Logic 1
1.1 Formal Logic 1
1.2 Basic Logical Strategies 6
1.3 The Direct Argument 10
1.4 More Argument Forms 12
1.5 Proof By Contradiction 15
1.6 Exercises 23
2 Sets 25
2.1 Set Notation 25
2.2 Predicates 26
2.3 Subsets 28
2.4 Union and Intersection 30
2.5 Exercises 32
3 Venn Diagrams 35
3.1 Inclusion/Exclusion Principle 35
3.2 Two Circle Venn Diagrams 37
3.3 Three Square Venn Diagrams 42
3.4 Exercises 50
4 Multiplication Principle 55
4.1 What is the Principle? 55
4.2 Exercises 60
5 Permutations 63
5.1 Some Special Numbers 64
5.2 Permutations Problems 65
5.3 Exercises 68
6 Combinations 69
6.1 Some Special Numbers 69
6.2 Combination Problems 70
6.3 Exercises 74
7 Problems Combining Techniques 77
7.1 Significant Order 77
7.2 Order Not Significant 78
7.3 Exercises 83
8 Arrangement Problems 85
8.1 Examples of Arrangements 86
8.2 Exercises 91
9 At Least, At Most, and Or 93
9.1 Counting With Or 93
9.2 At Least, At Most 98
9.3 Exercises 102
10 Complement Counting 103
10.1 The Complement Formula 103
10.2 A New View of ?At Least? 105
10.3 Exercises 109
11 Advanced Permutations 111
11.1 Venn Diagrams and Permutations 111
11.2 Exercises 120
12 Advanced Combinations 125
12.1 Venn Diagrams and Combinations 125
12.2 Exercises 131
13 Poker and Counting 133
13.1 Warm Up Problems 133
13.2 Poker Hands 135
13.3 Jacks or Better 141
13.4 Exercises 143
14 Advanced Counting 145
14.1 Indistinguishable Objects 145
14.2 Circular Permutations 148
14.3 Bracelets 151
14.4 Exercises 155
15 Algebra and Counting 157
15.1 The Binomial Theorem 157
15.2 Identities 160
15.3 Exercises 165
16 Derangements 167
16.1 Fixed Point Theorems 168
16.2 His Own Coat 173
16.3 Exercises 174
17 Probability Vocabulary 175
17.1 Vocabulary 175
18 Equally Likely Outcomes 181
18.1 Exercises 188
19 Probability Trees 189
19.1 Tree Diagrams 189
19.2 Exercises 198
20 Independent Events 199
20.1 Independence 199
20.2 Logical Consequences of Influence 202
20.3 Exercises 206
21 Sequences and Probability 209
21.1 Sequences of Events 209
21.2 Exercises 215
22 Conditional Probability 217
22.1 What Does Conditional Mean? 217
22.2 Exercises 223
23 Bayes? Theorem 225
23.1 The Theorem 225
23.2 Exercises 230
24 Statistics 231
24.1 Introduction 231
24.2 Probability is not Statistics 231
24.3 Conversational Probability 232
24.4 Conditional Statistics 239
24.5 The Mean 241
24.6 Median 242
24.7 Randomness 244
25 Linear Programming 249
25.1 Continuous Variables 249
25.2 Discrete Variables 254
25.3 Incorrectly Applied Rules 258
26 Subjective Truth 261
Bibliography 267
Index 269
Chapter 2
Sets
In this book, we will count the number of elements or objects that have a certain given property. We will constantly be answering the question Just how many elements are there like that? We will only count finite collections, but these finite collections can be difficult to count the traditional way. For example, in how many ways can you arrange six people in a row? The answer is not easily obtained by listing all of the arrangements or by simply making each of the arrangements with six people. Thus, we will have to find a different way to count these arrangements. Here is another one. How many pizzas can you make with exactly five different toppings if there are no repeated toppings and if there are ten toppings to choose from? These counting problems can become much more difficult with just a few changes in the wording. For example, consider the following counting problem. How many pizzas can you make with at most five different toppings if there are no repeated toppings and if there are ten toppings to choose from? These are typical of the counting problems that are our goal.
2.1 Set Notation
The language of mathematics is based on a grammar called Set Theory. This grammar gives us a brief and simple way to write down some very complex mathematical ideas. A set is a collection A such that given an object x, either x is in A, or x is not in A, but not both. As long as we can teil that any object is in A or not in A then A is a set. The collections we consider in this book will always be sets. The objects in A are called elements.
The elements of a set are sometimes listed between set braces, { }. For example, the following sets are described by listing the elements in them:
The first set has elements 1 and 2 but no other elements. Observe that book3 is an element in the third set but not an element of the second set. Also, Algebra is not an element of the third set unless it is book1, book2, book3, or book4.
An important set is called the empty set. This is the set that has no elements. In this book, the empty set is written in the following ways:
Thus, given an object x we know with certainty that x is not in . In terms of our counting theme, the empty set is the set with no elements, or 0 elements. For example, the set of cards in a Standard deck of 52 that are labeled by 11 make up the set {}. There are no such cards.
2.2 Predicates
The problems we are working on take place in a finite set called a universal set or a universe. This universe changes from problem to problem. For instance, if we are counting the number of red, white, and blue flags in the world, then this problem takes place in a universe of flags of the world. This set is finite. There are only a finite number of flags in this world. The set of all numbers that appear in a Standard deck of 52 cards is finite. In fact, we can list its nine elements as {2,3,4,5,6,7,8,9,10}.
Let us keep in mind that this universe that we are defining is a finite set and that it changes from problem to problem. These universes will never be the universe we live in since our surroundings are infinite once you count the abstract ideas that make up our thoughts.
The most effective means of listing a set is called a predicate. A predicate is a partial sentence that describes objects.
EXAMPLE 2.2.1 1. red, white, and blue flags is a predicate describing flags.
2. Positive even whole numbers less than 12 is a predicate describing the set {2,4,6,8,10}.
3. The predicate x2 – 4 = 0 can be used to describe the set {–2,2} as follows.
Read the symbol | as such that or as with the property that. Then x2 – 4 = 0 is a perfectly good predicate to describe the objects in a set.
4. Consider {x | x is a person on Earth}. The predicate is x is a person on Earth. This is a set that in this Computer age could be given as a finite complete list of people on the Earth, but which should not be given as that large list in this book.
5. There is also the predicate is a book, which describes {x | x is a book}.
Let A be a set in a universal set . The complement of A is the set
This is the set of elements that are not in A. This is what is outside of A in . Think of A as a circle, and then A′ is what is outside that circle.
EXAMPLE 2.2.2 Let = {0,1,2,3,4,5,6,7,8,9,10}.
1. Let A = {0,1,2,3,4,5}. Then A′ = {6,7,8,9,10}. These are the numbers in that are not in A.
2. Let B = {1,3,5,7,9}. Then B′ = {0,2,4,6,8,10}, the numbers not in B.
3. Let C be the set of even numbers in . Then C′ = {1,3,5,7,9} which is the set of odd numbers in .
4. Let be the set of children of age at most 6 years, and let B = the set of boys of age at most 6 years. Then B′ is the set of children of age at most 6 years that are not boys. These are the girls of age at most 6 years.
There are two complements that should be remembered. They come up often. We will assume the existence of a finite universal set in all that follows. Since contains everything being considered, no x satisfies x ∉ . Thus, the complement of is empty.
Since nothing is in , x ∉ for each x ∈ . Hence, the complement of is . In other words,
2.3 Subsets
When one set is contained in another set we say that the smaller is a subset of the larger. This is an intuitive way of thinking of subsets, but we will need a more precise definition of subset. Let A and B be sets. We say that B is a subset of A, and we write B ⊂ A, if
Given x ∈ B then x ∈ A.
When paraphrased, we say that B ⊂ A if each element of B is an element of A. One more way of saying B ⊂ A is that if we are given an x ∈ B then we can show that x ∈ A.
EXAMPLE 2.3.1 Let = the set of whole numbers between 0 and 25 inclusive.
1. {1,2,3} ⊂ {1,2,3,4,5}. This is True because evidently 1, 2, and 3 are elements of {1,2,3,4,5}.
2. {1,3} ⊂ {x ∈ | x is an odd number}. This is True because evidently 1 and 3 are odd numbers in .
3. Let B = the set of positive whole numbers between 1 and 25 inclusive. Each element of B is a whole number between 0 and 25 inclusive. Hence B ⊂ .
There are two examples of subsets that we should always be aware of.
Let A be a set. Evidently each element of A is an element of A. This is just mathematical double talk. Thus we conclude that
A ⊂ A.
Now consider the other end of the problem. Let A be a set. We will argue that
⊂ A.
To see this, suppose to the contrary that ⊄ A. This will lead us to a False statement. By the definition of subset, there is an element of that is not in A. But that means that has an element, which is not True of the empty set. This mathematical mistake, called a contradiction, shows us that we began with a Falsehood. You see, if we make no mistakes then a Truth leads to a Truth. The assumption that ⊄ A leads us to the untruth that contains an element. Thus it must be that we did proceed from a False premise. Hence ⊂ A.
We will have need of a list of all subsets of a set. Some counting problems use them all. Let A be a set. The set of all subsets of A is called the power set of A and it is denoted by
(A) = the set of all subsets of A.
EXAMPLE 2.3.2 Let A = {} = . Then A has exactly 0 elements, so that any subset of A has exactly 0 elements. The only set with 0 elements is . Then is the only subset of A. So (A) = {}.
EXAMPLE 2.3.3 Let A = {a}. Then A has exactly one element so that every subset of A will have at most 1 element. That is, they will have exactly 1 element or no elements. These subsets are {} which has no elements, and {a} which has exactly 1 element. So (A) = {,{a}}.
EXAMPLE 2.3.4 A = {a,b}. Then A has exactly 2 elements. Its subsets will then have exactly 2, or exactly 1, or no elements at all. The subset with no elements is {}, the subsets with exactly 1 element are {a}, {b}, and the only subset with exactly 2 elements is {a, b}. So (A) = {, {a}, {b}, {a, b}}.
2.4 Union and Intersection
In this section we study several important operations on sets. The union of sets A and B is
A ∪ B = {x | x ∈...
| Erscheint lt. Verlag | 21.8.2014 |
|---|---|
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
| Technik | |
| Schlagworte | combinatorics • combinatorics, probability, mathematics, statistics, finite mathematics, discrete math • Computer Science • Discrete Mathematics • Diskrete Mathematik • Informatik • Kombinatorik • Mathematics • Mathematik |
| ISBN-10 | 1-118-40748-2 / 1118407482 |
| ISBN-13 | 978-1-118-40748-6 / 9781118407486 |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
EPUB (Adobe DRM)Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: EPUB (Electronic Publication)
EPUB ist ein offener Standard für eBooks und eignet sich besonders zur Darstellung von Belletristik und Sachbüchern. Der Fließtext wird dynamisch an die Display- und Schriftgröße angepasst. Auch für mobile Lesegeräte ist EPUB daher gut geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
