A) = #(A) / #(S) for A 
S.Virtual Laboratories > Combinatorics > [1] 2 3 4 5
If a random variable X for an experiment is uniformly distributed on a finite subset S, then the probability distribution of X is proportional to counting measure:
P(X A) = #(A) / #(S) for A S.
Such random variables arise frequently in many different experiments, particularly those that can be interpreted as sampling from a finite set. The set S 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 A1, A2, ..., An are disjoint subsets of a finite set S then
#(A1 
A2 ··· An) = #(A1) + #(A2)
+ ··· + #(An)
Recall also that the basic rules of probability have analogues for counting measure. The most important of these are given in the following exercises:
1.
Show that #(Ac) = #(S) - #(A)
2.
Show that #(B 
Ac)
= #(B) - #(A
B).
3.
Show that if A B
then #(B Ac)
= #(B) - #(A).
4.
Show that #(A B) = #(A) + #(B) - #(A
B).
5.
Show that
#(A B C) = #(A) + #(B) + #(C) - #(A
B) - #(A
C) - #(B
C) + #(A
B
C).
Exercises 11 and 12 can be generalized to a union of n events Ai, i = 1, 2, ...n; the generalization is known as the inclusion-exclusion formula. To simplify the formulation, let N denote the index set: I = {1, 2, ..., n} and define
nJ = # [
j
in J Aj] for J
N,
mk = 
{J:
#(J) = k} nJ for k N.
6. Show that
# [
i
= 1, ..., n Ai] = k
= 1, ..., n (-1)k - 1
mk.
The general Bonferroni inequalities state that if sum on the right is truncated after k terms (k < n), then the truncated sum is an upper bound for the cardinality of the union if k is odd (so that the last term has a + sign) and is a lower bound for the cardinality of the union if k is even (so that the last terms as a - 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 k steps, performed sequentially, and that for each j, step j can be performed in nj 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
n1 n2 ··· nk.
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 undercount.
The first two exercises below give equivalent formulations of the multiplication principle.
7.
Suppose that S is a set of sequences of length k, and and that we denote
the elements of S by
(x1, x2, ..., xk)
Suppose that for each j, xj has nj different values, regardless of the values of the previous coordinates. Show that the cardinality of A is
n1 n2 ··· nk.
8.
Suppose that T is an ordered tree with depth k and that each vertex at
level i - 1 has ni children for i = 1, 2, ..., k.
Show that the number of vertices at level k is
n1 n2 ··· nk.
9.
A license number consists of two letters (uppercase) followed by five digits.
10.
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.
11. In the board game Clue, Mr. Boddy has been
murdered. There are
6 suspects, 6 possible weapons, and 9 possible rooms for the murder.
12.
Suppose that that Si is a set with ni elements
for i = 1, 2, ..., k. Show that
#(S1 × S2 × ··· × Sn ) = n1 n2 ··· nk.
In particular, if Si is the sample space of experiment Ei, then this product gives the number of outcomes in the compound experiment that consists of performing E1, ..., Ek in sequence.
13.
An experiment consists of rolling a fair die, drawing a card from a standard deck, and tossing
a fair coin.
14.
Show that if S is a set with m elements, then Sn has
mn elements.
In particular, if a basic experiment has m outcomes, then the compound experiment that consists of n replications of the basic experiment has mn outcomes.
15.
A fair die is rolled 5 times and the sequence of scores recorded.
16.
Show that the number of ordered samples of size n that can be chosen with
replacement from a population of m objects is mn.
17.
Suppose that 10 persons are chosen at random and their birthdays recorded.
18.
Show that the number of functions from a set A of n elements into a set B
of m elements is mn.
Elements of {0,1}n are sometimes called bit strings of length n. The outcome of the experiment that consists of n Bernoulli trials is a bit string of length n.
19.
Show that the number of bit strings of length n is 2n.
20.
A fair coin is tossed 10 times.
21.
A string of lights has 20 bulbs, each of which may be good or defective. How many
configurations are there?
22. 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.
23. Run the die-coin
experiment 1000 times, updating every 10 runs. Compare the empirical
probability that all coin tosses are heads with the true probability in the
previous exercise.
The Galton Board, named after Francis Galton, is a triangular array of pegs (Galton called the device a quincunx). The rows are numbered, from the top down, by 0, 1, ... Row k has k + 1 pegs that are labeled, from left to right by 0, 1, ..., i. Thus, a peg can be uniquely identified by an ordered pair (i, j) where i is the row number and j is the peg number in that row.
A ball is dropped onto the top peg (0, 0) of the Galton board. In general, when the ball hits peg (i, j), it either bounces to the left to peg (i + 1, j) or to the right to peg (i + 1, j + 1). The sequence of pegs that the ball hits is a path in the Galton board.
24.
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 2n elements. In particular, an experiment with n outcomes has 2n events.
25.
In the Galton board
game, move the ball from (0, 0) to (10, 6) along a path of your
choice. Note the corresponding bit string and subset.
26.
In the Galton board
game, generate the bit string 011100101. Note the corresponding subset
and path.
27.
In the Galton board
game, generate the subset {2, 4, 5, 9, 12}. Note the corresponding bit
string and path.
28.
In the Galton board
game, generate all paths from (0, 0) to (4, 2). How many paths are
there?
29. Suppose that A1,
A2, ..., Ak are events in a random
experiment. Show that there are 2^(2k) different (in general) events that can be constructed from the k given
events, using the operations of union, intersection, and complement. The
following steps show how:
B2
···
Bk where Bi is either Ai
or Aic for each i.
30. In the Venn diagram
applet, observe the diagram of each of the 16
events that can be constructed from A and B.
31. Suppose that S
is a set with n elements and that A is a subset of S with k
elements. If a random subset of S is chosen, find the probability that it
contains A.
The most basic applications of the multiplication principle are to permutations and combinations. It is also interesting to note that the multiplication principle is the counting measure analogue of the multiplication rule for conditional probability. Combinatorial methods play a fundamental role in chapter on Finite Sampling Models.