Permutations and combinations

Permutations and combinations

Basic Principles

• Permutations: Different ways in which a set of objects can be arranged.
• Combinations: Different selections of objects where the order of selection does not matter.

Factorial Notation

• The factorial of a positive integer n is the product of all positive integers less than or equal to n. It is denoted by n!.
• By convention, we define 0! as 1.

Permutations

• The number of permutations of n different items taken r at a time is given by nPr = n! / (n-r)!.
• When some items are identical, use the formula, n! / (p1! * p2! * … * pk!), where pi’s are the number of identical objects of type i.
• Circular permutations are different when dealing with rotations and arrangements around a circle. If there are n objects, the number of arrangements is (n-1)!.

Combinations

• The number of combinations of n different items taken r at a time is given by nCr = n! / r!(n-r)!.

The Multiplication Principle

• If an operation can be performed in m ways and following it a second operation can be performed in n ways, then the two operations can be performed in m x n ways.

The Addition Principle

• If an operation can be performed in m ways and an alternative operation can be performed in n ways, then either of the two operations can be performed in m + n ways.

Always remember to think carefully about whether order matters (which would mean using permutations) or not (which would mean using combinations). Understanding the problem is half the battle won.