Counting Principles in Statistics: Permutations, Combinations, and Random Sampling

Counting Principles in Statistics

Introduction

Counting principles are fundamental tools in statistics for determining the number of possible outcomes in various scenarios. These principles are essential for probability calculations, data analysis, and designing experiments. This guide covers the multiplication rule, permutations, combinations, and random sampling methods.

Multiplication Rule of Counting

Definition and Application

• Multiplication Rule: If a task consists of a sequence of choices, where there are p possibilities for the first choice, q for the second, r for the third, and so on, the total number of ways to make these selections is:

$p \times q \times r \times \ldots$

• This rule applies when each choice is independent of the others.

Example

• Suppose there are 2 appetizers, 4 entrées, and 3 desserts. The total number of different meals is:

$2 \times 4 \times 3 = 24$

• Thus, 24 different meals can be ordered.

Permutations

Definition

• A permutation is an ordered arrangement of objects. It is used when the order of selection matters and no object is repeated (no replacement).

• The number of permutations of r objects selected from n distinct objects is denoted as $P^n_r$.

$P^n_r = \frac{n!}{(n - r)!}$

• n! (n factorial) is the product of all positive integers up to n.

Example

• How many ways can horses in a 10-horse race finish first, second, and third?

$P^{10}_3 = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$

• There are 720 possible ways for the top three horses to finish.

Permutations with Non-Distinct Objects

• When some objects are identical, the number of distinct permutations is:

$\frac{n!}{n_1! n_2! \ldots n_k!}$ where $n = n_1 + n_2 + \ldots + n_k$

Example

• How many different vertical arrangements are there of 10 flags if 5 are white, 3 are blue, and 2 are red?

$\frac{10!}{5!3!2!} = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5!}{5! \times 3! \times 2!} = \frac{30240}{12} = 2,520$

• There are 2,520 different arrangements.

Combinations

Definition

• A combination is an unordered selection of objects. It is used when the order does not matter and no object is repeated (no replacement).

• The number of combinations of r objects selected from n distinct objects is denoted as $C^n_r$.

$C^n_r = \frac{n!}{r!(n - r)!}$

• This formula counts the number of ways to choose r objects from n without regard to order.

Example

• How many different simple random samples of size 4 can be obtained from a population of size 20?

$C^{20}_4 = \frac{20!}{4! \times 16!} = \frac{20 \times 19 \times 18 \times 17}{4 \times 3 \times 2 \times 1} = \frac{116,280}{24} = 4,845$

• There are 4,845 different simple random samples of size 4 from a population of 20.

Factorial Symbol

Definition

• The factorial of a non-negative integer n, denoted n!, is the product of all positive integers less than or equal to n:

$n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$

• Special cases:

• 0! = 1

• 1! = 1

• 2! = 2

• 3! = 6

Probability and Counting

Application Example: Coin Toss

• Suppose a fair coin is tossed 10 times. What is the probability of observing at least one head?

1. There are $2^{10} = 1,024$ possible outcomes (sequences of heads and tails).

2. Each outcome is equally likely: $P(\text{each outcome}) = \frac{1}{1,024}$

3. The event "at least one head" is the complement of "no heads" (i.e., all tails), which is only 1 outcome.

4. Thus, $P(\text{at least one head}) = 1 - \frac{1}{1,024} = \frac{1,023}{1,024} \approx 0.999$

• It is almost certain to observe at least one head in 10 tosses.

Random Sampling Designs

Types of Simple Random Sampling (SRS)

• Given a population of size N, the number of possible samples of size n depends on:

  • With or without replacement

  • Ordered or unordered selection

Sampling Design	Number of Samples	Formula
With replacement & ordered	$N^n$	$N^n$
With replacement & unordered	$\frac{(N+n-1)!}{n!(N-1)!}$	$\frac{(N+n-1)!}{n!(N-1)!}$
Without replacement & ordered	$\frac{N!}{(N-n)!}$	$P^N_n$
Without replacement & unordered	$\frac{N!}{n!(N-n)!}$	$C^N_n$

Example: Population of 4, Sample Size 2

• With replacement & ordered: $4^2 = 16$ samples

• With replacement & unordered: $\frac{5!}{2!3!} = 10$ samples

• Without replacement & ordered: $\frac{4!}{2!} = 12$ samples

• Without replacement & unordered: $\frac{4!}{2!2!} = 6$ samples

Decision Flowchart for Counting Methods

To determine which counting method to use, consider:

• Are you making a sequence of choices? Use the multiplication rule.

• Are the number of choices at each stage independent? If not, use a tree diagram.

• Does the order of arrangement matter?

  • If yes, use permutations.

  • If no, use combinations.

• Are objects distinct or are there repeated types? Use the appropriate formula for non-distinct objects if needed.

Applications

Lottery Probability Example

• In the Illinois Lottery, 6 balls are chosen from 52 without replacement and order does not matter.

• Number of possible combinations: $C^{52}_6 = \frac{52!}{6!46!} = 20,358,520$

• Each ticket has two sets of 6 numbers, so two chances to win:

• Probability of winning: $P(E) = \frac{2}{20,358,520} \approx 0.000000098$

• There is about a 1 in 107 chance of winning.

Summary Table: Counting Formulas

Situation	Order?	Replacement?	Formula
Sequence of choices	Yes	Yes/No	$p \times q \times r \times \ldots$
Permutations	Yes	No	$\frac{n!}{(n-r)!}$
Combinations	No	No	$\frac{n!}{r!(n-r)!}$
Permutations (non-distinct)	Yes	No	$\frac{n!}{n_1! n_2! \ldots n_k!}$

Additional info: The flowchart at the end of the notes provides a visual guide for selecting the appropriate counting method based on the problem's characteristics.