The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, GMAT, AMC-8, AMC-10, Math Kangaroo 7-8, Math Kangaroo 9-10.

Linear Permutations

In how many ways can N objects be arranged in a line?

If there are N spaces and N different letters the question is the same as making up the maximum number of distinct (though perhaps meaningless) words (we call these anagrams).

Therefore, we have a total number of ways to form words:

equation

There is a shorthand notation for such a product, which is called a factorial:

equation

The number of linear permutations of N different objects is N!

What if not all objects are different?

If some of the objects are identical, the problem is similar to considering a word with N letters, of which M<N are identical.

Whenever we want to place one of these letters that repeat we have M, then M-1, etc. choices. Therefore, the total number of ways in which we can form words is smaller, since there are groups of M! words formed according to the rule for different objects that are actually the same.

The number of linear permutations of N objects out of which M are identical is:

equation

Example:

In how many ways can we build a line of 15 poker chips of which 5 are red, 7 are blue and 8 are white?

equation

Circular permutations

In how many ways can N different objects be arranged in a closed loop?

With the closed loop, there is a problem since we can 'read the words' either clockwise or anticlockwise.

Any linear permutation of N different objects is part of a group of N identical circular permutations. This is because on a closed loop, the end is the same as the start.

For instance, the letters AHNOR, when placed on a circle, can be read in any of the following ways:

equation

equation

equation

equation

equation

This means that the N! linear permutations can be grouped into groups of N that are not distinguishable when read circularly. (These groups are called classes of equivalence.)

Therefore, the number of distinct circular permutations of N different objects is:

equation

This is true if we allow only one way of reading around the circle: either counterclockwise or clockwise.

If we allow reading both ways, then any mirror image of a word is identical to the word itself (only read the other way):

equation

Notice that RONHA is not one of the elements of the group of circular permutations.

Therefore, if we allow reading both ways, we have to divide by the size of the group of identical permutations: 2.

equation

Example:

How many distinct necklaces can be made using 16 opals, 11 alexandrites, and 18 sapphires?

Assuming all the similar stones are not distinguishable, since they are arranged in a circular loop:

equation

This is because the necklace is the same if we flip it upside down (i.e. we allow 'reading' it both clockwise and counter-clockwise.)

Number of paths in a lattice:

This problem reduces to a 'letter arranging' problem.

Example:

A he-flea is at point (3,4) on a lattice and can jump only 1 unit either up or left, due to a neurological injury from ingesting DDT. How many distinct possible paths can it take to reach a she-flea at (-4,10)?

Notice that the flea has to take 7 steps to the left and 6 to the right.

The order in which he takes the steps represents the path. The number of different paths is the same as the number of different linear permutations of 7 L letters and 6 U letters: LLLLLLLUUUUUU

equation

A lattice is a subset of points in the Cartesian plane that have integer coordinates.