Permutations and Combinations

The One Thing

Counting problems are solved by first determining whether order matters. Use permutations for ordered arrangements, combinations for unordered selections, and apply the multiplication or addition principles according to whether choices occur successively or are mutually exclusive.

Definitions and Results

• Factorial: For a positive integer $n$, $n!=n(n-1)(n-2)\cdots 2\times 1$, and $0!=1$.
• Fundamental Principle of Counting: If one task can be completed in $m$ ways and a second task in $n$ ways, both tasks can be completed in $m\times n$ ways. More generally, successive choices with $m_1,m_2,\dots ,m_k$ possibilities give $m_1{m}_2\cdots m_k$ outcomes.
• Addition Principle: If mutually exclusive alternatives can be chosen in $m$ and $n$ ways, one alternative can be chosen in $m+n$ ways. For several mutually exclusive cases, add the numbers of outcomes.
• Permutation: An arrangement of objects in which order or position is important.
• Combination: A selection of objects in which order is not important.
• Permutation of $n$ distinct objects: The number of arrangements of all $n$ objects is $n!$.
• Permutation of $n$ objects taken $r$ at a time:

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

• Combination of $n$ objects taken $r$ at a time:

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

• Repeated objects: If $n$ objects contain identical groups occurring $p_1,p_2,\dots ,p_k$ times, the number of distinct arrangements is

$$\frac{n!}{p_1!p_2!\cdots p_k!}.$$

• Circular permutation: The number of arrangements of $n$ distinct objects around a circle, when rotations are considered identical, is

$$(n-1)!.$$

• 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.

• Complementary selection: Selecting $r$ objects from $n$ is equivalent in number to selecting the remaining $n-r$ objects:

$${}^n{C}_r={}^n{C}_{n-r}.$$

• Pascal identity:

$${}^n{C}_r+{}^n{C}_{r-1}={}^{n+1}{C}_r.$$

• Special combination values:

$${}^n{C}_0={}^n{C}_n=1,{}^n{C}_1=n.$$

• Arrangements with repetition allowed: Filling $r$ positions from $n$ choices gives

$$n^r$$ arrangements.

Worked Methods

1. Applying the Fundamental Principle of Counting

• Identify successive tasks or choices.
• Count the possibilities for each stage.
• Multiply the numbers of possibilities.

If successive choices have $m_1,m_2,\dots ,m_k$ possibilities, the total number of outcomes is $$m_1\times m_2\times \cdots \times m_k.$$

Use this method when choices occur successively, including arrangements with repetition allowed. If $r$ positions are filled from $n$ available choices and repetition is allowed, the count is $$n^r.$$

2. Applying the Addition Principle

• Separate the problem into mutually exclusive cases.
• Count the outcomes in each case.
• Add the case totals.

If alternatives can be made in $m$ and $n$ ways, the total is $$m+n.$$

The alternatives must be mutually exclusive; otherwise some outcomes may be counted more than once.

3. Counting permutations of all objects

• Confirm that all $n$ objects are distinct.
• Since order matters, use the factorial formula.
• Calculate

$$n!.$$

For example, the number of arrangements of $n$ distinct objects is $n!$.

4. Counting partial permutations

• Confirm that order matters.
• Identify the total number of distinct objects, $n$, and the number selected for arrangement, $r$.
• Apply

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

The condition is $$0\le r\le n.$$

5. Counting combinations

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

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

The condition is $$0\le r\le n.$$

The relationship $${}^n{P}_r=r!{}^n{C}_r$$ shows that each unordered selection of $r$ objects corresponds to $r!$ ordered arrangements.

6. Counting arrangements with repeated objects

• Count all $n$ objects as though they were distinct, giving $n!$.
• Identify each group of identical objects.
• Divide by the factorial of the size of every identical group:

$$\frac{n!}{p_1!p_2!\cdots p_k!}.$$

This removes repeated counting of arrangements that differ only by interchanging identical objects.

7. Counting circular permutations

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

$$(n-1)!.$$

8. Using complementary selection

• Determine the total number of selections.
• Count the unwanted selections, usually those containing none of a required type.
• Subtract:

$$\text{required count}=\text{total count}-\text{unwanted count}.$$

This is particularly useful when a selection problem requires at least one object of a particular type.

9. Using combination identities

For complementary selections, replace $r$ with $n-r$: $${}^n{C}_r={}^n{C}_{n-r}.$$

For neighboring values, apply Pascal identity: $${}^n{C}_r+{}^n{C}_{r-1}={}^{n+1}{C}_r.$$

These identities can simplify calculations and connect related selection counts.

10. Handling restrictions

• Determine whether objects must be together, separated, fixed at an end, or arranged alternately.
• Apply the restriction before using the relevant permutation or combination formula.
• Check whether repetition is allowed.
• Decide whether the remaining problem involves an arrangement or a selection.
• Apply the appropriate formula only after the restriction has been incorporated.

Where It Goes Wrong

• Using permutations when order does not matter, or combinations when order does matter.
• Applying the Addition Principle to alternatives that are not mutually exclusive; addition requires separate cases.
• Forgetting that $0!=1$, which affects factorial, permutation, and combination calculations.
• Treating identical objects as distinct, thereby counting the same arrangement multiple times.
• Using $n!$ for a circular arrangement without removing equivalent rotations; when rotations are identical, the count is $(n-1)!$.
• Ignoring restrictions or whether repetition is allowed before selecting a formula.

What Gets Asked

• Calculate the number of arrangements using factorials.
• Apply the Fundamental Principle of Counting to successive choices.
• Apply the Addition Principle to mutually exclusive cases.
• Decide whether a problem requires a permutation or a combination.
• Calculate ${}^n{P}_r$ or ${}^n{C}_r$ under the condition $0\le r\le n$.
• Count arrangements containing repeated or identical objects.
• Count circular arrangements when rotations are considered the same.
• Use ${}^n{P}_r=r!{}^n{C}_r$, ${}^n{C}_r={}^n{C}_{n-r}$, or Pascal identity.
• Count arrangements with repetition allowed using $n^r$.
• Solve restricted arrangements involving objects together, separated, fixed at an end, or arranged alternately.
• Use the complement method in selection problems requiring at least one object of a specified type.