Permutations, Combinations & Binomial Coefficients
Permutation
Definition. Any arrangement of a set of n distinct objects in a specific order is called a permutation of the objects. Any arrangement of r objects (where 0 ≤ r ≤ n) taken from these n objects in a specific order is called an r-permutation or a permutation of n objects taken r at a time.
Notation. The number of r-permutations of n distinct objects is denoted by P(n, r).
Formula (standard). The number of permutations of n distinct objects taken r at a time is given by the formula below.
Theorem. The number of permutations of n distinct objects when taken all at a time equals n!
Proof.
The first place may be filled in n ways.
The second place may be filled in n - 1 ways.
The third place may be filled in n - 2 ways.
Continuing in this manner, the nth place may be filled in 1 way.
Therefore, by the fundamental principle of counting, the total number of linear arrangements is
which equals n!, and the result follows.
Worked example
Example. Solve 4 × nP3 = n + 1.
From the equation 4 (n - 2) = (n + 1),
4n - 8 = n + 1,
3n = 9,
n = 3.
Permutations with restrictions
- The number of permutations of n different objects taken r at a time in which p particular objects do not occur is the number of r-permutations from the remaining (n - p) objects, i.e., P(n - p, r).
- The number of permutations of n different objects taken r at a time in which p particular objects are required to be present can be obtained by first choosing how many of the required objects appear and then arranging; the typical counting expression is shown below.
Example: forming 6-digit numbers beginning with '30' (no repetition)
Problem. How many 6-digit numbers can be formed using the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 if every number is to start with '30' and no digit is repeated?
Solution idea. The first two digits are fixed as '3' and '0'. We must choose and arrange the remaining four digits from the remaining digits (excluding 3 and 0).
There are 9 available digits originally (0-8). After using 3 and 0, 7 digits remain. We need an ordered selection of 4 digits from these 7.
Hence the total number of such 6-digit numbers is
Permutations with repetition allowed
Theorem. If repetition of objects is allowed, the number of different ordered arrangements of r positions each chosen from n distinct objects equals nr.
Proof.
When repetition is allowed, each of the r places may be filled in n ways.
The first place may be filled in n ways.
The second place may be filled in n ways.
...
The rth place may be filled in n ways.
Therefore the total number of ordered r-tuples is
n × n × ··· × n (r factors) = nr.
Circular permutations
- A permutation arranged around a circle (where only relative order matters and rotations are considered equivalent) is called a circular permutation.
Example. In how many ways can the letters a, b, c, d, e, f, g, h, i, j be arranged around a circle?
For 10 distinct objects arranged on a circle the number of circular permutations is (10 - 1)! = 9! = 362880.
Theorem. The number of circular permutations of n different objects is (n - 1)!.
Proof.
Fix a circular ordering. For each distinct circular arrangement there correspond n linear arrangements obtained by choosing a different starting point and listing clockwise (or anticlockwise) from that point.
Therefore, the total number of linear permutations (n!) equals the number of circular permutations times n.
Hence the number of circular permutations is n!/n = (n - 1)!.
Combination
Definition. A combination is a selection of some or all objects from a given set in which the order of selection does not matter. The number of ways to choose r elements from n distinct elements (without regard to order) is denoted by C(n, r) or nCr.
Derivation of the combination formula.
The number of permutations of n different objects taken r at a time is
For each unordered selection (combination) of r objects there are r! distinct orderings.
Therefore the number of combinations equals
Example (product rule across independent choices)
Problem. A farmer purchases 3 cows, 2 pigs and 4 hens from a man who has 6 cows, 5 pigs and 8 hens. Find the number m of choices the farmer has.
Solution. The farmer can choose:
- the cows in C(6, 3) ways,
- the pigs in C(5, 2) ways, and
- the hens in C(8, 4) ways.
By the rule of product, the total number of choices is the product of these three combination counts.
Binomial coefficients
The number of r-combinations from a set of n elements is the binomial coefficient commonly written as C(n, r) or
This same number occurs as coefficients in the expansion of powers of a binomial expression; hence the name.
Binomial theorem. Let x and y be variables and n be a non-negative integer. Then
Example 1: Coefficient extraction
Problem. What is the coefficient of x12y13 in the expansion of (2x - 3y)25?
Write (2x - 3y)25 as (2x + (-3y))25.
By the binomial theorem, the general term is shown below.
The power of y is 13, so the term corresponds to j = 13.
Therefore the coefficient of x12y13 is:
Example 2: Sum of binomial coefficients
Problem. Prove that
Set x = 1 and y = 1 in the binomial theorem expression.
Example 3: Alternating sum of binomial coefficients
Problem. Prove that
Set x = -1 and y = 1 in the binomial theorem expression.
Example 4: Weighted sum identity
Problem. Prove that
Set x = 1 and y = 2 in the binomial theorem expression.
Applications and remarks. Permutations and combinations form the basis of counting in probability, algorithm analysis, combinatorial designs and enumerative combinatorics. Circular permutations are used when arrangements are invariant under rotation (for example, seating round tables). Binomial coefficients appear in algebra, probability distributions (for example, the binomial distribution), combinatorial identities and are central to many counting arguments in computer science and discrete mathematics.
Summary (optional). Use permutations when order matters and combinations when order does not matter. For permutations with repetition use nr. For circular arrangements of n distinct objects use (n - 1)!. The binomial theorem expands (x + y)n and provides coefficients C(n, r) which capture the number of r-element subsets of an n-element set.
