PERMUTATION & COMBINATION
1. FUNDAMENTAL PRINCIPLE OF COUNTING (counting without actually counting):
If an event can occur in 'm' different ways, following which another event can occur in 'n' different ways, then the total number of different ways of
(a) Simultaneous occurrence of both events in a definite order is \(m\) \(× n\). This can be extended to any number of events (known as multiplication principle).
(b) Happening of exactly one of the events is \(m + n\) (known as addition principle).
2. FACTORIAL:
A Useful Notation \(: n != n ( n -1)( n -2) \ldots \ldots\). \(2.1\);
\(n !=n .(n-1) !\) where \(n \in W\)
\(0 !=1 !=1\)
\((2 n) !=2^{n} \cdot n ![1.3 .5 .7 \ldots \ldots . .(2 n-1)]\)
Note that :
(i) Factorial of negative integers is not defined.
(ii) Let \(p\) be a prime number and \(n\) be a positive integer, then exponent of \(p\) in \(n !\) is denoted by \(E _{ p }( n !)\) and is given by
\(E_{p}(n !)=\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^{2}}\right]+\left[\dfrac{n}{p^{3}}\right]+\ldots.\)
3. PERMUTATION:
(a) \({ }^{ n } P _{ r }\) denotes the number of permutations (arrangements) of \(n\) different things, taken \(r\) at a time \(( n \in N , r \in W , n \geq r )\)
\({ }^{ n } P _{ r }= n ( n -1)( n -2) \ldots \ldots\)\( \ldots \ldots( n - r +1)=\dfrac{ n !}{( n - r ) !}\)
(b) The number of permutations of \(n\) things taken all at a time when \(p\) of them are similar of one type, \(q\) of them are similar of second type, r of them are similar of third type and the remaining \(n -( p + q + r )\) are all different is \(: \dfrac{ n !}{ p ! q ! r !}\)
(c) The number of permutation of \(n\) different objects taken \(r\) at a time, when a particular object is always to be included is \(r ! \cdot{ }^{ n -1} C _{ r -1}\)
(d) The number of permutation of \(n\) different objects taken \(r\) at a time, when repetition be allowed any number of times is \(n \times n \times n \ldots \ldots \ldots \ldots\) r times \(= n ^{ r }\)
(e) (i) The number of circular permutations of \(n\) different things taken all at a time is \(;( n -1) !=\dfrac{{ }^{ n } P _{ n }}{ n }.\)
If clockwise & anti-clockwise circular permutations are considered to be same, then it is \(\dfrac{( n -1) !}{2}\).
(ii) The number of circular permutation of \(n\) different things taking \(r\) at a time distinguishing clockwise & anticlockwise arrangement is \(\dfrac{{ }^{ n } P _{ r }}{ r }\)
4. COMBINATION:
(a) \({ }^{ n } C _{ r }\) denotes the number of combinations (selections) of \(n\) different things taken \(r\) at a time, and \({ }^{ n } C _{ r }=\dfrac{ n !}{ r !( n - r ) !}=\dfrac{{ }^{ n } P _{ r }}{ r !}\) where \(r \leq n\) \(; n \in N\) and \(r \in W \cdot{ }^{ n } C _{ r }\) is also denoted by \(\left(\begin{array}{l} n \\ r \end{array}\right)\) or \(A _{ r }^{ n }\) or \(C ( n , r )\).
(b) The number of combination of \(n\) different things taking \(r\) at a time.
(i) when \(p\) particular things are always to be included \(={ }^{ n - p } C _{ r - p }\)
(ii) when p particular things are always to be excluded \(={ }^{ n - p } C _{ r }\)
(iii) when p particular things are always to be included and q particular things are to be excluded \(={ }^{ n - p - q } C _{ r - p }\)
(c) Given n different objects, the number of ways of selecting atleast one of them is, \({ }^{ n } C _{1}+{ }^{ n } C _{2}+{ }^{ n } C _{3}+\ldots \ldots .+{ }^{ n } C _{ n }=2^{ n }-1\). This can also be stated as the total number of non-empty combinations of \(n\) distinct things.
(d) (i) Total number of ways in which it is possible to make a selection by taking some or all out of \(p + q + r +\ldots \ldots\) things, where \(p\) are alike of one kind, q alike of a second kind, r alike of third kind & so on is given by : \((p+1)(q+1)(r+1) \ldots \ldots \ldots-1\).
(ii) The total number of ways of selecting one or more things from p identical things of one kind, q identical things of second kind, r identical things of third kind and \(n\) different things is \((p+1)(q+1)(r+1) 2^{n}-1\)
5. DIVISORS :
Let \(N=p^{a} \cdot q^{b} \cdot r^{c} \ldots \ldots\) where \(p, q, r \ldots \ldots . .\) are distinct primes & a, b, c....... are natural numbers then :
(a) The total numbers of divisors of \(N\) including \(1\) & \( N\) is \(=( a +1)( b +1)( c +1) \ldots \ldots\)
(b) The sum of these divisors is \(\left(p^{0}+p^{1}+p^{2}+\ldots+p^{a}\right)\) \(\left(q^{0}+q^{1}+q^{2}+\ldots+q^{b}\right)\left(r^{0}+r^{1}+r^{2}+\ldots+r^{c}\right) \ldots\)
(c) Number of ways in which \(N\) can be resolved as a product of two factors is
\(\dfrac{1}{2}(a+1)(b+1)(c+1) \ldots \ldots\) if \(N\) is not a perfect square
\(\dfrac{1}{2}[(a+1)(b+1)(c+1) \ldots \ldots+1]\) if \(N\) is a perfect square
(d) Number of ways in which a composite number \(N\) can be resolved into two factors which are relatively prime (or coprime) to each other, is equal to \(2^{ n -1}\) where \(n\) is the number of different prime factors in \(N\).
6. DIVISION INTO GROUPS AND DISTRIBUTION :
(a) (i) The number of ways in which \(( m + n )\) different things can be divided into two groups containing \(m \) & \(n\) things respectively is : \(\dfrac{(m+n) !}{m ! n !}(m \neq n)\).
(ii) If \(m=n\), then number of ways in which \(2 n\) distinct objects can be divided into two equal groups is \(\dfrac{(2 n) !}{n ! n ! 2 !} ;\) as in any one way it is possible to inter change the two groups without obtaining a new distribution.
(iii) If \(2 n\) things are to be divided equally between two persons then the number of ways \(=\dfrac{(2 n ) !}{ n ! n !(2 !)} \times 2 !\).
(b) (i) Number of ways in which \(( m + n + p )\) different things can be divided into three groups containing \(m , n \) & \(p\) things respectively is \(\dfrac{( m + n + p ) !}{ m ! n ! p !}, m \neq n \neq p\)
(ii) If \(m=n=p\) then the number of such grouping \(=\dfrac{(3 n) !}{n ! n ! n ! 3 !}\)
(iii) If 3n things are to be divided equally among three people then the number of ways in which it can be done is \(\dfrac{(3 n) !}{(n !)^{3}}\).
(c) In general, the number of ways of dividing \(n\) distinct objects into \(\ell\) groups containing p objects each ,m groups containing q objects each is equal to \(\dfrac{ n !}{( p !)^{\ell}( q !)^{ m } \ell ! m !}\)
Here \(\ell p + mq = n\)
(d) Number of ways in which \(n\) distinct things can be distributed to p persons if there is no restriction to the number of things received by them is \(p ^{ n }\)
(e) Number of ways in which \(n\) identical things may be distributed among p persons if each person may receive none, one or more things is \({ }^{ n + p -1} C _{ n }\).
7. DERANGEMENT :
Number of ways in which \(n\) letters can be placed in \(n\) directed envelopes so that no letter goes into its own envelope is
\(=n !\left[1-\dfrac{1}{1 !}+\dfrac{1}{2 !}-\dfrac{1}{3 !}+\dfrac{1}{4 !}-\ldots \ldots . .+(-1)^{n} \dfrac{1}{n !}\right]\)
8. IMPORTANT RESULT :
(a) Number of rectangles of any size in a square of size \(n \times n\) is \(\displaystyle \sum_{r=1}^{n} r^{3} \) & number of squares of any size is \(\displaystyle \sum_{r=1}^{n} r^{2} .\)
(b) Number of rectangles of any size in a rectangle of size \(n \times p\) \(( n < p )\) is \(\dfrac{ np }{4}( n +1)( p +1) \) & number of squares of any size is \(\displaystyle \sum_{r=1}^{n}(n+1-r)(p+1-r)\)
(c) If there are \(n\) points in a plane of which \(m (< n )\) are collinear :
(i) Total number of lines obtained by joining these points is \({ }^{ n } C _{2}-{ }^{ m } C _{2}+1\)
(ii) Total number of different triangle \({ }^{ n } C _{3}-{ }^{ m } C _{3}\)
(d) Maximum number of point of intersection of \(n\) circles is \({ }^{ n } P _{2}\) & \(n\) lines is \({ }^{ n } C _{2}\)
Comments
Post a Comment