Permutations and Combinations Concepts for CAT

In P&C (Permutation and Combination), it is more important to understand the problem than to know how to solve it. This is because the task is to figure out how the problem is to be solved, while the calculation part is too easy to worry about. Even if you do not know the formula or property, you can still get the answer you need by being creative, clever, and artistic. As a business manager or team leader, it is your job to set up events and choose the best people and tools, so why do not you start right now.

Since it is a very logical part, it is one of the ones that people who set the questions for competitive tests like to use the most. About 1-3 questions from this chapter will come up in almost every CAT session/slot. Other tests, like the XAT and IIFT, also ask about two to four problems from this chapter.

Counting

[Click Here for Previous Year CAT Questions]

If one operation can be done in m ways and a second operation can be done in n ways for each way the first operation can be done, then the two operations can be done together in (m x n) ways. If a third operation can be done in p ways after two operations have been done in any of the (m x n) ways, then the three operations can be done together in (m x n x p) ways, and so on.

Permutations

[Click Here for Previous Year CAT Questions]

You take all or some of a set of finite things and arrange them in different ways. Each of these different ways is called a permutation. In Permutation, how things are put together is very important.

Permutation means selection and arrangement both, while Combination means only selection.

Types of Permutations

• A permutation is said to be a Linear Permutation if the objects are arranged in a line. A linear permutation is simply called as a permutation.
• A permutation is said to be a Circular Permutation if the objects are arranged in the form of a circle.

• The number of (linear) permutations that can be formed by taking r things at a time from a set of n distinct things is denoted by ⁿP_r or P(n, r), for every 1 ≤ r ≤ n.
• ⁿP_r =n(n−1)(n−2)(n−3)….....(n−r+1)= \(\frac{n!}{(n-r)!}\)

Permutations of n Different Things

1. Number of permutations of n different things taken all at a time = ⁿP_n = n!
2. No of permutations of n different things taken r at a time= ⁿP_r = \(\frac{n!}{(n-r)!}\)
3. Number of permutations of n different things taken at Most r at a time= ⁿP + ⁿP + ⁿP +...+ ⁿP_r
4. Number of permutations of n different things taken at least r at a time = ⁿP_r +ⁿP_r+1 +ⁿP_r+2 +...+ⁿP_n
5. Number of permutations of n different things taken r at a time, when one particular thing always occurs = r ⋅ ( ^{n −1}P_{r − 1} )
6. Number of permutations of n different things taken r at a time, when one particular thing never occurs = ^{n −1}P_r
7. Number of permutations of n different things taken r at a time, when k particular things, always occur = (^rP_k )(^{n −k} P_{r − k} )
8. Number of permutations of n different things taken r at a time, when k particular things never occur = ^{n −k} P_r
9. Number of permutations of n different things, taken all at a time, when m specified things always come together = m!(n−m+1)!
10. Number of permutations of n different things, taken all at a time, when m specified things never come together = n! − [m!(n − m +1)!]

Permutations of n Things Not All Different

1. Number of ways to arrange n things when p of them are all the same and the rest are all different = \(\frac{n!}{p!}\)
2. Number of ways n things can be put together when p things are the same of one kind, q things are the same of another kind, r things are the same of another kind, and the rest, if any, are different from p, q, and r. = \(\frac{n!}{p!q!r!}\)
3. Number of ways n things taken all at once when p₁ things are alike of one kind, p₂ things are alike of second kind, p₃ things are alike of third kind,... p_r things are alike of r^th kind, and the rest, if any, are different from p₁, p₂, p₃,..., p_r, then the number of permutations of n things = \(\frac{n!}{p_1! p_2!........p_r!}\)

Permutations Where Repetitions are Allowed

1. Number of permutations of n different things taken exactly r at a time, where each thing can be repeated any number of times in each order = n^r
2. Number of different things that can happen at any given time, and the number of times each thing can happen in each order. = n+n² +n³ +...+n^r = \(\frac{n(n^r-1)}{(n-1)}\)
3. Number of permutations of n different things taken at least r at a time, when each may be repeated any number of times in each arrangement = n^r +n^r+1 +n^r+2 +….+nⁿ = \(\frac{n^r(n^{(n-r+1)}-1)}{n-1}\)

Circular Permutations

1. Number of circular permutations of n different things taken all at a time = (n −1)!
2. Number of circular permutations of n different things taken all at a time in one direction (either clock-wise or anti-clock-wise) = \(\frac{(n-1)!}{2}\)
3. Number of circular permutations of n different things taken r at a time = \(\frac{^np_r}{r}\)
4. Number of circular permutations of n different things taken r at a time in one direction (either clock-wise or anti-clock-wise) = \(\frac{^np_r}{2r}\)

Combinations

[Click Here for Previous Year CAT Questions]

number of combinations of n dissimilar things taken r at a time is denoted by ⁿC_r or C(n,r) or (ⁿ_r)

 ⁿ C_r = \(\frac{n!}{r!\ (n-r)!}\)  C denotes the combination and r ≤ n

Essential Properties

• ⁿC_r = \(\frac{p_r}{r!}\)
• ⁿ C₀ = ⁿ C_n = 1
• ⁿ C_r = ⁿ C_n-r ( 0≤r≤n)
• ⁿ C_r = ⁿ C_y \(\Leftrightarrow\) x+y =n or x = y
• ⁿC_r−1 +ⁿC_r =ⁿ⁺¹C_r
• If n is even, the greatest value of ⁿ C_r = ⁿC_m where m = n/2
• If n is odd, the greatest value of ⁿC_r = ⁿC_m where m=  \(\frac{(n \mp 1)}{2}\)
• ^rC_r +^r+1C_r +^r+2C_r +…....+ⁿC_r = ⁿ⁺¹C_r+1 ; r ≤ n
• ⁿC₀ + ⁿC₁ +ⁿ C₂ + ⁿC₃ +…...+ ⁿC_n = 2ⁿ
• ⁿC₁ +ⁿC₂ +ⁿC₃ +…...+ⁿC_n = 2ⁿ −1
• ⁿC₀ +ⁿC₂ +ⁿC₄ +…....= 2ⁿ⁻¹
• ⁿC₁ +ⁿC₃ +ⁿC₅ +….....= 2ⁿ⁻¹

Combination of n Different Things

1. Number of ways that n different things can be put together when x things always happen = ^{n − x}C_{r − x}
2. Number of ways n different things can happen at the same time when x things never happen = ^{n − x} C _r
3. Number of ways that n different things can be put together so that x things always happen and y things never happen = ^{n −x−y}C_r−x
4. Number of ways n different things can be put together r at a time when x things can not be put together in any pick = ^n-xC _{r −x}
5. Number of ways of selections of zero or more things from a group of n distinct things = ⁿC₀ +ⁿC₁ +ⁿC₂ +ⁿC₃ +...+ⁿC_n =2ⁿ
6. Number of ways of selections of one or more things from a group of n distinct things = ⁿC₁ +ⁿC₂ +ⁿ C₃ +...+ⁿC_n =2ⁿ −1 (ⁿC₀ =1)

Combination of n Identical Things

1. Number of ways of selections of r things from a group of n identical things = 1.
2. Number of ways of selections of at most r things from a group of n identical things = r + 1
3. Number of ways of selections of at least r things from a group of n identical things = (n − r) +1
4. Number of ways of selections of at least one thing from a group of n identical things = n
5. Number of ways of selections of zero or more things from a group of n identical things = n + 1

Combination of n Things Not All Different

1. Number of ways of selection of zero or more things out of (p+q+r+...)things,ofwhich parealikeofone kind, q are alike of second kind, r are alike of third kind,andsoon=[(p+1)(q+1)(r+1)...]
2. Number of ways of selection of at least one thing out of (p+q+r+...)things,ofwhich parealikeofonekind, q are alike of second kind, r are alike of third kind, and so on =[(p+1)(q+1)(r+1)K]−1
3. Number of ways of selection of zero or more things from p identical things of one kind, q identical things of second kind, r identical things of third kind, and from remaining n things which are all different = [( p +1) (q +1) (r +1)2ⁿ ]
4. Number of ways of selection of at least one thing from p identical things of one kind, q identical things of second kind, r identical things of third kind, and from remaining n things which are all different =[{(p+1)(q+1)(r+1)2ⁿ}−1]
5. The number of ways of choosing k objects, from
   p objects of one kind, q objects of second kind, and so on, is the coefficient of x^k in the expansion (1+x+x² +K+x^p)(1+x+x² +K+x^q)...
6. The number of ways of choosing k objects from
   p objects of one kind, q objects of second kind, and so on, such that one object of each kind must be included is the coefficient of x^k in the expansion (x+x² +....+x^p)(x+x² +K+x^q)
7. The number of ways in which r things can be selected from a group of n things of which p are identical is ∑^{n − p} C_r ; if r ≤ p
8. The number of ways in which r things can be selected from a group of n things of which p are identical is ∑^n−pC_r ;if r > p

Combination of Contiguous Things

(A) Linear Combination

1. Number of selections of k consecutive things out of n things in a row=(n−k +1)
2. Number of selection of k things out of n things in a row, such that no two of the selected objects are next to each other= ^n−k+1C_k

(B) Circular Combination

Number of selections of k consecutive things out of n things in a circle

 n, when k < n

 1, when k = n