Ch. 8 Permutations and Combinations Revision Points - 1

1. Factorial

Factorial: the continued product of first n natural numbers is called the “n factorial” and is denoted by n! or

i.e. n! = 1*2*3…*(n-1)*n

4! = 1*2*2*4

n! is defined for positive integers only.

0! is defined as 1.

n! = n*(n-1)!


2. Exponent of prime number p in factorial of n (n!)

The exponent of prime number of 3 in 100! is 48.
It means 100! is divisible by 3⁴⁸

How do you find it?
Let p be a prime number and n be a positive integer. Then find the last integer in the sequence 1,2,…,n which is divisible by p.
Express this integer as [n/p]p.
[n/p] denotes the greatest integer less than or equal to n/p

In case of 3 (p) and 100 (n); [n/p] is 33 and n/p is 33 and 1/3.

Let E_p(n) denote the exponent of the prime p in the positive integer n. Then,


E_p(n!) = E_p(1.2.3…(n-1).n)

This will be equal to E_p(p.2p.3p…[n/p]p)
= [n/p]+ E_p(1.2.3...[n/p])

This process continues and we get the answer

E_p(n!) = [n/p] + [n/p²]+…+[n/p^s]
Where s is the largest positive integer such that p^s≤n≤p^s+1

Hence applying the formula to find exponent of prime 3 in 100!

E₃(100!) = [100/3] + [100/3²] + [100/3³] + [100/3⁴]
= 33+11+3+1 = 48

Note: remember the meaning of notation [100/3] or [n/p]



Fundamental principle of multiplication

If there are two jobs such that one of them can be completed in m ways, and when it has been completed in any one of these m ways, second job can be completed in n ways, then the two jobs in succession can be completed in m*n ways.

Fundamental principle of addition

If there are two jobs such that they can be performed independently in m and n ways respectively, then either of the two jobs can be performed in (m+n) ways.


Each of the arrangement which can be made by taking some or all of a number of things is called a permutation.



Theorem 1

Let r and n be positive integers such that 1≤r≤n. then the number of all permutations of n distinct things taken r at a time is given by

n(n-1)(n-2)…(n-(r-1))

Notation: Let r and n be positive integers such that 1≤r≤n. then the number of all permutations of n distinct things taken r at a time is denoted by the symbol P(n,r) or ⁿ C_r.

Then P(n,r) = ⁿ C_r = n(n-1)(n-2)…(n-(r-1))


Theorem 2

P(n,r) = ⁿ C_r = n!/(n-r)!

Theorem 3

The number of all permutations of n distinct things taken all at a time is n!.

Theorem 4

0! = 1


8.5 Permutations under certain conditions
Three theorems

Theorem 1
The number of all permutations of n different objects taken r at a time, when a particular object is to be always included in each arrangement is r.^n-1C_r-1

Theorem 2

The number of all permutations of n different objects taken r at a time, when a particular object is never taken in each arrangement is, ^n-1C_r-1

Theorem 3

The number of all permutations of n different objects taken r at a time, when two specified objects always occur together is 2!(r-1) ^n-2C_r-2

Revision Points (Text R.D. Sharma)

8.6 Permutations of Objects not all Distinct

Theorems and Formulas

Theorem
The number of mutually distinguishable permutations of n things, taken all at a time, of which p are alike of one kind, q alike of second such that p+q = n, is

n!/p!q!


Formulas based on the above theorem

1. The number of mutually distinguishable permutations of n things, taken all at a time, of which p1 are alike of one kind, p2 alike of second,…, pr alike of of rth kind such that p1+p2+…pr = n, is

n!/p1!p2!…pr!

2. The number of mutually distinguishable permutations of n tings, of which p are alike of one kind, q alike of second and remaining all are distinct is
n!/p!q!

3. suppose there are r things to be arranged, allowing repetitions. Let further p1,p2,…,pr be the integers such that the first object occurs exactly p1 times, the second occurs exactly p2 times, etc. Then the total number of permutations of these r objects to the above condition is

(p1+p2+…+pr)!/p1!p2!…pr!


8.7 Permutations when Objects can Repeat
Theorem
The number of permutations of n different things, taken r at a time, when each may be repeated any number of times in each arrangement is n² .

8.8 Circular Permutations
If we arrange objects along a closed curve for example a circle, the permutations are known as circular permutations. In a circular permutation, we have to consider one object as fixed and the remaining are arranged as in case of linear arrangement.

Linear arrangement is arrangement in a row.

Theorem
The number of circular permutations of n distinct objects is (n-1)!.

Anti-clock wise and clockwise order of arrangements are considered as distinct permutations in the above theorem.

If the anticlockwise and clockwise order is not distinct as in case of a garland which can be turned over easily, the number of distinct permutations will be ½ (n-1)!..



_{Updated  10 Jan 2016, 7 June 2008}