Important Formulas: Permutations & Combinations

DEFINITIONS :
1. PERMUTATION : Each of the arrangements in a definite order which can be made by taking some or all of a number of things is called a permutation.
2. COMBINATION : Each of the groups or selections which can be made by taking some or all of a number of things without reference to the order of the things in each group is called a combination.

Fundamental Principle of Counting

If an event can occur in m different ways, and following that another event can occur in n different ways, then the total number of different ways of simultaneous occurrence of both events in a definite order is m × n. This principle can be extended to any finite sequence of events: if there are k events with numbers of ways m1, m2, ..., mk, then the total number of ordered outcomes is m1 × m2 × ... × mk.

Useful Notation and Basic Results

• Factorial : For a positive integer n, n! = n × (n - 1) × (n - 2) × ... × 3 × 2 × 1. Also, 0! = 1.
• Some factorial properties : n! = n × (n - 1)!, and factorials of negative integers are not defined.
• Permutation of n different things taken r at a time : denoted by nP_r and given by the formula nP_r = n! / (n - r)! where 0 ≤ r ≤ n.
• Combination of n different things taken r at a time : denoted by nC_r and given by the formula nC_r = n! / [r! (n - r)!] where 0 ≤ r ≤ n and n ∈ N.
• Division into two groups : The number of ways in which (m + n) different things can be divided into two groups containing m and n things respectively is (m + n)! / (m! n!). If m = n (groups equal) then interchange of the two groups does not give a new subdivision and the number of distinct subdivisions becomes (m + n)! / (m! n! 2).
• Division into three groups : The number of ways in which (m + n + p) different things can be divided into three groups containing m, n and p things respectively is (m + n + p)! / (m! n! p!). If m = n = p and groups are indistinguishable among themselves, divide further by 3! as required.
• Permutations with repetitions : If among n objects, p are identical of one type, q are identical of another type, r are identical of a third type, and the remaining n - (p + q + r) are all distinct, then the number of distinct permutations is n! / (p! q! r!).
• Circular permutations : The number of circular permutations of n different things taken all at a time is (n - 1)!. If clockwise and anti-clockwise arrangements are considered the same (i.e., reflections are not distinguished), then the number is (n - 1)! / 2.
• Selecting at least one object : Given n different objects, the number of ways of selecting at least one of them is nC₁ + nC₂ + ... + nC_n = 2ⁿ - 1. This is the total number of non-empty subsets of an n-element set.
• Selection when there are identical items : If there are p objects identical of one kind, q identical of another kind, r identical of a third kind, and so on, then the total number of ways to make a selection (including empty selection) is (p + 1)(q + 1)(r + 1) ... . If empty selection is excluded, subtract 1.
• Selection of r items from groups of identical objects (generating functions) : If there are groups with at most p, m, n copies respectively, then the number of ways to select r objects is the coefficient of x^r in the expansion of (1 + x + x² + ... + x^p)(1 + x + x² + ... + x^m)(1 + x + x² + ... + xⁿ).
• Combination identity (negative binomial form) : The coefficient of x^r in (1 - x)^-n (for n ∈ N) is (n + r - 1)C_r. This is useful for problems of combinations with repetition.
• Distribution of distinct objects to people : Number of ways in which n distinct things can be distributed to p persons when there is no restriction on how many each person receives is pⁿ.
• Distribution of identical objects to people : Number of ways in which n identical objects may be distributed among p persons if each person may receive none, one or more objects is (n + p - 1)C_n (stars and bars).
• Basic combination properties : nC_r = nC_n-r ; nC₀ = nC_n = 1 ; and nC_r + nC_r-1 = (n + 1)C_r.
• When nC_r is maximal : nC_r is maximum when r = n/2 if n is even, and when r = (n - 1)/2 or r = (n + 1)/2 if n is odd. (Equivalently r = floor(n/2) or ceil(n/2).)
• Number theory related results : If N = p^a q^b r^c ... where p, q, r are distinct primes and a, b, c are natural numbers, then
  (a) The total number of positive divisors of N (including 1 and N) is (a + 1)(b + 1)(c + 1)....
  (b) The sum of these divisors is (p⁰ + p¹ + ... + p^a)(q⁰ + q¹ + ... + q^b) ... .
  (c) The number of ways in which N can be resolved as a product of two factors is given by the appropriate divisor count (see image reference below).
  (d) The number of ways a composite number N can be resolved into two factors which are relatively prime to each other is 2^n-1 where n is the number of distinct prime factors of N.
• Grid problems and tree diagrams : Many counting problems are solved by drawing a tree diagram (for ordered sequences) or by counting paths in a grid using combinations.
• DEARRANGEMENT : The number of ways in which n labelled letters can be placed into n labelled envelopes so that no letter goes into its own envelope is denoted by !n (subfactorial) and given by the formula !n = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ / n!). An equivalent expression is !n = nearest integer to n! / e.
• Choosing whether a problem is permutation or combination : Certain words and phrases in a problem indicate whether order matters (permutation) or not (combination). A reference table assists this decision (see image reference below).

Examples with Step-wise Solutions

Example 1 - Permutation and Combination: small values

Question: Find 5P3 and 5C3.

Sol.

Use the permutation formula nP_r = n! / (n - r)! and the combination formula nC_r = n! / [r!(n - r)!].

5P3 = 5! / (5 - 3)!

5P3 = 5! / 2!

5P3 = (5 × 4 × 3 × 2 × 1) / (2 × 1)

5P3 = 5 × 4 × 3 = 60

5C3 = 5! / [3! (5 - 3)!]

5C3 = 5! / (3! 2!)

5C3 = (5 × 4 × 3 × 2 × 1) / [(3 × 2 × 1)(2 × 1)]

5C3 = (5 × 4) / (2 × 1) = 10

Example 2 - Selection from letters of a word (use of generating function)

Question: The number of ways in which a selection of four letters can be made from the letters of the word PROPORTION is given by the coefficient of x⁴ in the product of generating polynomials for each distinct letter. (Preserve this question formulation exactly.)

Sol.

Identify multiplicities of letters in the word PROPORTION: counts of each distinct letter give the limits in generating factors.

Form the generating function where each factor corresponds to one distinct letter and allows powers up to its multiplicity.

Coefficient of x⁴ is obtained from expansion of (1 + x + x² + x³)(1 + x + x²)(1 + x + x²)(1 + x)(1 + x)(1 + x).

Expand or use convolution to compute the coefficient of x⁴ (students may compute by successive multiplication or by counting partitions consistent with multiplicities).

Example 3 - Circular permutations

Question: In how many ways can 6 different books be arranged on a round table? If clockwise and anti-clockwise arrangements are considered identical, how many distinct arrangements are there?

Sol.

Number of circular permutations of 6 distinct objects (distinguishing clockwise and anticlockwise) is (6 - 1)!.

(6 - 1)! = 5! = 120.

If clockwise and anticlockwise arrangements are considered the same, divide by 2.

Therefore, distinct arrangements = 120 / 2 = 60.

Example 4 - Distribution of identical objects (stars and bars)

Question: In how many ways can 7 identical sweets be distributed among 3 children if a child may receive zero or more sweets?

Sol.

Use the formula for distributing n identical objects among p persons: (n + p - 1)C_n.

Here n = 7, p = 3.

Number of ways = (7 + 3 - 1)C₇ = 9C₇ = 9C₂.

9C₂ = 9 × 8 / 2 = 36.

How to Decide: Permutation or Combination

Words and phrases that indicate order matters (use permutations): arrange, order, first/second/third, rank, seat, sequence, digit forming, code, serial, line up, permutations, distinct positions.

Words and phrases that indicate order does not matter (use combinations): select, choose, pick, committee, team, subset, group, combination, choose any r, selection, without regard to order.

Where ambiguity exists, consider whether exchanging two selected items produces a different outcome. If yes, order matters (permutation). If no, order does not matter (combination).

Additional Remarks and Tips

• Always check whether objects are distinct or some are identical - identical objects reduce the count by factorials of multiplicities.
• In circular arrangements, fix one object to remove the rotational symmetry - this reduces count from n! to (n - 1)! for distinct objects.
• For problems involving "at least one" or "at most" selections, consider complementary counting (total minus forbidden cases).
• Use generating functions for selections when there are bounded repetitions of identical objects.
• Use the inclusion-exclusion principle for derangements and for counting with exclusion conditions.
• Tree diagrams are useful to visualise stepwise decisions; grid path counting often reduces to combinations (e.g., number of shortest paths on a rectangular grid).

Final short summary: Know the factorial and its properties, the formulas nP_r = n!/(n - r)!, nC_r = n!/[r!(n - r)!], rules for distributions (distinct and identical), circular permutations, permutations with repetition, generating-function method for limited repetitions, and the inclusion-exclusion formula for derangements. Decide between permutation and combination by checking whether order affects the outcome.