Important Formulas: Permutation and Combination

Table of Contents
1. Permutation
2. Permutation and Combination Formulas
3. Important Points
4. Factorial
5. Permutations
6. Combinations
7. Worked Examples
8. Applications and Tips
View more

Permutation

A permutation is an arrangement of a set of objects in a specific order. When order matters, different arrangements of the same objects are considered different permutations. The number of permutations of n distinct objects taken r at a time is denoted by nPr. Permutations appear across mathematics and computer science, for example in counting arrangements, ordering tasks and analysing sorting algorithms.

Combination
A combination is a selection of objects where order does not matter. When only the choice of members matters and not their order, we count combinations. The number of combinations of n distinct objects taken r at a time is denoted by nCr. Combinations are used when forming committees, groups, subsets and in probability problems.

Permutation and Combination Formulas

The number of all permutations of n things taken r at a time is given by:

In standard notation this is

nPr = n! ÷ (n - r)!

where n! denotes factorial of n.

The number of all combinations of n things taken r at a time is given by:

In standard notation this is

nCr = nPr ÷ r! = n! ÷ (r!(n - r)!)

Use combinations when the order of selection does not matter.

Important Points

• Factorial of a negative integer is not defined.
• If one task can be done in m ways and another independent task in n ways, then either one of the two tasks can be done in m + n ways and both tasks together can be done in m × n ways.
• 0! = 1.
• 1! = 1.
• When some objects are identical, the number of distinct permutations decreases. If from n objects, p1 are of one kind, p2 are of another kind, ..., pr are of the rth kind, then the number of distinct linear arrangements is given by a correction to n! that divides by identical-block factorials.

Factorial

For a non-negative integer n, the factorial n! is defined by the product of all positive integers from n down to 1.

n! = n × (n - 1) × (n - 2) × ... × 2 × 1

Example:

5! = 5 × 4 × 3 × 2 × 1

Standard Truths

• 0! = 1.
• The factorial n! is defined for n ≥ 0 and is not defined for negative integers.

Permutations

nPr denotes the number of ways to select and arrange r objects from n distinct objects. The general formula is

nPr = n! ÷ (n - r)!

Common permutation cases and formulas:

• Permutations when repetition is allowed: For arranging r positions where each position can be filled independently from n distinct types, the number of arrangements is n^r.
• Permutations with identical objects: If objects include identical items, divide total permutations by the factorials of repetitions. Example: arrangements of letters in the word BANANA.
• Circular permutations (arrangements around a circle): For arranging n distinct objects in a circle where rotations are considered identical, the number is (n - 1)!.

Combinations

nCr denotes the number of ways to select r objects from n distinct objects when order does not matter. The formula is

nCr = n! ÷ (r!(n - r)!)

• Symmetry: nCr = nC(n - r).
• Relation with permutations: nCr = nPr ÷ r!.
• Pascal's identity: nCr = (n - 1)C(r - 1) + (n - 1)Cr.
• Combinations with repetition (multiset combinations): The number of ways to choose r items from n types with repetition allowed is (n + r - 1)C r.

Worked Examples

Example 1. How many ways can a committee of 3 be chosen from 7 people?

Sol.

Select 3 from 7; order does not matter.

7C3 = 7! ÷ (3!4!)

Compute or simplify to obtain the numeric value.

Ans. 35

Example 2. How many distinct arrangements are there of the letters in the word BANANA?

Sol.

Total letters = 6.

If letters were all distinct, permutations = 6!.

Letters repeated: A appears 3 times and N appears 2 times.

Distinct arrangements = 6! ÷ (3! × 2!)

Ans. 60

Example 3. In how many ways can 4 students be seated in a row of 10 chairs?

Sol.

Choose 4 chairs from 10 and arrange 4 students in those chairs.

Number of ways = 10P4 = 10! ÷ 6!

Ans. 5040

Applications and Tips

• Decide first whether order matters. If it does, use permutations; if not, use combinations.
• For repeated items divide by factorials of repetition counts.
• For problems with multiple independent choices, use sum rule for exclusive choices and product rule for sequential independent choices.
• Use complement counting when direct counting is hard: count the total and subtract the unwanted cases.
• Familiarise yourself with factorial growth and cancellation to simplify factorial expressions quickly.

Summary: Use nPr = n! ÷ (n - r)! when order matters and nCr = n! ÷ (r!(n - r)!) when order does not matter. Remember special cases such as repetition, identical objects and circular arrangements, and apply product/sum rules where appropriate.