222
Sets, Combinatorics, and Probability
This is an example of a counting problem; you want to count the number of elements in a certain collection or set—the set of all subscribers with access to all
three systems. A formula that easily solves this counting problem is developed in
Section 4.3.
Set theory is one of the cornerstones of mathematics. Many concepts in mathematics and computer science can be conveniently expressed in the language of
sets. Operations can be performed on sets to generate new sets. Although most sets
of interest to computer scientists are finite or countable, there are sets with so many
members that they cannot be enumerated. Set theory is discussed in Section 4.1.
It is often of interest to count the number of elements in a finite set. This may
not be a trivial task. Section 4.2 provides some ground rules for counting the number of elements in a set consisting of the outcomes of an event. Counting the elements in such a set can be made manageable by breaking the event down into a sequence of subevents or into disjoint subevents that have no outcomes in common.
Some specialized counting principles appear in Section 4.3. Section 4.4 provides
formulas for counting the number of ways to arrange objects in a set and to select
objects from a set, as well as algorithms to generate all the possible arrangements
or selections. Section 4.5 discusses the binomial theorem, an algebraic result that
can also be viewed as a consequence of the counting formulas. Finally, Section 4.6
extends “counting” to the more general idea of probability.
S e c t i o n 4 . 1 SetS
Definitions are important in any science because they contribute to precise communication. However, if we look up a word in the dictionary, the definition is expressed
using other words, which are defined using still other words, and so on. Thus, we
have to have a starting point for definitions where the meaning is taken to be understood; our starting point in this discussion will be the idea of a set, a term that we
will not formally define. Instead, we will simply use the intuitive idea that a set is a
collection of objects. Usually all of the objects in a set share some common property
(aside from that of belonging to the same set!); any object that has the property is a
member of the set, and any object that does not have the property is not a member.
(This is consistent with our use of the word set in Section 3.1, where we talked about
the set of propositional well-formed formulas, the set of all strings of symbols from
a finite alphabet, and the set of identifiers in some programming language.)
Notation
We use capital letters to denote sets and the symbol [ to denote membership
in a set. Thus a [ A means that object a is a member, or element, of set A, and
b o A means that object b is not an element of set A. Braces are used to indicate
a set.
example 1
If A = {violet, chartreuse, burnt umber}, then chartreuse [ A and magenta o A.
No ordering is imposed on the elements in a set; therefore {violet, chartreuse,
burnt umber} is the same as {chartreuse, burnt umber, violet}. Also, each element
of a set is listed only once; it is redundant to list it again.
Sets, Combinatorics, and Probability
This is an example of a counting problem; you want to count the number of elements in a certain collection or set—the set of all subscribers with access to all
three systems. A formula that easily solves this counting problem is developed in
Section 4.3.
Set theory is one of the cornerstones of mathematics. Many concepts in mathematics and computer science can be conveniently expressed in the language of
sets. Operations can be performed on sets to generate new sets. Although most sets
of interest to computer scientists are finite or countable, there are sets with so many
members that they cannot be enumerated. Set theory is discussed in Section 4.1.
It is often of interest to count the number of elements in a finite set. This may
not be a trivial task. Section 4.2 provides some ground rules for counting the number of elements in a set consisting of the outcomes of an event. Counting the elements in such a set can be made manageable by breaking the event down into a sequence of subevents or into disjoint subevents that have no outcomes in common.
Some specialized counting principles appear in Section 4.3. Section 4.4 provides
formulas for counting the number of ways to arrange objects in a set and to select
objects from a set, as well as algorithms to generate all the possible arrangements
or selections. Section 4.5 discusses the binomial theorem, an algebraic result that
can also be viewed as a consequence of the counting formulas. Finally, Section 4.6
extends “counting” to the more general idea of probability.
S e c t i o n 4 . 1 SetS
Definitions are important in any science because they contribute to precise communication. However, if we look up a word in the dictionary, the definition is expressed
using other words, which are defined using still other words, and so on. Thus, we
have to have a starting point for definitions where the meaning is taken to be understood; our starting point in this discussion will be the idea of a set, a term that we
will not formally define. Instead, we will simply use the intuitive idea that a set is a
collection of objects. Usually all of the objects in a set share some common property
(aside from that of belonging to the same set!); any object that has the property is a
member of the set, and any object that does not have the property is not a member.
(This is consistent with our use of the word set in Section 3.1, where we talked about
the set of propositional well-formed formulas, the set of all strings of symbols from
a finite alphabet, and the set of identifiers in some programming language.)
Notation
We use capital letters to denote sets and the symbol [ to denote membership
in a set. Thus a [ A means that object a is a member, or element, of set A, and
b o A means that object b is not an element of set A. Braces are used to indicate
a set.
example 1
If A = {violet, chartreuse, burnt umber}, then chartreuse [ A and magenta o A.
No ordering is imposed on the elements in a set; therefore {violet, chartreuse,
burnt umber} is the same as {chartreuse, burnt umber, violet}. Also, each element
of a set is listed only once; it is redundant to list it again.