0 ratings0% found this document useful (0 votes) 1K views5 pagesPNC Short Notes
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Formula Sheet
Permutation and Combination
INTRODUCTION
‘The present chapter can be given the name as
counting techniques or counting without actual
counting. For example if we are interested in
counting the number of 9 digit numbers which
are divisible by 9, then it will take a lot of time to
count the number of such numbers, but by using
the techniques given in this chapter, this will be
easy enough to find the number.
‘The basis of all the techniques given in this
chapter are based on two fundamental principles
of counting namely addition and multiplication
principles. Using these principles, formulae for
number of ways of arrangements and selections
of different objects are derived.
FUNDAMENTAL PRINCIPLE OF COUNTING
Multiplication Principle: If an operation can be
performed in ‘nr’ different ways following which a
second operation can be performed in ‘n’ diferent
‘ways, then the two operations in suecession can be
performed in m x n ways, This can be extended
to any finite number of operations.
PERMUTATION
Definition : Each of the different arrangements
which can be made by taking some (or all) of a
number of given things is called permutation.
Note :
Factorial Notation : The continued product of first
‘nm natural numbers is generally written as n! and
is read as factorial mi.
ml =n(n— In 2)3.21
Some Important Properties
@ nl=n(n-1)!
(ii) (2n)! =2"- nl [1-3-5-7..-Qn- 1]
(iijol= = 1
(iv) factorial of negative integers are not defined
Arrangement of » different things
‘The number of permutations of n different things
taken all ata time = "P, = n!
Meaning and value of "P,
‘The number of permutations of » different things,
taken r at a time is denoted by "P, or P (1,1).
np, -
(n-
n(n 1) (12)
n, then "C, = 0.
"G (srsn)
="C,= "C= 0
(i) "G4", ="*C,
©) "C=", 3 x=yorxty=n
Wn" =r "Gy
(vii)If m is even then the greatest value of "CG, is
"Cua
(viii) If m is odd then the greatest value of "C, is
Selection from Distinct objects
‘The number of ways (or combinations) of
different things selecting at least one of them is
MCL 4 "Cy + "Cyt a tC = 2" = 1
Selection from Identical Objects
1. The number of ways of selecting r (r »
» Pg ae distinct primes and ay, dy, .. dy are
non negative integers. px, then number of divisors
(a, +1) which
ip
of N are (a; + 1) (a; + 1).
includes 1 and N also.
Note : All the divisors excluding 1 and N are
called proper divisors.
(b) Sum of divisors
‘The sum of the divisors of N
= (1+ pt Pit + pH (Lt pat Pat
oot PB) vee (Lt Pe + De tm + BED
pitten potlr piel
Pi Pr Pe
(©) Number of ways in which N can be resolved
as a product of two factors
‘The number of ways of putting N as a product
of two natural numbers is,
FG, 40 (0, Vo (4+ 0 AEN not a
perfect square, If N is a perfect square then
this aye) 4a Dn Ge ¥ DT
(d) Number of ways in which a composite
number N can be resolved into two factors
Which are relatively prime or co-prime.
Number of ways = 2""' where nis the number
of different prime factors in N.
CIRCULAR PERMUTATIONS
Arrangements round a circular table :
Consider five persons A, B, C, Dand E to be seated
on the circumference of a circular table in order
(which has no head). Now, shifting A, B,C, D and
E one position in anticlockwise direction we will
set arrangements a fallow
Coo.
ai a
OOo
ww) ic)
‘We see that arrangements in all figures are same.
The number of circular permutations
of n different things taken all at a time is
—t = (n ~ 1)}, if clockwise and anticlockwise
orders are taken as different,
Formation of necklace/garland using beads/
flowers (Ring permutation)
Consider five beads A, B, C, D and E ina necklace
or five flowers A, B, C, D and E in a garland etc.
If the necklace or garland on the left is turned
over we obtain the arrangement on the right, i.,
anticlockwise and clockwise order of arrangements
are not different.
a
Thus, the number of circular permutations
of ‘n’ different things taken all at a time is
1
<(n ~ 1)}, if clockwise and anticlockwise orders
2! ! is
are taken as not different.
Number of circular permutations of ‘n°
things taken ‘r at a time.
Case I: If clockwise and anticlockwise orders are
taken as different, then the required number of
circular permutation = ("P,) |r.
Case I: If clockwise and anticlockwise orders
are taken as same, then the required number of
circular permutations = ("P,) / (2r)
different
DIVISION INTO GROUPS
Different number of objects in each group
‘The number of ways in which 1 distinct objects
can be split into r groups containing respectively
‘S115, 5, Objects, where 5; #5;, for ij, is given
7 stg!
Same number of objects in some group
If k of the numbers among 51, S95. » 5, are
equal, then the required number of ways is
A
Sls 1K
For example if36 distinet objects are to be divided
among 9 groups such that four groups have 2
objects each, three groups have 5 objects each and
remaining two groups having 6 and 7 objects then
the required number of ways
oe
(ant a1@p?- 31-6! 7 DISTRIBUTION AMONG PERSONS.
“The number of ways in which n distinct objects can
be distributed among r persons in a required way
= number of ways of dividing m distinct objects
in r-groups in the required way x
For example if 36 distinct objects are to be
divided among 9 persons such that four of the
persons are getting 2 objects each, three of
the persons are getting 5 objects each and the
remaining two persons are getting 6 and 7
‘objects, then the number of ways of doing so is
36!
(21)* -41(51)? -31- 61-71
EXPONENT OF PRIME NUMBER (p) IN nt
Let p bea given prime and n is any positive integer,
then maximum power of p present in n! is
(eh{sHS Boe (ofeenne te
‘greatest integer function, ‘The proof of the above
x9!
formula can be obtained using the fact that [2]
‘gives the number of integral multiples of min 1, 2,
~=- 11 for any positive integers n and m. The above
formula does not work for composite numbers.
For example, if we have to find the maximum
power of 6, present in 321, then the answer is not
Gita
multiples of 6 in 1, 2, ... 32s and 6 can be obtained
‘on multiplying 2 by 3 also. Hence for the required
number, we find the maximum powers of 2 and
3 (say r and s) present in 32!. Using the above
formula r= 31 and s = 14, Hence 2 and 3 will be
combined (to form 6) 14 times. Thus maximum
power of 6 present in 32! is 14.
PRINCIPLE OF INCLUSION AND EXCLUSION
If Ay, Apso» » Ay, are mt sets and n(S) denotes the
number of elements in the set S, then
{Ua} Soao- 3 #anane .
daa}
kel
5, as Sis the number of integral
yy
ich cigci,sm
Note that if xe [J Ag . then x belongs to atleast
ke
one of Ay SKS mi.
DE-ARRANGEMENT
‘As another application of the principle of inclusion
and exclusion, number of dearrangement of
objects (number of ways in which n numbered
balls (from 1 to n) can be placed in n numbered
boxes (from 1 to 1), one in each box, so that no
ball goes to its corresponding numbered box) is
a
sven tr
Also Dy = (11~ 1) [Dyes + Dy-al
MULTINOMIAL THEOREM AND
APPLICATION
Consider the equation x, +x) + .. +%,=, where
S50; 3 45 by 3) € T31=1, 2s Fs In order to
find the number of solutions ofthe given equation
satisfying the given conditions we observe that the
rhumber of solutions is the same as the coefficient
of x" in the product
ith gt a hh) x
ITS
(ath ee
(alt ae*lag x2"? ag glo) x
(x xB ea)
a,42 4,
hg eg abr)
x(a ex
For example, if we have to find the number
‘of non negative integral solutions of x, + x) +
+x, = 1 then as above the required number is
the coefficient of x" in
taM)il sate. tx")
(0 ta! +. +x") brackets)
Coefficient of x" in (l+x4+x°+..42°)"
Coefficient of x" in (1+ x42? +..."
Coefficient of x" in (1 ~ x)"
Coefficient of x" in
[rs(oneae
(sate
= Coefficient of x" in
ete Gta OP
meric Note : If there are / objects of one kind, m objects
of second kind, n objects of third kind and so ons
then the number of ways of choosing r objects
ut of these objects is the coefficient of x” in the
expansion of
(exe tate tx) Dette tx)
(txt tte).
Further if one object of each kind is to be included,
then the number of ways of choosing r objects
out of these objects is the coefficient of x” in the
expansion of
(etext ta) (etre tte")
(Eee eee)
and the number of possible permutations of r
objects out of these objects is the coefficient of
2 ry,
nike le
wa
While applying it, we use the coefficient of x’ in
(= ais IC or IG,
(@ Number of non-negative integral solution
of equation xy+x;+...+x,=n is "7 'C, or
mre
Gi) Number of positive integral solution of
equation x 4.4) ta tape Is "IC, , oF
nace
