Mathematics Permutations & Combinations

Fundamental Principle of Counting

`text(Multiplication principle : )`

If an operation can be performed in 'm' different ways, following which a second operation can be performed in 'n' different ways, then the two operations in succession can be performed in m x n ways. This can be extended to any finite number of operations.

Note: For AND : 'x' (multiply)

Illustration 1. A hall has 12 gates. In how many ways can a man enter the hall through one gate and come out through a different gate')

Solution. Since, there are 12 ways of entering into the hall. After entering into the hall, the man come out through a different gate in 11 ways. Hence, by the fundamental principle of multiplication, total number of ways is `12 x 11 = 132` ways.

`text(Addition principle : )`

If an operation can be performed in 'm' different ways and another operation, which is independent of the first operation, can be performed in 'n' different ways. Then, either of the two operations can be performed in (m + n) ways. This can be extended to any finite number of mutually exclusive operation.

Note : For OR : '+' (Addition)

Illustration 3. There are 25 students in a class in which 15 boys and 10 girls. The class teacher select either a boy or a girl for monitor of the class. In how many ways the class teacher can make this selection'?

Solution. Since, there are 15 ways to select a boy, so there are 10 ways to select a girl.
Hence, by the fundamental principle of addition, either a boy or a girl can be
performed in 15 + 10 = 25 ways.

`text(Some Important Properties :)`

`(i) n ! = n(n -1) ! = n(n -1)(n- 2)!`
`(ii) 0! = 1 ! = 1`
`(iii) (2n)! = 2^n n! [1 · 3 · 5 ... (2n - 1)]`
`(iv) (n!)/(r!) = n(n - 1)(n - 2) ... (r + 1) \ \ \ \ [r < n]`
`(v) (n!)/((n-r)!) = n(n- 1) (n- 2) ... (n- r + 1) \ \ \ \ [r < n]`
`(vi) =1/(n!) + 1/((n+1)!) = lambda/((n+2)!) `
(vii) If `x! = y! =>x= y` or `x= 0,y =1 ` or `x= 1,y = 0`

Exponent of prime p in n!

Exponent of prime p in n! is denoted by `E_p(n !)` , where pis prime number and n is a natural number. The last integer amongst 1, 2, 3, ... , (n -1), n which is divisible by p is `[n/p] p` , where [ ·] denotes the greatest integer function.

`therefore E_p(n!) = E_p(1.2.3...........(n-1).n)`

`= E_p(p.2p.3p..........(n-1)p.[n/p] p)`

[because the remaining natural numbers from 1 ton are not divisible by p]

`= [n/p] + E_p(1.2.3.............[n/p])`

Now, the last integer amongs `1, 2, 3, ... , [n/p]` which is divisible by p is

`[(n/p)/p] = [n/p^2],` Now , From Eq. (i) we get

`E_p(n!) = [n/p] + E_p(p,2p,3p,............,[n/p^2]p)`

[because the remaining natural numbers from 1 to `[ n/p]` are not divisible by p]

`therefore` `E_p(n!) = [n/p] + [n/p^2]+ E_p(1.2.3..............[n/p^2])`

Similarly, we get

`E_p(n!) = [n/p] + [n/p^2]+[n/p^3]+...............+[n/p^s]`

where, sis the largest natural number such that `p^s <= n < p^(s+1)`

`text(Note)` Number of zeroes at the end of `n! = E_5(n !)`

`text(.Illustration)` . Find the exponent of 3 in 100!.

`text(Solution)` In terms of prime factors 100! can be written as `2^a. 3^b. 5^c · 7^d.............`

Now, `b = E_s (100!) = [100/3] + [100/3^4] + [100/3^3] + [100/3^4] + ...............`

`= 33 + 11 + 3 + 1+ 0 + .........= 48`

Divisibility Test

In decimal system all numbers are formed by the digits 0, 1, 2, 3, ... , 9. If `a b
c d e` is a five-digit number in decimal system, then we can write that.
`a b c d e = 10^4 ·a + 10^3 · b + 10^2 · e + 10 · d +e.`
Number a b c d e will be divisible
(1) by 2, if e is divisible by 2.
(2) by 4, if 2d + e is divisible by 4.
(3) by 8, if 4c + 2d + e is divisible by 8.
(4) by `2^t` , if number formed by last t digits is divisible by `2^t`

For example, Number 820101280 is divisible by `2^5` because 01280 1s
divisible by `2^5` .
(5) by 5, if `e = 0` or 5.
(6) by 5t, if number formed by last t digits is divisible by 51
.
For example, Number 1128375 is divisible by 53 because 37fi is divisible
by 53
.
(7) by 3, if a+ b + e + d + e (sum of digits) is divisible by 3.
(8) by 9, if a+ b + e + d + e is divisible by 9.
(9) by 6, if e = even and a + b + c + d + e is divisible by 3.
(10) by 18, if e = even and a+ b + c + d + e is divisible by 9.
(11) by 7, if abed- 2e is divisible by 7.
For example, Number 6552 is divisible by 7 because `655- 2 xx 2 = 651`
`= 93 xx 7` is divisible by 7.
(12) by 11, if `undersettext(Sum of digit at odd places)(\underbrace(a+b+c)) - undersettext(Sum of digit at even places)(\underbrace(b+d))`

is divisible by 11.
For example, Number 15222163 is divisible by 11 because
`(1 + 2 + 2 + 6) - ( 5 + 2 + 1 + 3) = 0` is divisible by 11.
(13) by 13, if abed + 4e is divisible by 13.
For example, Number 1638 is divisible by 13 because
`163 + 4 xx 8 = 195 = 15 xx 13` is divisible by 13.