]>
Suppose that is a finite set. If then the cardinality of is the number of elements in , and is denoted . The function is called counting measure. Counting measure plays a fundamental role in discrete probability structures, and particularly those that involve sampling from a finite set. The set is typically very large, hence efficient counting methods are essential. The first combinatorial problem is attributed to the Greek mathematician Xenocrates.
In many cases, a set of objects can be counted by establishing a one-to-one correspondence between the given set and some other set. Naturally, the two sets have the same number of elements, but for some reason, the second set may be easier to count.
The addition rule of combinatorics is simply the additivity axiom of counting measure. If is a collection of disjoint subsets of then
The counting rules in this subsection are simple consequences of the addition rule.
Show that .
Hint: and are disjoint and their union is .
Show that .
Hint: and are disjoint and their union is .
Show that if then .
Hint: Apply the difference rule and note that
Show that if then .
Thus, is an increasing function, relative to the subset partial order on , and the ordinary order on .
This subsection gives two inequalities that are useful for obtaining bounds on the number of elements in a set.
Suppose that is a a finite collection of subsets of . Prove Boole's inequality (named after George Boole):
Intuitively, Boole's inequality holds because parts of the union have been counted more than once in the expression on the right.
Suppose that is a finite collection of subsets of . Prove Bonferroni's inequality (named after Carlo Bonferroni):
Hint: Apply Boole's inequality to and use DeMorgan's law.
Show that
Show that
Hint: Use the inclusion-exclusion rule for two sets. You will use this rule three times.
Exercise 7 and Exercise 8 can be generalized to a union of sets; the generalization is known as the inclusion-exclusion formula.
Suppose that is a collection of subsets of where . Show that
The general Bonferroni inequalities, named again for Carlo Bonferroni, state that if sum on the right is truncated after terms (), then the truncated sum is an upper bound for the cardinality of the union if is odd (so that the last term has a positive sign) and is a lower bound for the cardinality of the union if is even (so that the last terms has a negative sign).
The multiplication rule of combinatorics is based on the formulation of a procedure (or algorithm) that generates the objects to be counted. Specifically, suppose that the procedure consists of steps, performed sequentially, and that for each , step can be performed in ways regardless of the choices made on the previous steps. Then the number of ways to perform the entire algorithm (and hence the number of objects) is .
The key to a successful application of the multiplication rule to a counting problem is the clear formulation of an algorithm that generates the objects being counted, so that each object is generated once and only once. That is, we must neither over-count nor under-count.
The first two exercises below give equivalent formulations of the multiplication principle.
Suppose that is a set of sequences of length , and that we denote a generic element of by . Suppose that for each , has different values, regardless of the values of the previous coordinates. Show that
Suppose that is an ordered tree with depth and that each vertex at level has children for . Show that the number of vertices at level is .
Suppose that is a set with elements for . Show that
Show that if is a set with elements, then has elements.
Show that the number of ordered samples of size that can be chosen with replacement from a population of objects is .
Show that the number of functions from a set of elements into a set of elements is .
Hint: To construct , there are choices for for each .
Recall that the set of functions from a set into a set (regardless of whether the sets are finite or infinite) is denoted . The result in the previous exercise is motivation for this notation.
Elements of are sometimes called bit strings of length . Show that the number of such strings is .
Suppose that is a set with elements. Show that there are subsets of .
Hint: To construct , decide whether or for each .
Suppose that is a collection of subsets of a set . Show that there are different (in general) sets that can be constructed from the given sets, using the operations of union, intersection, and complement. These sets form the algebra generated by the given sets.
In the Venn diagram applet, observe the diagram of each of the 16 sets that can be constructed from and .
Suppose that is a set with elements and that is a subset of with elements. Show that the number of subsets of that contain is .
A license number consists of two letters (uppercase) followed by five digits. How many different license numbers are there?
Suppose that a Personal Identification Number (PIN) is a four-symbol code word in which each entry is either a letter (uppercase) or a digit. How many PINs are there?
In the board game Clue, Mr. Boddy has been murdered. There are 6 suspects, 6 possible weapons, and 9 possible rooms for the murder.
An experiment consists of rolling a fair die, drawing a card from a standard deck, and tossing a fair coin. How many outcomes are there?
Suppose that 10 persons are chosen and their birthdays recorded. How many possible outcomes are there?
In the card game Set, each card has 4 properties: number (one, two, or three), shape (diamond, oval, or squiggle), color (red, blue, or green), and shading (solid, open, or stripped). The deck has one card of each (number, shape, color, shading) configuration. A set in the game is defined as a set of three cards which, for each property, the cards are either all the same or all different.
A fair coin is tossed 10 times and the sequence of scores recorded.
A string of lights has 20 bulbs, each of which may be good or defective. How many configurations are there?
The die-coin experiment consists of rolling a die and then tossing a coin the number of times shown on the die. The sequence of coin results is recorded.
Run the die-coin experiment until exactly 2 heads occurs.
Suppose that a sandwich at a restaurant consists of bread, meat, cheese, and various toppings. There are 4 different types of bread (select one), 3 different types of meat (select one), 5 different types of cheese (select one), and 10 different toppings (select any). How many sandwiches are there?
The Galton Board, named after Francis Galton, is a triangular array of pegs. Galton, apparently too modest to name the device after himself, called it a quincunx from the Latin word for five twelfths (go figure). The rows are numbered, from the top down, by . Row has pegs that are labeled, from left to right by . Thus, a peg can be uniquely identified by an ordered pair where is the row number and is the peg number in that row.
A ball is dropped onto the top peg of the Galton board. In general, when the ball hits peg , it either bounces to the left to peg or to the right to peg The sequence of pegs that the ball hits is a path in the Galton board.
Show that there is a one-to-one correspondence between each pair of the following three collections:
Thus, from the previous exercise, each of these collections has elements.
Open the Galton board applet.