Restricted Permutations

Restricted Permutations:

In mathematics, a permutation is a way of arranging a set of objects in a specific order. A restricted permutation is a permutation where certain restrictions or conditions are imposed on the arrangement of the objects. These restrictions can be based on various criteria, such as the position of certain elements, the distance between certain elements, or the parity (even or odd) of certain elements.

Permutation of n things taken all together when the things are not all different:

Let the n given things in this case be n letters, but all the letters are not different. Let p of them be alike of one kind, q of them be alike of a second kind, r of them be alike of a third kind and the rest of the letters be different. Let us consider the required number of permutations by taking all of them together to be x.

Now, if in any one of the x permutations, all the p alike letters of first kind be changed into p unlike letters different from any of the rest and only these p new letters be arranged among themselves without altering the position of any of the remaining letters, then p! new permutations would be formed from each one of the x permutations. Hence, for this change only, we would have x . p! permutations.

Similarly, if in each of the new x . p! permutations, q alike letters of the second kind be changed into q new letters different from one another and different from any of the rest and if the order of these q new letters only be changed without changing the order of any other letter we would have q! permutations from each of x . p! permutations. Thus, the total number of permutations would then be x . p! . q!.

Now, all the alike objects have been changed to different objects and so we have now n different letters. The number of permutations of these n different letters by taking all at a time = n!. Naturally, then

Permutations Involving Repetitions:

To find the number of permutations of n different things by taking r at a time, when each thing may be repeated up to r times in any arrangement.

Let the n things in this case be n different kinds of letters, there being not less than r of each kind. Let us also suppose that there are r blank places. The required number of permutations, in this case, will be equal to the number of ways in which r places can be filled up by taking r letters from the set of n kinds of different letters, each being taken once, twice, thrice …. up to r times.

The first place can be filled up by any one of the n kinds of letters and so it can be filled up in n ways. Now, when the first place has been filled up in any one of the n ways, the second can also be filled up in n ways as the same letter can be used again there. Hence, the first two places can be filled up in n x n or n² ways.

The third place can also be filled up in n ways and so the first three places can be filled up in n³ ways.

Thus, we find that at any stage of permutation, the index of the power of n in the number of permutations is the same as the number of places filled up.

Proceeding in this way, we get n as the number of ways in which the last (i.e. the r^th) place can be filled up.

Thus, the required number of permutations = n^r.

Cyclic Permutation:

When the different objects are arranged in the form of a ring, then the permutation is known as cyclic permutation. As a circle does not have any extremity, the number of permutations in a circle depends on the relative position of the objects.

If n things are to be arranged in a ring, then at first one of them is kept fixed and other (n – 1) things are to be arranged among themselves which can be done in (n – 1)! ways. So, the number of permutations, in this case, is (n – 1)! (in the case of linear permutations, the number is n!).

Arrangements of beads in a garland are also a circular permutation. But a garland can be turned upside down. So, the two orders of arrangements- clockwise and anti-clockwise are not distinguished in this case. Thus, with n beads in a garland, the number of arrangements will be (1/2) [(n – 1)!].

Notes:

(1) The number of permutations of n different things taken r at a time in which m particular things never occur would be obtained by arranging r objects out of the remaining n – m things, which can be done in ^n-mP_r ways. In this case, n – m ≥ r.

(2) The number of permutations of n different things taken r at a time in which m particular things always occur in ^rP_m x ^n-mP_r-m.

(3) The number of permutations of n different things taken r at a time in which m particular things are placed in m given places-

• in a definite order is ^n-mP_r-m
• in any order is ^n-mP_r-m . m!

(4) The number of permutations of n different things taken r at a time in which m particular things come together in a given order is (r – m + 1) . ^n-mP_r-m.

(5) In case of arrangments with respect to a round table, the number of permutations of n persons is n!.