Combinations, Group Division and Derangements | NIMCET

Quick answer: A combination is a selection where order does not matter: $^nC_r = \frac{n!}{r!(n - r)!}$ . Key properties are $^nC_r = {}^nC_{n - r}$ and $^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r$ . Dividing $m + n$ distinct objects into groups of m and n ( $m \ne n$ ) can be done in $\frac{(m + n)!}{m!\,n!}$ ways. The number of derangements of n objects (none in its original place) is $D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}\right)$ .

This follows permutations: linear and circular arrangements.

nCr and its properties

Property	Statement
Formula	$^nC_r = \frac{n!}{r!(n - r)!}$
Link to permutations	$^nP_r = r! \cdot {}^nC_r$
Symmetry	$^nC_r = {}^nC_{n - r}$
Pascal's rule	$^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r$
Equal values	$^nC_x = {}^nC_y \Rightarrow x = y$ or $x + y = n$
Sum	$\sum_{r=0}^{n}{}^nC_r = 2^n$
Largest value	At $r = \frac{n}{2}$ (n even) or $r = \frac{n \pm 1}{2}$ (n odd)

Selections with restrictions

Restriction	Count
k particular objects always included	$^{n - k}C_{r - k}$
k particular objects always excluded	$^{n - k}C_r$
At least one from n distinct	$2^n - 1$
From p alike, q alike, r alike (at least one)	$(p + 1)(q + 1)(r + 1) - 1$

Division into groups

Situation	Count
$m + n$ objects into groups of m and n ( $m \ne n$ )	$\frac{(m + n)!}{m!\,n!}$
2m objects into 2 equal groups (unlabelled)	$\frac{(2m)!}{2!\,(m!)^2}$
3m objects into 3 equal groups (unlabelled)	$\frac{(3m)!}{3!\,(m!)^3}$
Groups then given to distinct people	Multiply by the number of ways to assign groups

Identical objects into boxes

Situation	Count
n identical objects into r distinct boxes, empty allowed	$^{n + r - 1}C_{r - 1}$
Each box gets at least one	$^{n - 1}C_{r - 1}$
Non-negative solutions of $x_1 + \ldots + x_r = n$	$^{n + r - 1}C_{r - 1}$

Derangements

$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$

n	1	2	3	4	5
$D_n$	0	1	2	9	44

Geometry counting

Quantity (n points)	Count
Lines, no three collinear	$^nC_2$
Triangles, no three collinear	$^nC_3$
Diagonals of an n-sided polygon	$^nC_2 - n = \frac{n(n - 3)}{2}$
Lines when m of them are collinear	$^nC_2 - {}^mC_2 + 1$
Triangles when m are collinear	$^nC_3 - {}^mC_3$

Worked examples

Example 1: committee

A committee of 5 is chosen from 6 men and 4 women with at least 2 women. How many ways?

$^4C_2\,^6C_3 + {}^4C_3\,^6C_2 + {}^4C_4\,^6C_1 = 120 + 60 + 6 = 186$

Example 2: equal nCr values

If $^nC_8 = {}^nC_6$ , find $^nC_2$ .

$n = 14$ , so $^{14}C_2 = 91$ .

Example 3: group division

In how many ways can 12 different books be divided equally among 3 students?

$\frac{12!}{(4!)^3} = 34650$

(Groups are given to distinct students, so we do not divide by $3!$ .)

Example 4: identical objects

In how many ways can 10 identical balls go into 4 distinct boxes so that no box is empty?

$^9C_3 = 84$ .

Example 5: derangements

Four letters are placed in four addressed envelopes. In how many ways is every letter in a wrong envelope?

$D_4 = 24\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 12 - 4 + 1 = 9$ .

Summary table

Idea	Key result
$^nC_r$	$\frac{n!}{r!(n - r)!}$
Symmetry	$^nC_r = {}^nC_{n - r}$
Identical into boxes	$^{n + r - 1}C_{r - 1}$
Derangements of 4	9
Diagonals	$\frac{n(n - 3)}{2}$

Exam tips

"At least" questions: split into cases, or subtract the complement from the total.
In group division, divide by $k!$ only when equal-sized groups are unlabelled.
Memorise $D_3 = 2$ , $D_4 = 9$ , $D_5 = 44$ .

Practise with the NIMCET permutations and combinations PYQs, or see the NIMCET Algebra chapter.

Common mistakes

Using permutations when order does not matter.
Dividing by $k!$ for equal groups that go to distinct people.
Counting "at least one" as $2^n$ instead of $2^n - 1$ .
Forgetting collinear points when counting triangles.

Frequently Asked Questions

What is the formula for nCr?

ⁿCᵣ = n!/(r!(n − r)!).

If nCx = nCy, what can you conclude?

Either x = y or x + y = n.

How many ways can n identical objects go into r distinct boxes?

ⁿ⁺ʳ⁻¹Cᵣ₋₁ if boxes may be empty, and ⁿ⁻¹Cᵣ₋₁ if every box must get at least one.

What is a derangement?

An arrangement in which no object is in its original position. For 4 objects there are 9 derangements.

How many diagonals does a polygon with n sides have?

n(n − 3)/2.