Each of the different arrangement which ccan be made by taking some or all of a number of things is called a permutation.
The number of ways of arranging n distinct object in a row taking r (0≤r≤n) at a time is denoted by P(n;r) or ^{n}P_{r}.
Important results on Permutation
1. The number of permutations of n different things taken r at a time, allowing repetitions is n^{r}.
2. The number of permutations of n different things taken r at a time is ^{n}P_{n}=n!.
3. The number of permutations of n things taken all at a time, in which p are alike of one kind, q are alike of second kind an r are alike of thir kind and rest are different is
Permutations when any elements are not distinct
Suppose we have to find the number of ways of rearranging the letters of the word ROOT. In this case, the letters of the word are not all different. There are 2 Os, which are of the same kind.
Let us treat, temporarily, the 2 Os as different, say, O_{1}and O_{2}. The number of permutations of 4-different letters, in this case, taken all at a time is 4!. Consider one of these permutations say, RO_{1}O_{2}T. Corresponding to this
permutation,we have 2! permutations RO_{1}O_{2}T and RO_{2}O_{1}T which will be exactly the same permutation if O_{1}and O_{2}are not treated as different, i.e., if O_{1}and O_{2}are the same O at both places.
Therefore, the required number of permutations =4!/2!=3×4=12.
Permutations when O_{1},O_{2} are different | Permutations when O_{1},O_{2} are the same O. | |
---|---|---|
RO_{1}O_{2}T RO_{2}O_{1}T |
–> | ROOT |
TO_{1}O_{2}R TO_{2}O_{1}R |
–> | TOOR |
RO_{1}TO_{2} RO_{2}TO_{1} |
–> | ROTO |
TO_{1}RO_{2} TO_{2}RO_{1} |
–> | TORO |
RTO_{1}O_{2} RTO_{2}O_{1} |
–> | RTOO |
TRO_{1}O_{2} TRO_{2}O_{1} |
–> | TROO |
O_{1}O_{2}RT O_{2}O_{1}RT |
–> | OORT |
O_{1}RO_{2}T O_{2}RO_{1}T |
–> | OROT |
O_{1}TO_{2}R O_{2}TO_{1}R |
–> | OTOR |
O_{1}RTO_{2} O_{2}RTO_{1} |
–> | ORTO |
O_{1}TRO_{2} O_{2}TRO_{1} |
–> | OTRO |
O_{1}O_{2}TR O_{2}O_{1}TR |
–> | OOTR |
Let us now find the number of ways of rearranging the letters of the word INSTITUTE. In this case there are 9 letters, in which I appears 2 times and T appears 3 times.
Temporarily, let us treat these letters different and name them as I_{1},I_{2},T_{1},T_{2},T_{3}.
The number of permutations of 9 different letters, in this case, taken all at a time is 9!. Consider one such permutation, say, I_{1}NT_{1}SI_{2}T_{2}UET_{3}. Here if I_{1},I_{2}are not same and T_{1},T_{2},T_{3}are not same, then I_{1}I_{2}can be arranged in 2! ways and 4,T_{2},T_{3}can be arranged in 3! ways. Therefore, 2!×3! permutations will be just the same permutation corresponding to this chosen permutation I_{1}NT_{1}SI_{2}T_{2}UET_{3}. Hence, total number of different permutations will be 9!/2!3!.
We can state (without proof) the following theorems:
Theorem 1: The number of permutations of n objects, where p objects are of the same kind and rest are all different =n!/em>p!.
In fact, we have a more general theorem.
Theorem 2: The number of permutations of n objects, where p_{1}objects are of one kind, p_{2}are of second kind, …, p_{k}are of em>k^{th} kind and the rest, if any, are of different kind is
solution: Here, there are 9 objects (letters) of which there are 4A’s, 2L’s and rest are all different.
Therefore, the required number of arrangements
solution: Total number of discs are 4+3+2=9. Out of 9 discs, 4 are of the first kind (red), 3 are of the second kind (yellow) and 2 are of the third kind (green).
Therefore, the number of arrangements
9!/(4!3!2!)=1260
Example 3: Find the number of arrangements of the letters of the word
INDEPENDENCE. In how many of these arrangements,
(i). do the words start with P
(ii). do all the vowels always occur together
(iii). do the vowels never occur together
(iv). do the words begin with I and end in P?
solutions: There are 12 letters, of which N appears 3 times, E appears 4 times and D appears 2 times and the rest are all different. Therefore
The required number of arrangements
(i). Let us fix P at the extreme left position, we, then, count the arrangements of the remaining 11 letters. Therefore, the required number of words starting with P are
(ii). There are 5 vowels in the given word, which are 4 Es and 1 I. Since, they have to always occur together, we treat them as a single object [EEEEI] for the time being. This single object together with 7 remaining objects will account for 8 objects. These 8 objects, in which there are 3Ns and 2 Ds, can be rearranged in 8!/3!2! ways. Corresponding to each of these arrangements. the 5 vowels E,E,E,E and I can be rearranged in 5!/4! ways. Therefore, by multiplication principle the required number of arrangements
(iii) The required number of arrangements
= the total number of arrangements (without any restriction) – the number of arrangements where all the vowels occur together.
(iv). Let us fix I and P at the extreme ends (I at the left end and P at the right end). We are left with 10 letters.
Hence, the required number of arrangements
If the different permutations of all the letter of the word EXAMINATION are listed as in a dictionary, how many words are there in list before the first word starting with E?
solution:
In the given word EXAMINATION, there are 11 letters out of which, A, land N appear 2 times and all the other letters appear only once.
The words that will be listed before the words starting with E in a dictionary will be the words that start with A only.
Therefore, to get the number of words starting with A, the letter A is fixed at the extreme left position, and then the remaining 10 letters taken all at a time are rearranged.
Since there are 2 Is and 2 Ns in the remaining 10 letters,
Number of words starting with A
Thus, the required numbers of words is 907200.
Example 5:
In how many of the distinct permutations of the letters in MISSISSIPPI do the four I’s not come together?
solution:
In the given word MISSISSIPPI, I appears 4 times, S appears 4 times, P appears 2 times, and M appears just once.
Therefore, number of distinct permutations of the letters in the given word
There are 4 Is in the given word. When they occur together, they are treated as single object [IIII] for the time being. This single object together with the remaining 7 objects will account for 8 objects.
These 8 objects in which there are 4 Ss and 2 Ps can be arranged in 8!/4!2! ways i.e., 840 ways.
Number of arrangements where all Is occur together =840.
Thus, number of distinct permutations of the letters in MISSISSIPPI in which four Is do not come together =34650-840=33810.
shorter solution:
Here, number of letters n=11. Number of ‘I’, p=4. Number of ‘S’, q=4. Number of ‘P’, r=2. Number of ‘M’, s=1
This is the formula for counting the number of permutations
If all 4 ‘I’ come together, they must be counted to one. So, number of permutations having all ‘I’ come together is equal to
Hence, required number of ways =34650-840=33810.
Example 6:
In how many ways can the letters of the word ASSASSINATION be arranged so that all the S’s are together?
solution:
In the given word ASSASSINATION, the letter A appears 3 times, S appears 4 times, I appears 2 times, N appears 2 times, and all the other letters appear only once. Since all the words have to be arranged in such a way that all the Ss are together, SSSS is treated as a single object for
the time being. This single object together with the remaining 9 objects will account for 10 objects.
These 10 objects in which there are 3 As, 2 Is, and 2 Ns can be arranged in 10!/(3!2!2!)
ways. Thus, Required number of ways of arranging the letters of the given word =10!/(3!2!2!)=151200.
Example 7:
In how many ways can the letters of the word PERMUTATIONS be arranged if the
(i) Words start with P and end with S,
(ii) Vowels are all together,
(iii) There are always 4 letters between P and S?
solutions:
In the word PERMUTATIONS, there are 2 Ts and all the other letters appear only once.
(i) If P and S are fixed at the extreme ends (P at the left end and S at the right end), then 10 letters are left.
Hence, in this case, required number of arrangements
(ii) There are 5 vowels in the given word, each appearing only once.
Since they have to always occur together, they are treated as a single object for the time being.
This single object together with the remaining 7 objects will account for 8 objects.
These 8 objects in which there are 2 Ts can be arranged in 8!/2! ways.
Corresponding to each of these arrangements, the 5 different vowels can be arranged in 5! ways.
Therefore, by multiplication principle, required number of arrangements in this case
(iii) The letters have to be arranged in such a way that there are always 4 letters between P and S.
Therefore, in a way, the places of P and S are fixed. The remaining 10 letters in which there are 2 Ts can be arranged in 10!/2! ways.
Also, the letters P and S can be placed such that there are 4 letters between them in 2×7=14 ways.
Therefore, by multiplication principle, required number of arrangements in this case