Counting Permutations

Permutations is that part of statistics involving arrangements of objects, some of which fall in the same group and some of which fall in different groups. Each object is distinct from all the other objects, so we can tell each one apart, and if two objects are interchanged, this is a different arrangement of the objects. There are a wide variety of questions that may be asked.

We may be asked how many arrangements can there be ifobjects in a group are arranged in a line. This is the simplest question – the answer issince the first in line can be chosen from candidates, the second fromcandidates, the third fromcandidates etc. Continuing in this way we find there arepossible arrangements altogether.

Suppose that instead of a single group there are two groups. The first group hasobjects and the second group hasobjects. If the two groups must be arranged separately, with the first group together and the second all together, then the first may be arranged inways and the second inways, so the total number of arrangements isIf We can have the first group either first or second this introduces another factor of 2 so there arearrangements altogether.

In general if we have m groups of objects withobjects respectively then the number of arrangements of all the objects iswith the groups in the natural order, with the first group first, second groups second, third group third etc. If we allow the order of the groups to change – as opposed to the objects within the groups – this introduces another factor ofsince there aregroups.

Hence the number of arrangements of k groups of objects, withobjects in group 1,objects in group 2,objects in group 3, is

If we treat all the objects as part of one single group then there are elements altogether, and there arearrangements.

Suppose now that we have n objects arranged in a circle. You might imagine there are n! Possible arrangements but you are wrong. We must divide by a factor n because the ring can be rotated so that abcde for example is the same as bcdea, cdeab, deabc, eabcd and by a factor 2 because the ring can be reflected. Hence there arearrangements altogether. Ifa reflection is the same as a rotation – this is a special case. There is only one arrangement.

You have no rights to post comments