Get the Knowledge that sets you free...Science and Math for K8 to K12 students

Login / Register

Login to your account

Email
Password
×

Warning

Please Login to Read More...

Permutations and Combinations

The Counting Principle

Fundamental principle of counting (multiplication rule): If a first operation can be performed in 'p' ways and a second operation can be performed in 'q' ways, then the two operations together can be performed in 'p × q' ways. For example, if a first operation can be performed in 4 ways and a second operation can be performed in 5 ways, then the two operations together can be performed in 4 × 5 = 20 ways.

The above principle can be extended to the case in which the different operations can be performed in p, q, r, s, ..... ways. In this case, the number of ways of performing all the operations together would be p × q × r × s ..... ways. For example, if four different operations can be performed in 2, 3, 4 and 5 ways, then the four operations together can be performed in 2 × 3 × 4 × 5 = 120 ways.

Fundamental principle of counting (addition rule): If there are two assignments such that they can be performed independently in p and q ways respectively, then either of the two assignments can be performed in (p + q) ways. For example, if there are two assignments such that they can be performed independently in 4 and 5 ways respectively, then either of the two assignments can be performed in 4 + 5 = 9 ways.

Factorial Notation

The product of ‘n’ consecutive positive integers beginning with 1 is denoted by n! or and read as ‘factorial n’ or ‘n factorial’. Thus,
n! = 1 . 2 . 3 . . . . . (n – 1)n
    = n(n – 1) . . . . . 3 . 2 . 1.

Points to remember
• When ‘n’ is a negative integer or a fraction, n! is not defined.
• The factorial of 0, i.e., 0! = 1.
• n! = n(n – 1)!.
• (2n)! = 2n . n![1 . 3 . 5 . . . . (2n – 1)].

     

Exponent of prime p in n!

Let p be a prime number and n be a positive integer.
Then, the last integer amongst 1, 2, 3, ...., (n – 1), n which is divisible by p is p
where denotes the greatest integer less than or equal to n/p.

For example,

Let Ep(n) denote the exponent of the prime p in the positive integer n. Then,
where s is the largest positive integer such that ps ≤ n < ps + 1

Flash is Not Installed in Your System. Please Click here to Install. Close
Java is Not Installed in Your System. Please Click here to Install. Close