Combinatorics and Probability

The One Thing

Combinatorics counts arrangements and selections systematically, while probability measures the likelihood of events. The decisive distinction is whether order matters: permutations apply to ordered arrangements, whereas combinations apply to selections in which order does not matter.

Definitions and Results

• Fundamental Principle of Counting: If one task can be completed in $m$ ways and a second task in $n$ ways, then both tasks together can be completed in $m\times n$ ways. For successive choices, multiply the numbers of choices at each stage; for alternative choices that cannot occur together, add the numbers of choices.
• Factorial: For a positive integer $n$, $n!=n\times (n-1)\times (n-2)\times \cdots \times 2\times 1$, and $0!=1$.
• Permutation: An arrangement of objects in which order matters.
• Permutation of $n$ objects taken $r$ at a time: The number of ordered arrangements of $r$ objects selected from $n$ objects is

$${}_n{P}_r=\frac{n!}{(n-r)!},$$ where $0\le r\le n$.

• Permutation with repeated objects: If $n$ objects contain identical groups of sizes $p$, $q$, and so on, the number of distinct arrangements is

$$\frac{n!}{p!q!\cdots }.$$

• Circular permutation: The number of arrangements of $n$ distinct objects around a circle is

$$(n-1)!,$$ when rotations are considered identical.

• Combination: A selection of objects in which order does not matter.
• Combination of $n$ objects taken $r$ at a time: The number of selections of $r$ objects from $n$ objects is

$${}_n{C}_r=\frac{n!}{r!(n-r)!},$$ where $0\le r\le n$.

• Relation between permutations and combinations:

$${}_n{P}_r={}_n{C}_r\times r!,$$ because each selection of $r$ objects can be arranged in $r!$ orders.

• Symmetry of combinations:

$${}_n{C}_r={}_n{C}_{n-r},$$ because selecting $r$ objects is equivalent to leaving out $n-r$ objects.

• Sample space: The set of all possible outcomes of a random experiment, usually denoted by $S$.
• Random experiment: A process with a known set of possible outcomes, although its exact outcome cannot be predicted with certainty.
• Event: A collection of one or more outcomes from the sample space.
• Favourable outcomes: Outcomes satisfying the condition of the event being considered.
• Classical probability: When all outcomes are equally likely,

$$P(E)=\frac{\text{number of favourable outcomes}}{\text{total number of outcomes}}=\frac{n(E)}{n(S)}.$$

• Probability bounds and special cases:

$$0\le P(E)\le 1,P(S)=1,P(\varnothing )=0.$$

• Complement of an event: The event that $E$ does not occur, written $E^{\prime }$ or $E^c$:

$$P(E^{\prime })=1-P(E).$$

• Mutually exclusive events: Events that cannot occur together. Thus $P(A\cap B)=0$, and

$$P(A\cup B)=P(A)+P(B).$$

• Independent events: Events for which the occurrence of one does not affect the probability of the other:

$$P(A\cap B)=P(A)P(B).$$

• Addition rule of probability: For any two events,

$$P(A\cup B)=P(A)+P(B)-P(A\cap B).$$

• Conditional probability: The probability of $A$ when $B$ has already occurred is

$$P(A\mid B)=\frac{P(A\cap B)}{P(B)},$$ provided $P(B)>0$.

Worked Methods

1. Applying the Fundamental Principle of Counting

• Divide the task into successive stages.
• Count the choices available at each stage.
• Multiply the numbers of choices.

For alternative choices that cannot occur together:

• Identify the separate alternatives.
• Count the outcomes for each alternative.
• Add the counts.

This principle supports counting in passwords, schedules, teams, games, and quality-control situations.

2. Calculating a Factorial

• Write the integer as a product of all positive integers down to $1$.
• Multiply the factors.

For example, $$n!=n(n-1)(n-2)\cdots 2\times 1.$$

The special value is $$0!=1.$$

3. Counting Ordered Arrangements Using Permutations

• Determine that order matters.
• Identify $n$, the total number of objects, and $r$, the number selected.
• Apply

$${}_n{P}_r=\frac{n!}{(n-r)!}.$$

This method applies to passwords, rankings, seating orders, and schedules, where positions matter.

4. Counting Arrangements with Repeated Objects

• Count all $n$ objects.
• Identify the repetition counts $p$, $q$, and so on.
• Divide the total factorial by the factorial of each repetition count:

$$\frac{n!}{p!q!\cdots }.$$

The division prevents identical objects from being counted as distinct arrangements.

5. Counting Circular Arrangements

• Confirm that the objects are distinct.
• Treat rotations as identical.
• Fix one object to remove rotational duplication.
• Arrange the remaining $n-1$ objects:

$$(n-1)!.$$

6. Counting Selections Using Combinations

• Determine that order does not matter.
• Identify $n$, the total number of objects, and $r$, the number selected.
• Apply

$${}_n{C}_r=\frac{n!}{r!(n-r)!}.$$

This method applies to committees, teams, groups, and other selections.

The equivalent form $${}_n{C}_r={}_n{C}_{n-r}$$ may be used when leaving out $n-r$ objects is simpler than selecting $r$ objects.

7. Relating Permutations and Combinations

• Count the selection using ${}_n{C}_r$.
• Arrange the selected $r$ objects in $r!$ orders.
• Multiply:

$${}_n{P}_r={}_n{C}_r\times r!.$$

8. Calculating Classical Probability

• Define the random experiment.
• Specify the sample space $S$.
• Identify the event $E$.
• Count the favourable outcomes $n(E)$.
• Count the total outcomes $n(S)$.
• Confirm that the outcomes are equally likely.
• Calculate

$$P(E)=\frac{n(E)}{n(S)}.$$

The sample space must be defined carefully to avoid double-counting outcomes.

9. Using the Complement Rule

• Identify the event whose probability is easier to calculate.
• Define its complement.
• Use

$$P(E^{\prime })=1-P(E).$$

This calculates the probability that $E$ does not occur.

10. Using the Addition Rule

For two events $A$ and $B$:

• Calculate $P(A)$.
• Calculate $P(B)$.
• Calculate the overlap $P(A\cap B)$.
• Apply

$$P(A\cup B)=P(A)+P(B)-P(A\cap B).$$

If $A$ and $B$ are mutually exclusive, then $P(A\cap B)=0$, so the rule becomes $$P(A\cup B)=P(A)+P(B).$$

11. Using the Multiplication Rule for Independent Events

• Establish that the events are independent.
• Calculate $P(A)$ and $P(B)$.
• Multiply:

$$P(A\cap B)=P(A)P(B).$$

Independence means that the occurrence of one event does not affect the probability of the other.

12. Calculating Conditional Probability

• Identify the condition $B$, which has already occurred.
• Confirm that $P(B)>0$.
• Determine the probability of the intersection $A\cap B$.
• Apply

$$P(A\mid B)=\frac{P(A\cap B)}{P(B)}.$$

Where It Goes Wrong

• Using permutations when order does not matter, or combinations when positions matter.
• Forgetting to multiply successive choices or to add alternative choices that cannot occur together.
• Applying ${}_n{P}_r$ or ${}_n{C}_r$ without checking that $0\le r\le n$.
• Failing to divide by factorials for repeated objects, or failing to use $(n-1)!$ for circular arrangements when rotations are identical.
• Using the classical probability formula without confirming that outcomes are equally likely or without defining the sample space carefully.
• Adding probabilities without subtracting $P(A\cap B)$ for overlapping events, or applying the independent-events rule when independence has not been established.

What Gets Asked

This material supports questions requiring students to:

• Apply the Fundamental Principle of Counting to successive and alternative choices.
• Evaluate factorials, including the convention $0!=1$.
• Calculate permutations for passwords, rankings, seating orders, and schedules.
• Count distinct arrangements with repeated objects.
• Calculate circular permutations when rotations are considered identical.
• Calculate combinations for committees, teams, groups, and selections.
• Use ${}_n{C}_r={}_n{C}_{n-r}$ and ${}_n{P}_r={}_n{C}_r\times r!$.
• Define a sample space, an event, and the favourable outcomes of a random experiment.
• Calculate classical probabilities using

$$P(E)=\frac{n(E)}{n(S)}.$$

• Apply complement, addition, mutually exclusive, independent, and conditional probability rules.
• Determine whether repetition is allowed, whether order matters, and whether outcomes are equally likely before selecting a formula.