Permutations, combinations and binomial coefficients

Choosing a pair differs from filling two named positions

Place three different objects labelled A, B and C on a table. Fill a first position and a second position with different objects. The possible lists are (A,B), (A,C), (B,A), (B,C), (C,A) and (C,B). There are six. The two positions make (A,B) different from (B,A).

Now ask only which two objects to take. There are three selections: {A,B}, {A,C} and {B,C}. Writing a set in another order does not change its members. In the adjacent diagram, each selected pair receives exactly two ordered lists.

(A,B) and (B,A) map to {A,B}; (A,C) and (C,A) map to {A,C}; (B,C) and (C,B) map to {B,C}. Six lists form three groups of size two.

A counting formula cannot decide which question you meant. First state what counts as one outcome and when two descriptions count as the same outcome. Here every object is distinct and cannot be selected twice.

Use small lists first, then return to the general argument

Revisit Counting, zero and natural numbers to count an empty collection separately from one empty outcome. Revisit Multiplication and division for equal-size groups, and Symbols, definitions and mathematical language to state exactly what your objects and conditions are.

The sum and product counting rules lesson develops these rules further. Here the needed product rule says: if every partial list of a given length has the same number of permitted next entries, multiply those stage counts. The options may depend on which entries came earlier; their number must still be the stated stage count.

On a first reading, finish the distinct-list and unordered-selection examples before the identities and polynomial expansion. The published lesson Exponent laws and power functions prepares the powers used there. Return to the binomial theorem after you can expand a product using distribution and read an exponent as the number of factors.

Arrange all distinct objects, including the empty case

A permutation of n distinct objects is a list containing every object exactly once. There are n choices for the first entry, n−1 for the second, and so on until the final single choice. For a nonnegative integer n, write n! for the factorial. When n ≥ 1, n! = n·(n−1)·…·2·1.

For A,B,C there are 3·2·1 = 6 full permutations. The two-stage list in our opening also has six outcomes, but it omits one object; that equality is specific to n = 3 and k = 2, not a reason to treat every partial list as a full permutation.

There is exactly one list of length zero: the empty list (). Arranging no objects therefore has one outcome, so 0! = 1. The product of no factors is 1 because it must leave another product unchanged. This also makes the recurrence n! = n·(n−1)! valid at n = 1: 1! = 1·0!.

Zero outcomes and one empty outcome are different. If a task requires choosing one object from an empty collection, it has no outcome. If it asks for a length-zero list, the empty list completes the task.

Stop after k positions to count a partial permutation

Let n and k be integers with 0 ≤ k ≤ n. A k-permutation is an ordered list of k different objects chosen from n distinct objects. Denote its count by P(n,k), also written nPₖ. For k ≥ 1 the count is n·(n−1)·…·(n−k+1), a product of k factors.

Every completed prefix of length j has used exactly j objects, leaving n−j permitted choices for the next entry. Thus the same stage count holds for every prefix, which justifies multiplying even though the identities of the available objects change.

Cancelling the unused tail of n! gives P(n,k) = n!/(n−k)!. For k = 0, the empty product and the empty list both give P(n,0) = 1. For k = n, the denominator is 0! and P(n,n) = n!.

Equivalently, assign an object to each of k named positions so that no two positions receive the same object. This is an injective assignment: distinct inputs have distinct outputs. No mapping terminology is needed to perform the count. If k > n, no such list exists and its count is 0; do not evaluate (n−k)! as though negative factorials belonged to this formula.

Every k-element selection has exactly k! orderings

A combination here means an unordered selection of k distinct objects from an n-element set. Write C(n,k), or “n choose k”, for its count. The word combination in a product name such as a combination lock does not tell you whether order matters; the outcome definition does.

Map each distinct ordered k-list to the set of its entries, forgetting their order. Fix any k-element selection. Its members can be ordered in exactly k! ways, and these are precisely the lists mapping to it. The groups are disjoint and all have the same size k!.

(A,B) and (B,A) map to {A,B}; (A,C) and (C,A) map to {A,C}; (B,C) and (C,B) map to {B,C}. Six lists form three groups of size two.

Therefore P(n,k) = C(n,k)·k!, so C(n,k) = P(n,k)/k! = n!/[k!(n−k)!] for integers 0 ≤ k ≤ n. The brackets in the denominator mean divide by the whole product k!(n−k)!, not divide by k! and then multiply by (n−k)!.

The boundary gives C(n,0) = C(n,n) = 1: there is one empty selection and one selection containing all objects. In particular C(0,0) = 1. For k > n there are no k-element subsets and the count is 0; the factorial quotient itself is used only on its stated domain.

Division needs a uniform number of descriptions

To divide a description count by d, every counted outcome must have exactly d descriptions. For distinct k-element selections, d = k! is proved by arranging those k distinct members. It is not a rule to divide every repeated-choice count by k!.

For two positions filled from A,B with repetition allowed, the four lists are AA, AB, BA and BB. Forgetting order gives three multisets: AA, AB and BB. The first and last have one description each; AB has two. Dividing 4 by 2! would give 2, which is wrong.

A multiset records how many copies of each type occur. It differs from a set, which records membership alone, and from an ordered list, which records positions. We will count arrangements of one fixed multiset below; we are not using the distinct-selection formula to count all multisets.

Explain two binomial identities by the choices they count

For a fixed n-element set, taking the complement pairs every k-element subset with exactly one (n−k)-element subset, and doing it twice returns the original subset. This bijection proves C(n,k) = C(n,n−k) for integers 0 ≤ k ≤ n. Choosing what to keep and choosing what to leave out give the same number of outcomes.

For n ≥ 1 and 1 ≤ k ≤ n−1, single out one object, say D. Every k-element subset either contains D or does not. In the first disjoint case choose k−1 of the other n−1 objects; in the second choose k of them. These cases are exhaustive, so C(n,k) = C(n−1,k−1) + C(n−1,k).

Omitting D gives {A,B},{A,C},{B,C}. Including D gives {A,D},{B,D},{C,D}. No selection belongs to both groups, and together they exhaust all six pairs.

Rows zero through five are 1; 1,1; 1,2,1; 1,3,3,1; 1,4,6,4,1; 1,5,10,10,5,1. The highlighted six has parents three and three.

For example, to choose two from A,B,C,D, the three choices containing D are {A,D},{B,D},{C,D}; the three omitting D are {A,B},{A,C},{B,C}. Thus C(4,2) = C(3,1)+C(3,2) = 3+3 = 6. The adjacent split shows both cases without overlap.

Pascal’s triangle begins with row 0 containing 1. Row n lists C(n,0),…,C(n,n). Both boundary entries are 1; every interior entry is the sum of the two appropriate entries in the preceding row. If we extend C(n,k) to be 0 for integer k outside 0,…,n, Pascal’s identity also covers k = 0 and k = n without negative factorials.

A coefficient counts which factors supply y

Expand (x+y)³ as three labelled factors (x+y)(x+y)(x+y). Distribution chooses either x or y from each factor. The eight choice patterns are xxx,xxy,xyx,yxx,xyy,yxy,yyx,yyy. Their positions are choices from particular factors, even though multiplication later makes xxy,xyx,yxx the same monomial x²y.

In n factors, a term xⁿ⁻ᵏyᵏ arises by choosing y from exactly k factor positions and x from the others. There are C(n,k) such selections. Adding the contributions with the same monomial gives the finite binomial theorem: (x+y)ⁿ = Σₖ₌₀ⁿ C(n,k)xⁿ⁻ᵏyᵏ for every nonnegative integer n.

xxx contributes x³; xxy,xyx,yxx contribute x²y; xyy,yxy,yyx contribute xy²; yyy contributes y³. Group sizes are 1,3,3,1.

This is a polynomial identity for commuting variables, and it can be evaluated at any real numbers x,y. A factor with exponent zero is omitted; when n = 0 the entire polynomial is the constant 1. No claim about arbitrary real exponents or noncommuting multiplication is being made.

For n = 3 the coefficients are 1,3,3,1, giving x³+3x²y+3xy²+y³. A coefficient is the number of factor-choice patterns contributing to one monomial, not an additional exponent. Summing all C(n,k) counts all subsets by their sizes, so Σₖ₌₀ⁿ C(n,k) = 2ⁿ: each object is independently either included or omitted.

Repetition keeps all n options available at every position

For n ≥ 1 distinct symbols and a nonnegative integer k, an ordered length-k list with repetition allowed has n choices at every position. It therefore has nᵏ outcomes. Here “independent choices” means that each position permits the full same symbol set, without restrictions imposed by earlier entries; it is a counting condition, not a probability assumption.

For A,B,C and two positions there are 3² = 9 lists. The three extra lists beyond the six distinct-entry lists are AA, BB and CC. In a grid of first and second choices, repetition permits the diagonal as well as the off-diagonal cells.

Rows are AA,AB,AC; BA,BB,BC; CA,CB,CC. The diagonal AA,BB,CC is allowed only in the repetition model. Nine repeated-choice lists versus six distinct-entry lists.

A length-zero list still has one outcome for every alphabet, even the empty alphabet. A positive-length list over the empty alphabet has zero outcomes. Handle that empty-alphabet boundary from the objects rather than relying on an unstated meaning of 0⁰.

Strings such as digit codes can begin with 0 when the task permits it. A k-digit number usually cannot: its first position has a different permitted set. The expression nᵏ describes only the stated same-options-at-each-position model.

Erase temporary labels only among identical copies

Suppose a fixed multiset has r types with multiplicities m₁,…,mᵣ, all nonnegative integers, and total N = m₁+…+mᵣ. Count ordered arrangements containing exactly these copies. Temporarily label copies within each type so that all N objects become distinct. There are N! labelled lists.

Fix one visible arrangement and erase the temporary labels. The m₁ copies of the first type can exchange labels in m₁! ways without changing the visible arrangement, and likewise for each type. These exchanges occur in disjoint sets of positions, so every visible arrangement has exactly m₁!·…·mᵣ! labelled descriptions.

A₁A₂B and A₂A₁B give AAB; A₁BA₂ and A₂BA₁ give ABA; BA₁A₂ and BA₂A₁ give BAA. Every group has size 2!, so six descriptions give three strings.

Uniform division now gives N!/(m₁!·…·mᵣ!) visible arrangements. For A,A,B, the six labelled lists collapse into AAB, ABA and BAA, two descriptions per outcome. Hence 3!/2! = 3. For A,A,B,B the count is 4!/(2!2!) = 6.

The multiplicities are fixed here. This differs from making N independent choices from r types, which would allow different multiplicities in different lists. Zero multiplicities contribute 0! = 1. If N = 0, there is one empty arrangement. Labels that make two objects observably different must not be erased.

Ask what can change without creating a new outcome

Does exchanging positions create a new outcome? If yes, count lists. If no, and the selected objects are distinct and used once, count subsets. May an object or symbol appear again? If yes, specify whether every position retains all options or whether fixed multiplicities are required.

Decide distinguishability from the task. Two people with the same first name are still distinct people when selecting a committee. Two tokens of the same colour may be indistinguishable only if their individual identities do not matter to the counted result.

A small complete list is a useful check, while the stage counts, uniform group sizes or bijections explain why the general formula works. If additional conditions couple positions, count the permitted outcomes under those conditions instead of forcing one of these formulas.

Worked examples

Try it yourself

1. For A,B,C,D, count ordered two-entry lists without repetition and unordered two-member selections. Explain the dividing factor.

   Show the answer and reasoning

   P(4,2) = 4·3 = 12 lists; C(4,2) = 12/2! = 6 selections.

   Each two-member selection has exactly two list orderings. Different selections share no list, so dividing by 2 is justified.

2. How many length-zero lists use an empty alphabet? How many length-one lists use it? What are P(0,0) and C(0,0)?

   Show the answer and reasoning

   One empty list, zero length-one lists, P(0,0) = 1 and C(0,0) = 1.

   The empty list and empty selection each form one completed outcome. A required first entry has no permitted symbol. Counting outcomes is different from counting their entries.

3. Can five distinct-entry positions be filled from four objects? Why should 4!/(4−5)! not be used?

   Show the answer and reasoning

   No; the count is 0. The factorial quotient is outside its domain 0 ≤ k ≤ n.

   After using all four objects no object remains for the fifth position. The expression would require (−1)!, which is not a factorial defined for this finite-count formula.

4. Compute C(6,4) using complement symmetry, then verify it with Pascal’s identity.

   Show the answer and reasoning

   C(6,4) = C(6,2) = 15, and C(5,3)+C(5,4) = 10+5 = 15.

   Every four-member subset is paired with the omitted two-member subset. Singling out one of the six objects splits four-member selections into those containing it and those not containing it.

5. Find the coefficient of x³ in (1+2x)⁵.

   Show the answer and reasoning

   C(5,3)·2³ = 10·8 = 80.

   Choose 2x from exactly three of the five factors; each chosen pattern contributes 8x³. The other factors contribute 1. Ten such patterns give the coefficient 80.

6. Why does 2²/2! not count unordered two-symbol multisets drawn from A,B when reuse is allowed? List the actual outcomes.

   Show the answer and reasoning

   The outcomes are AA, AB and BB, so there are 3. The proposed quotient gives 2 and is wrong.

   AA and BB each have one ordered description, while AB has two. The groups do not all have size 2!, so the uniform division argument does not apply.

7. Compare all length-four A/B strings with those containing exactly two A’s and two B’s.

   Show the answer and reasoning

   There are 2⁴ = 16 unrestricted strings, but 4!/(2!2!) = C(4,2) = 6 with the prescribed multiplicities.

   The first task retains both options in every position; the second restricts the number of each symbol. Choosing the two A positions counts exactly the second task.

8. Four people include two with the same first name. How many unordered two-person committees can be chosen if individual identities matter?

   Show the answer and reasoning

   C(4,2) = 6 committees.

   The two people remain distinct objects despite sharing a name. Dividing by another 2! to erase their identities would change the outcome definition and incorrectly identify different committees.

What to carry forward

• State whether positions, reuse and individual identities matter before selecting a formula.
• Factorials count complete distinct arrangements; 0! = 1 reflects one empty arrangement.
• P(n,k) counts distinct ordered k-lists and C(n,k) counts k-element subsets; divide by k! only after proving uniform group size.
• Complement symmetry and Pascal’s identity follow from a bijection and two exhaustive disjoint cases.
• A binomial coefficient counts factor positions supplying one term in a finite polynomial expansion.
• Repeated independent choices and fixed multiset permutations have different conditions, including their empty cases.