Permutations and Combinations

Nature, as we know it, consists, in the main of permutations and combinations.

—William Keith Brooks

Two basic counting ideas distinguish arrangements from selections:

• Permutations are groupings in which the order of objects matters.
• Combinations are groupings where content matters but order does not.

For example:

• “My fruit salad is a combination of apples, grapes and bananas”: no matter what order we put the fruits in, it could be “bananas, grapes and apples” or “grapes, apples and bananas”, it is the same salad.
• “The combination of the lock is 693”: now the order matters. “693” would work, whereas “936” would not. It has to be exactly 6-9-3

Let’s start with Laplace’s Rule: in the case where all the results of a random experiment are equally probable, Laplace defines the probability of an event A as the quotient between the number of favorable results for the event A to occur in the experiment and the number of possible results of the experiment.

To apply Laplace’s Rule, the calculation of favorable events and possible events sometimes does not pose any problem, since they are a small number and can be easily calculated, for example:

• When calculating the probability of rolling a die and getting a 2, there is only one favorable case while the possible cases are six.
• If we guess a person’s zodiac sign uniformly from the signs, there is one favorable case and twelve equally likely guesses.

However, calculating the number of favorable cases and possible cases can be difficult sometimes and you have to apply mathematical rules, for example:

Five couples randomly sit down to dinner and we want to calculate the probability that at least the members of one couple sit together. In this case, determining the number of favorable cases and possible cases is complex.

The mathematical rules that can assist us here are the calculation of combinations and the calculation of permutations.

COMBINATIONS

In combinatorics we determine the number of subgroups of 1, 2, 3, etc. elements that can be formed with the n elements of one group and where each subgroup differs from the rest in the elements that compose it without taking the order in which they appear into account.

For example, calculate the possible combinations of two elements that can be formed with the numbers 1, 2 and 3.

Three different pairs can be established: (1,2), (1,3) and (2,3). In the calculation of combinations, the pairs (1,2) and (2,1) are considered identical, therefore they are only counted once.

PERMUTATIONS

Permutations count ordered arrangements, using all the objects or a chosen subset. Changing the order produces a different arrangement.

For example, calculate the possible ways in which the numbers 1, 2, and 3 can be ordered.

These examples distinguish unordered selections from ordered arrangements.

• Combination: Picking a team of 3 people from a group of 10. C(10,3) = 10!/(7! · 3!) = 10 · 9 · 8 / (3 · 2 · 1) = 120.
• Permutation: Picking a President, VP and Water boy from a group of 10. P(10,3) = 10!/7! = 10 · 9 · 8 = 720.
• Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.
• Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.

BASIS FOR COMPARISON	PERMUTATION	COMBINATION
MEANING	Permutation refers to the different ways of arranging a set of objects in a sequential order.	Combination refers to several ways of choosing items from a large set of objects, such that their order does not matter
ORDER	Relevant	Irrelevant
DENOTES	Arrangement	Selection
WHAT IS IT?	Ordered arrangement	Unordered selection
ANSWERS	How many different arrangements can be created from a given set of objects?	How many different groups can be chosen from a larger group of objects?
DERIVATION	Multiple permutations from a single combination.	Ignoring order maps each arrangement to a single selection.
EXAMPLES	Assigned seats, race classification, organizational hierarchy, industrial processes	Selecting fruits