xSkill: notes, lectures and practice for CBSE and CSE

1.1 Two counting principles When a task is done in stages, multiply the choices at each stage. When the task can be finished in several independent ways, add the choices of those ways. The first rule handles arrangements where order matters in the sequence of decisions; the second handles alternatives such as choosing a route from two disjoint sets of options. A quick check before computing: decide whether the question asks for an arrangement, where order matters, or a selection, where order does not. Permutation counts arrangements; combination counts selections. Every wrong answer in this chapter usually begins with that choice going the wrong way.

1.2 Factorial and permutations The factorial of a natural number n is the product of the numbers from 1 to n, and by definition 0 factorial is 1. The factorial has the recursive property n factorial equal to n times (n minus 1) factorial, which is the workhorse for simplifying ratios such as 7 factorial by 5 factorial. The number of arrangements of n different objects taking r at a time without repetition is nPr, equal to n factorial divided by (n minus r) factorial. It also equals the product n(n minus 1) and so on down to (n minus r plus 1), which is the form to use when the product is small. Count Formula arrangements of n objects, r at a time, no repetition nPr = n! by (n minus r)! arrangements of n objects, r at a time, repetition allowed n to the power r arrangements of n objects when all are used n! arrangements of n objects with p1, p2, ... alike n! by (p1! p2! ...)

Count	Formula
arrangements of n objects, r at a time, no repetition	nPr = n! by (n minus r)!
arrangements of n objects, r at a time, repetition allowed	n to the power r
arrangements of n objects when all are used	n!
arrangements of n objects with p1, p2, ... alike	n! by (p1! p2! ...)

^{n} P_{r} = \frac{n !}{( n - r )!},^{n} P_{r} = n (n - 1) \dots (n - r + 1), 0! = 1

Permutation formula and factorial convention

1.3 Combinations A combination ignores order. The number of ways to choose r objects out of n different objects is nCr, equal to n factorial divided by r factorial times (n minus r) factorial. Every selection of r objects can be arranged internally in r factorial ways, so the link between the two counts is nPr equal to nCr times r factorial. Identity Meaning nCr = nC(n minus r) choosing r is the same as leaving out n minus r nCr plus nC(r minus 1) = (n plus 1)Cr Pascal rule for adding neighbouring choices nC0 plus nC1 up to nCn = 2 to the power n total number of subsets nPr = nCr times r! arrangement count from selection count Two standard shortcuts cover most exam wording. The number of ways with at least one of something is the total minus the number of ways with none. The number of arrangements where two specified objects are never adjacent is the total minus the arrangements where they are kept together as one block.

Identity	Meaning
nCr = nC(n minus r)	choosing r is the same as leaving out n minus r
nCr plus nC(r minus 1) = (n plus 1)Cr	Pascal rule for adding neighbouring choices
nC0 plus nC1 up to nCn = 2 to the power n	total number of subsets
nPr = nCr times r!	arrangement count from selection count

^{n} C_{r} = \frac{n !}{r ! ( n - r )!},^{n} P_{r} =^{n} C_{r} \cdot r!,^{n} C_{r} =^{n} C_{n - r}

Combination formula and its link to permutations

Exam

Before calculating, write one line saying whether order matters. An arrangement with distinct positions uses nPr; a committee or a hand of cards uses nCr. Marks are lost at the interpretation step far more often than at the arithmetic step.