Basic Principal of counting

Basic principle of counting

If one thing can be done in n1 different ways and second thing can be done in n2 different ways then the first thing followed by the second can be done in n1 n2 different ways.

Similarly, this can be extended for finite number of ways nk and then the total number of ways in which all things can be done in the given order is n1.n2. n3….nk.

Permutations

The different arrangements that can be made out of a given set of things, by taking some or all at a time are called their permutations. Thus ab and ba are two different permutations of the two letters a and b taking both at a time. The permutation of three letters a, b, c taken two at a time are ab, ba, ac, ca, bc, cb and the permutations of these three letters a, b, c taken all at a time are obviously abc, bca, cab, acb, cba, bac. The number of permutations of n different things taken r at a time is usually denoted by nPr or P(n, r).

The permutations of things all are different

The number of permutations of n different things taken r at a time is same as the number of different ways in which r places can be filled up by the n things.

The first place can be filled up in n ways, for any one of the n things can be put in it. When the first place has been filled up in any one of these n ways, the second place can be filled up in (n - 1) ways, for only of the remaining (n - 1) things can be put in it. Since each way of filling up the first place can be associated with each way of filling up the second place, first two places can be filled up in n(n - 1) ways.

When the first two places has been filled up in any one of these n(n - 1) ways, the third place can be filled up in (n - 2) ways, for these are now (n - 2)things left to fill up the third place. Each of this (n - 2) ways can be associated with each of the
n(n - 1) arrangements of the first two places. Hence, the first three places can be filled up in n(n - 1) (n - 2) ways.

Processing in this way and noticing that at any stage the number of factors is the same as the number of places filled up, the total number of ways in which r places can be filled up in







Permutation of things not all different

Let n things be represented by n letters and suppose p of them are a's, q of them are b's r of them are c's and the rest all different.

Let x be the required number of permutations. If the p a's are changed in to, p letters different from each other and from the rest, then these p letters can be arranged in P! ways. Hence if this change were made in each of x permutations, the number of permutation would become   x ´ p!

Similarly q b's be changed q letters different from each other and the rest, then these letters can be arranged in q: ways and the total numbers of permutations would now become x ´ p! ´ q!

Again, if r c's be changed into r letters different from each other and from the rest, the total numbers of permutations would similarly become x ´ p! ´q! ´ r!

But now, there are n different things and the permutations of n different things taken all at a time is n!.

             \ x ´ p! ´ q! ´ r! = n!