Counting Sample Points

• Combinatorics - counting rules in set theory. This provides the idea of the principles of enumeration, counting sample points in the sample space.
• When an experiment is performed, the statistician want to evaluate the chance associated with the occurrence of certain events.
• In many cases we can evaluate the probability by counting the number of points in the sample space.
• Theorem 2.1 (multiplication rule):
  
  
• The multiplication rule is the fundamental principle of counting sample points.

• Example 2.14: Home buyers are offered
  • four exterior styling
  • three floor plans
• Since $n_1=4,n_2= 3$ and , a buyer must choose from
  $$n_1n_2=12$$
  possible homes

Figure 4: Tree diagram for Example 2.14.

• Theorem 2.2 (generalized multiplication rule):
  
• The multiplication rule can be extended to cover any number of operations.

• Example 2.16: How many even four-digit numbers can be formed from the digits 0, 1, 2, 5, 6, and 9 if each digit can be used only once?
• We consider the unit position by two parts, 0 or not 0.
  • If the units position is 0 $(n_1=1)$:
    • $n_2=5$ choices for the thousands positions,
    • $n_3=4$ choices for the hundreds positions,
    • $n_4=3$ choices for the tens positions.
    • a total of $n_1n_2n_3n_4= 60$ choices.
  • If the units position is not 0 $(n_1=2)$:
    • $n_2=4$ choices for the thousands positions,
    • $n_3=4$ choices for the hundreds positions,
    • $n_4=3$ choices for the tens positions.
    • a total of $n_1n_2n_3n_4= 96$ choices.
  • The total number of even four-digit numbers is 60 + 96 = 156

• Permutation: Definition 2.7
  
• An ordered arrangement of distinct objects. Consider the number of ways of filling $r$ boxes with $n$ objects.
• Theorem 2.3:
  
• Theorem 2.4:
  
• Example 2.17: In one year, three awards (research, teaching, and service) will be given for a class of 25 graduate students in a statistics department.
  • If each student can receive at most one award, how many possible selections are there?
  • Since the awards are distinguishable, it is a permutation problem.
  • The number of sample points is $_{25}P_3=\frac{25!}{22!}$

• Example 2.18: A president and a treasurer are to be chosen from a student club consisting of 50 people. How many different choices of officers are possible if
  • there are no restrictions; $_{50}P_2=\frac{50!}{48!}=2450$
  • $A$ will serve only if he is president;
    1. $A$ is selected as the president, which yields 49 possible outcomes; or
    2. Officers are selected from the remaining 49 people which has the number of choices $_{49}P_2$
    Therefore, the total number of choices is $49+_{49}P_2= 2401$.
  • $B$ and $C$ will serve together or not at all;
    1. The number of selections when $B$ and $C$ serve together is 2.
    2. The number of selections when both $B$ and $C$ are not chosen is $_{48}P_2$
    Therefore, the total number of choices in this situation is 2 + 2256 = 2258.
  • $D$ and $E$ will not serve together; $2*48+2*48+_{48}P_2$
    1. The number of selections when $D$ serves as officer but not $E$,
    2. The number of selections when $E$ serves as officer but not $D$
    3. The number of selections when both $D$ and $E$ are not chosen
    Therefore, the total number of choices is 2448. This problem also has another short solution: $_{50}P_2 -2$ (since $D$ and $E$ can only serve together in 2 ways).

• Permutations are used when we are sampling without replacement and order matters.
• Theorem 2.5:
  
• Permutations that occur by arranging objects in a circular are called circular permutations.
• Two circular permutations are not considered different unless corresponding objects in the two arrangements are preceded or followed by a different objects as we proceed in a clockwise direction.

• Theorem 2.6:
  
• Example 2.19: In a college football training session, the defensive coordinator needs to have 10 players standing in a row.
  • Among these 10 players, there are 1 freshman, 2 sophomores, 4 juniors, and 3 seniors, respectively.
  • How many different ways can they be arranged in a row if only their class level will be distinguished?
    $$\frac{10!}{1!2!3!4!}=12600$$

• Theorem 2.7:
  
• The order of the elements within each cell is of no importance.
• The intersection of any two cells is the empty set and the union of all cells gives the original set.
• Example 2.22: How many different letter arrangements can be made from the letters in the word of STATISTICS?
• We have total 10 letters, while letters S and T appear 3 times each, letter I appears twice, and letters A and C appear once each.
  $$\left( \begin{array}{c} 10 \\ 3,3,2,1,1\\ \end{array}\right)=\frac{10!}{3!3!2!1!1!}=50400$$

• Theorem 2.8:
  
• We might want to select $r$ objects from $n$ without regard to order.
• These selections are called combinations. Combinations are used when we are sampling without replacement and order does NOT matter.
• A combination is a partition with two cells,
  • the one containing $r$ objects selected
  • the one containing the $(n -r)$ objects that are left
• The number of such combinations,
  $$\left( \begin{array}{c} n \\ r,n-r \\ \end{array}\right... ...rrow \left( \begin{array}{c} n \\ r \\ \end{array}\right)$$

• The number of permutations of $n$ distinct objects is $n!$.
• The number of permutations of $n$ distinct objects taken $r$ at a time is
  $$P(n,r)=\frac{n!}{(n-r)!}$$

• The number of permutations of $n$ distinct objects arranged in a circle is
  $$\frac{n!}{n}=(n-1)!$$

• The number of permutations of $n$ things of which $n_1$ are of one kind, $n_2$ of a second kind, $\dots$, and $n_k$ of a $k^{th}$ kind is
  $$\frac{n!}{n_1!n_2!\ldots n_k!}$$

• The number of arrangements of partitioning a set of $n$ objects into $r$ cells with $n_1$ elements in the first cell, $n_2$ elements in the second, and so forth, is
  $$\left( \begin{array}{c} n \\ n_1,n2_,\ldots ,n_r \\ \en... ...)=\frac{n!}{n_1!n_2!\ldots n_r!},(where~n_1+n_2+\ldots +n_r=n)$$

• The number of combinations of $n$ distinct objects taken $r$ at a time is
  $$C(n,r)=\left( \begin{array}{c} n \\ r \\ \end{array}\right)=\frac{n!}{r!(n-r)!}$$