Chapter 4 · Permutations and Combinations

4.2 Combinations and Applications

A combination is a selection in which order does not matter: ${}^{n}C_{r}=\dfrac{n!}{r!\,(n-r)!}$. From it come Pascal's rule, committees with conditions, divisors, the counting of lines, triangles and diagonals, groups and distributions, and the stars-and-bars count of integer solutions.

A cricket selector must pick $11$ players from a squad of $15$. Unlike the podium of Section 4.1, it does not matter in which order the names are written on the team sheet — the team is the same. A pizza with mushroom, olive and paneer is the same pizza as one with paneer, mushroom and olive. Lottery tickets, committees, hands of cards, the triangles that can be drawn through given points, the subsets of a set: all of these are selections, and counting them is the subject of this section.

The key observation is that every selection of $r$ different objects can be arranged in exactly $r!$ ways, so the number of selections is the number of arrangements divided by $r!$. That one division gives the combination numbers ${}^{n}C_{r}$, which are the most-used numbers of the whole chapter: they count committees with conditions and divisors of a number, lines and triangles in geometry, ways of splitting objects into groups, solutions of $x+y+z=n$ in whole numbers — and, in Chapter 5, they are the coefficients in the expansion of $(a+b)^n$.

Combinations — Selections where Order does not Matter

📘 Definition 4.4 — Combination; the number ${}^{n}C_{r}$

A combination of $r$ objects from $n$ different objects is a selection of $r$ of them, without regard to order — that is, an $r$-element subset of the $n$-element set. The number of such combinations is written ${}^{n}C_{r}$, $C(n,r)$ or $\dbinom{n}{r}$, for $0\le r\le n$.

From the letters $A,B,C,D$ the selections of three are $\{A,B,C\}$, $\{A,B,D\}$, $\{A,C,D\}$, $\{B,C,D\}$: ${}^{4}C_{3}=4$. Each of them can be arranged in $3!=6$ ways, and that gives all ${}^{4}P_{3}=24$ arrangements — each exactly once.

📐 Theorem 4.6 — Counting combinations

For integers $0\le r\le n$:

$${}^{n}C_{r}=\frac{{}^{n}P_{r}}{r!}=\frac{n!}{r!\,(n-r)!}=\frac{n(n-1)\cdots(n-r+1)}{r(r-1)\cdots1}.$$

In particular ${}^{n}C_{0}={}^{n}C_{n}=1$ and ${}^{n}C_{1}=n$.

Proof. Count the arrangements of $r$ out of $n$ objects in two stages: first select the $r$ objects (${}^{n}C_{r}$ ways), then arrange the selected objects ($r!$ ways). By the multiplication principle ${}^{n}P_{r}={}^{n}C_{r}\times r!$, and Theorem 4.2 gives ${}^{n}P_{r}=\frac{n!}{(n-r)!}$. $\blacksquare$ ⏱ For numbers, use the last form: ${}^{10}C_{3}=\dfrac{10\cdot9\cdot8}{3\cdot2\cdot1}=120$ — $r$ factors on top, $r$ factors below. The result is always a whole number, even though it is written as a fraction: it counts something.

📐 Theorem 4.7 — Properties of ${}^{n}C_{r}$
Symmetry${}^{n}C_{r}={}^{n}C_{n-r}$
Pascal's rule${}^{n}C_{r}+{}^{n}C_{r-1}={}^{n+1}C_{r}\ \ (1\le r\le n)$
Absorption$r\cdot{}^{n}C_{r}=n\cdot{}^{n-1}C_{r-1}\ \ (1\le r\le n)$
Equal values${}^{n}C_{x}={}^{n}C_{y}\Rightarrow x=y\ \text{or}\ x+y=n$
Ratio$\dfrac{{}^{n}C_{r}}{{}^{n}C_{r-1}}=\dfrac{n-r+1}{r}$
Largest value${}^{n}C_{n/2}$ ($n$ even); ${}^{n}C_{(n-1)/2}={}^{n}C_{(n+1)/2}$ ($n$ odd)

Proofs by counting. Symmetry: choosing the $r$ objects to take is the same as choosing the $n-r$ objects to leave behind. Pascal's rule: from $n+1$ objects, one of them special ($X$), the selections of $r$ either contain $X$ — then the other $r-1$ come from the remaining $n$: ${}^{n}C_{r-1}$ — or do not contain $X$: ${}^{n}C_{r}$. Absorption: count committees of $r$ with a chairperson from $n$ people: choose the committee and then its chair ($r\cdot{}^{n}C_{r}$), or choose the chair first and then the other $r-1$ members from the remaining $n-1$ ($n\cdot{}^{n-1}C_{r-1}$). Ratio: divide the two factorial formulas. The ratio exceeds $1$ exactly when $n-r+1\gt r$, i.e. $r\lt\frac{n+1}2$, so the values rise up to the middle and then fall; this gives the largest value. Equal values: since the values strictly rise to the middle and strictly fall after it, a value is taken at most twice, at $r$ and at $n-r$. $\blacksquare$

✏️ Example 1 — Working with ${}^{n}C_{r}$
(a) Evaluate ${}^{10}C_{3}$ and ${}^{12}C_{10}$. (b) If ${}^{n}C_{8}={}^{n}C_{6}$, find ${}^{n}C_{2}$. (c) Find $n$ and $r$ if ${}^{n}C_{r-1}=120$, ${}^{n}C_{r}=210$ and ${}^{n}C_{r+1}=252$. (d) Prove that ${}^{n}C_{r}+2\,{}^{n}C_{r-1}+{}^{n}C_{r-2}={}^{n+2}C_{r}$ for $2\le r\le n$.
(a) ${}^{10}C_{3}=\dfrac{10\cdot9\cdot8}{6}=120$. By symmetry ${}^{12}C_{10}={}^{12}C_{2}=\dfrac{12\cdot11}{2}=66$ — always use the smaller of $r$ and $n-r$.
(b) $8\ne6$, so $8+6=n$: $n=14$ and ${}^{14}C_{2}=91$.
(c) Ratio rule: $\dfrac{n-r+1}{r}=\dfrac{210}{120}=\dfrac74$ gives $4n+4=11r$; $\dfrac{n-r}{r+1}=\dfrac{252}{210}=\dfrac65$ gives $5n-6=11r$. So $4n+4=5n-6$: $n=10$, $r=4$.
(d) Split the middle term: $\big({}^{n}C_{r}+{}^{n}C_{r-1}\big)+\big({}^{n}C_{r-1}+{}^{n}C_{r-2}\big)={}^{n+1}C_{r}+{}^{n+1}C_{r-1}={}^{n+2}C_{r}$, using Pascal's rule three times. $\blacksquare$
Check (c) ${}^{10}C_{3}=120$, ${}^{10}C_{4}=210$, ${}^{10}C_{5}=252$ ✓.

There are ${}^{6}C_{3}=20$ ways to choose $3$ of the objects $1,2,\dots,6$. How many of these selections contain the object $6$?

Set $n=6$, $r=3$. The lab sorts the $20$ selections into two panels: contain 6 — $10$ of them, because once $6$ is in, the other two members come from $\{1,\dots,5\}$: ${}^{5}C_{2}=10$ — and do not contain 6 — also $10$, ${}^{5}C_{3}=10$. So $20=10+10$, which is Pascal's rule ${}^{6}C_{3}={}^{5}C_{2}+{}^{5}C_{3}$. In general a fixed object lies in a fraction $\tfrac rn$ of the selections: $\tfrac36\times20=10$.
Interactive 1 — Selection Lab: Pascal's Rule in Front of You

Choose $n$ objects and the size $r$ of the selection. Every one of the ${}^{n}C_{r}$ selections is listed — the left panel holds those that contain the last object $n$, the right panel those that do not. Press Play to walk through them; the objects at the top light up for the current selection (and the grey ones are the $n-r$ left behind, which is why ${}^{n}C_{r}={}^{n}C_{n-r}$).

63
${}^{n}C_{r}$—
contain $n$: ${}^{n-1}C_{r-1}$—
without $n$: ${}^{n-1}C_{r}$—
${}^{n}C_{n-r}$—

In how many ways can $3$ of $8$ friends be chosen to go on a trip together?

Selections with Conditions

Real selections come with conditions: a particular person must (or must not) be included, members must come from different groups, at least so many of a kind. Three ideas settle almost all of them.

📐 Theorem 4.8 — Counting all selections; divisors
  1. From $n$ different objects, the number of selections of any size is ${}^{n}C_{0}+{}^{n}C_{1}+\cdots+{}^{n}C_{n}=2^n$; selections of at least one object: $2^n-1$.
  2. From $p$ alike objects of one kind, $q$ alike of a second kind, $s$ alike of a third kind and $n$ further different objects, the number of selections of at least one object is $(p+1)(q+1)(s+1)\,2^n-1$.
  3. If $N=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ with distinct primes $p_i$, the number of positive divisors of $N$ is $(a_1+1)(a_2+1)\cdots(a_k+1)$ (including $1$ and $N$).

Proof. (1) Counting by size gives the sum; counting object by object, each object is either in or out — $2$ ways each — giving $2^n$ (Theorem 1.1). Remove the empty selection for "at least one". (2) From $p$ alike objects you can take $0,1,\dots,p$ of them — $p+1$ ways, since alike objects are distinguished only by how many; similarly $q+1$ and $s+1$; each different object is in or out. Multiply, and remove the empty selection. (3) A divisor of $N$ is $p_1^{b_1}\cdots p_k^{b_k}$ with each $0\le b_i\le a_i$: it "selects" $b_i$ of the $a_i$ alike factors $p_i$ — $(a_i+1)$ choices for each prime. $\blacksquare$

✏️ Example 2 — A committee with at least two women
A committee of $5$ is to be formed from $6$ men and $4$ women. In how many ways can this be done if (a) the committee has at least $2$ women; (b) it has exactly $2$ women and a particular man, Mr. $M$, must be on it? (c) A student argues: "for (a), first choose $2$ women (${}^{4}C_{2}$ ways), then any $3$ of the remaining $8$ people (${}^{8}C_{3}$ ways)". What answer does this give, and what is wrong with it?
Find (a) before you open the solution:
(a) $2W+3M$: ${}^{4}C_{2}\,{}^{6}C_{3}=6\times20=120$. $3W+2M$: ${}^{4}C_{3}\,{}^{6}C_{2}=4\times15=60$. $4W+1M$: ${}^{4}C_{4}\,{}^{6}C_{1}=6$. Total $186$.
Complement check All committees ${}^{10}C_{5}=252$; with no woman ${}^{6}C_{5}=6$; with exactly one ${}^{4}C_{1}\,{}^{6}C_{4}=60$. $252-6-60=186$ ✓.
(b) Women: ${}^{4}C_{2}=6$. Men: Mr. $M$ is in, so choose $2$ more of the other $5$ men: ${}^{5}C_{2}=10$. Total $60$.
(c) ${}^{4}C_{2}\times{}^{8}C_{3}=6\times56=336\gt186$: an overcount. A committee with $3$ women, say $W_1W_2W_3$ and two men, is produced three times — with $\{W_1,W_2\}$, $\{W_1,W_3\}$ or $\{W_2,W_3\}$ as the "first two" women. The two stages are not independent descriptions of a committee, so the multiplication principle does not apply.
✏️ Example 3 — Divisors and a fruit basket
(a) How many positive divisors does $720$ have? How many of them are even? (b) A basket holds $4$ identical apples, $3$ identical mangoes and $2$ different bananas (one ripe, one raw). In how many ways can at least one fruit be taken from it?
Factorise $720=2^4\cdot3^2\cdot5$.
(a) Divisors $2^a3^b5^c$ with $0\le a\le4$, $0\le b\le2$, $0\le c\le1$: $(4+1)(2+1)(1+1)=30$. Even divisors need $a\ge1$: $4\times3\times2=24$ (and $30-24=6$ odd ones: the divisors of $45$).
(b) Apples $0$–$4$: $5$ ways; mangoes $0$–$3$: $4$ ways; each banana in or out: $2^2$. Total $5\times4\times4-1=79$ (removing the empty choice).
Check (b) is Theorem 4.8(2). Had the apples been different, they alone would give $2^4=16$ choices, not $5$ — identical objects are chosen only by how many.

The number of positive divisors of $360=2^3\cdot3^2\cdot5$ is

Counting in Geometry

A line is fixed by $2$ points, a triangle by $3$ non-collinear points, a quadrilateral by $4$ points no three collinear — so geometric figures through given points are combinations of those points. Collinear points are the one complication.

📐 Theorem 4.9 — Standard geometric counts

For $n$ points in a plane, no three collinear except where stated:

  • lines through two of the points: ${}^{n}C_{2}$; triangles: ${}^{n}C_{3}$;
  • if exactly $m$ of the points are collinear (and no other three are): lines ${}^{n}C_{2}-{}^{m}C_{2}+1$, triangles ${}^{n}C_{3}-{}^{m}C_{3}$;
  • diagonals of a convex polygon with $n$ sides: ${}^{n}C_{2}-n=\dfrac{n(n-3)}{2}$;
  • a set of $p$ parallel lines crossed by a set of $q$ parallel lines forms ${}^{p}C_{2}\times{}^{q}C_{2}$ parallelograms; $n$ lines in general position meet in ${}^{n}C_{2}$ points.

Why. With $m$ collinear points, ${}^{n}C_{2}$ counts the one line through them ${}^{m}C_{2}$ times instead of once: subtract ${}^{m}C_{2}$ and add $1$ back. Any $3$ of the $m$ collinear points give no triangle, so subtract ${}^{m}C_{3}$ (nothing to add back). Joining two vertices of a polygon gives either a side ($n$ of them) or a diagonal. A parallelogram needs $2$ lines from each family. $\blacksquare$

✏️ Example 4 — Lines, triangles, diagonals, parallelograms
(a) Twelve points lie in a plane; exactly $5$ of them are on one line and no other three are collinear. How many lines and how many triangles do the points determine? (b) How many diagonals does a decagon have? (c) Five parallel streets run east–west and four parallel streets run north–south. How many parallelogram-shaped blocks (of any size) do they form?
Find the number of triangles in (a):
(a) lines ${}^{12}C_{2}-{}^{5}C_{2}+1=66-10+1=57$.
(a) triangles ${}^{12}C_{3}-{}^{5}C_{3}=220-10=210$.
(b) $\dfrac{10\times7}{2}=35$.
(c) Choose $2$ east–west streets and $2$ north–south streets: ${}^{5}C_{2}\times{}^{4}C_{2}=10\times6=60$.
Check (b) with a square: $\tfrac{4\times1}{2}=2$ diagonals ✓; with a triangle: $0$ ✓.

Ten points are marked on a circle. How many triangles have all three vertices among these points?

Selecting then Arranging; Groups and Distributions

Many problems have two stages: select the objects, then arrange them. A four-letter word with two vowels and two consonants is a selection of letters followed by an arrangement of the four chosen letters. The multiplication principle joins the two stages.

📐 Theorem 4.10 — Dividing into groups

Let $n=p+q+s$. The number of ways to divide $n$ different objects into three groups of sizes $p$, $q$, $s$ is

$$\frac{n!}{p!\,q!\,s!}\quad\text{if } p,q,s \text{ are all different;}\qquad \frac{(3m)!}{(m!)^3\,3!}\quad\text{for three equal groups of } m.$$

If the groups are then handed to three different people, multiply by the number of ways to assign the groups: $3!$ for the equal groups (giving $\frac{(3m)!}{(m!)^3}$). The same pattern holds for any number of groups: divide by $k!$ for every set of $k$ groups of equal size.

Proof. Choose the first group (${}^{n}C_{p}$), then the second from what is left (${}^{n-p}C_{q}$), then the rest form the third: ${}^{n}C_{p}\,{}^{n-p}C_{q}=\dfrac{n!}{p!\,q!\,s!}$. This counts labelled groups ("first", "second", "third"). When the sizes differ, the sizes themselves label the groups. When three groups have the same size, the same division is produced in $3!$ orders, so divide by $3!$. $\blacksquare$

Now distribute identical objects. Seven identical sweets shared by three children: a distribution is just a list $(x_1,x_2,x_3)$ of whole numbers with $x_1+x_2+x_3=7$. Write the sweets as stars and separate the children's shares by two bars: $\star\star\,|\,\star\star\star\star\,|\,\star$ means $(2,4,1)$, and $|\,\star\star\star\star\star\star\star\,|$ means $(0,7,0)$. Every distribution is a row of $7$ stars and $2$ bars, and every such row is a distribution.

📐 Theorem 4.11 — Stars and bars

The number of ways to distribute $n$ identical objects among $k$ different people (or boxes) — equivalently, the number of solutions of $x_1+x_2+\cdots+x_k=n$ in non-negative integers — is

$${}^{n+k-1}C_{k-1}.$$

If each person must get at least one ($x_i\ge1$, positive integer solutions; $n\ge k$), the number is ${}^{n-1}C_{k-1}$.

Proof. A row of $n$ stars and $k-1$ bars has $n+k-1$ places; choosing which $k-1$ places hold bars fixes the row, and the row fixes the solution ($x_1$ = stars before the first bar, and so on). So the solutions and the choices of bar places correspond one-to-one: ${}^{n+k-1}C_{k-1}$. For positive solutions, first give one object to each person; the remaining $n-k$ are distributed freely: ${}^{(n-k)+k-1}C_{k-1}={}^{n-1}C_{k-1}$. (Equivalently: the $n$ stars have $n-1$ inner gaps, and we put the $k-1$ bars into different gaps.) $\blacksquare$ Lower bounds such as $x_1\ge3$ are handled the same way: hand out the guaranteed amounts first, then distribute the rest.

✏️ Example 5 — Words, parcels and students
(a) From $5$ vowels and $7$ consonants, how many four-letter words can be formed that contain $2$ different vowels and $2$ different consonants? (b) In how many ways can $12$ different books be packed into $3$ identical parcels of $4$ books each? (c) In how many ways can the $12$ books be given to $3$ students, $4$ books each?
(a) Select: ${}^{5}C_{2}\times{}^{7}C_{2}=10\times21=210$ sets of four letters. Arrange each: $4!=24$. Total $5040$.
(b) Equal groups, unlabelled: $\dfrac{12!}{(4!)^3\,3!}=\dfrac{479001600}{13824\times6}=5775$.
(c) The students label the groups: $5775\times3!=34\,650=\dfrac{12!}{(4!)^3}$. Directly: ${}^{12}C_{4}\,{}^{8}C_{4}\,{}^{4}C_{4}=495\times70\times1$.
Check (a) by places: choose the $2$ places for the vowels (${}^{4}C_{2}=6$), fill them with different vowels in order (${}^{5}P_{2}=20$) and the other two places with different consonants (${}^{7}P_{2}=42$): $6\times20\times42=5040$ ✓.

Seven identical sweets are shared among three children; a child may get none. In how many ways can this be done?

Set $n=7$ objects, $k=3$ boxes, "boxes may be empty". The lab shows rows of $7$ stars and $2$ bars in $9$ places, and the readout gives ${}^{9}C_{2}=36$. Switch to "each box at least one" and it drops to ${}^{6}C_{2}=15$ — that is the first option. $2187=3^7$ would be right if the sweets were all different (each sweet chooses a child); $21={}^{7}C_{2}$ forgets that the bars also take up places.
Interactive 2 — Stars and Bars: Sharing Identical Objects

$n$ identical balls go into $k$ different boxes. Each way of doing it is a row of $n$ stars and $k-1$ bars (top) — the bars cut the row into the boxes' shares (bottom). Press Play to run through every distribution in turn and watch the bars move through the $n+k-1$ places. In "at least one" mode one ball (green) is first put in every box and only the rest are shared.

73
solution $(x_1,\dots,x_k)$—
number of ways—
showing—
✏️ Example 6 — Hard example: integer solutions with conditions
(a) Find the number of solutions of $x+y+z+w=12$ in non-negative integers. (b) How many of these have $x\ge1$ and $y\ge2$? (c) Find the number of solutions of $x+y+z=10$ in positive integers. (d) In how many ways can $10$ identical chocolates be given to $4$ children so that every child gets at least one?
Find (b) before you open the solution:
(a) $n=12$, $k=4$: ${}^{15}C_{3}=455$.
(b) Substitute $x=x'+1$, $y=y'+2$: $x'+y'+z+w=9$ with all four $\ge0$: ${}^{12}C_{3}=220$.
(c) Positive solutions: ${}^{10-1}C_{3-1}={}^{9}C_{2}=36$.
(d) Same as positive solutions of $x_1+x_2+x_3+x_4=10$: ${}^{9}C_{3}=84$.
Check (c) by a different route: give each variable $1$, then $x'+y'+z'=7$ in non-negative integers: ${}^{9}C_{2}=36$ ✓ — the same as Interactive 2 with $7$ balls and $3$ boxes.
⚠️ JEE Main traps

1. Selection or arrangement? Ask: if two chosen objects swap roles, is it a new outcome? Team, committee, hand of cards, set of points — no ($C$). Posts, positions in a word, seats — yes ($P$).

2. "At least" by "guarantee first, then anything". Choosing the required members first and then "any" from all the rest overcounts (Example 2(c): $336$ instead of $186$). Split into exact cases or use the complement.

3. Collinear points. Lines: subtract ${}^{m}C_{2}$ and add $1$ back. Triangles: subtract ${}^{m}C_{3}$ and add nothing back.

4. Equal groups. Divide by $k!$ only for $k$ groups of the same size that are not labelled; if the groups then go to different people, multiply the $k!$ back.

5. Identical or different objects? Identical objects into $k$ boxes: stars and bars, ${}^{n+k-1}C_{k-1}$ (or ${}^{n-1}C_{k-1}$ if no box is empty). Different objects into $k$ boxes: each object chooses a box, $k^n$.

🚀 Beyond JEE Main (JEE Advanced) — upper limits by inclusion–exclusion

Not in the JEE Main 2026 list as a method; distribution problems with upper limits are met in JEE Advanced. How many solutions has $x+y+z=10$ with $0\le x,y,z\le5$? Count all non-negative solutions, ${}^{12}C_{2}=66$, and remove those that break a limit. If $x\ge6$, put $x=x'+6$: $x'+y+z=4$, ${}^{6}C_{2}=15$ solutions; the same for $y$ and $z$. Two variables cannot both be $\ge6$ (that would need $12\gt10$), so by inclusion–exclusion (Section 1.1) the answer is $66-3\times15=21$. With larger totals the "two variables too big" terms must be added back, exactly as in $n(A\cup B\cup C)$.

Five identical balls are placed in three different boxes, and a box may stay empty. The number of ways is

Exercises

Give each answer as a number, and say in one line whether you are counting selections or arrangements.

I
The numbers ${}^{n}C_{r}$ and their properties.
  • 1 Evaluate ${}^{12}C_{4}$ and ${}^{12}C_{8}$. Why are they equal?
  • 2 If ${}^{n}C_{7}={}^{n}C_{5}$, find $n$ and then ${}^{n}C_{10}$.
  • 3 Find $n$ if ${}^{2n}C_{3}:{}^{n}C_{3}=10:1$.
  • 4 Write ${}^{8}C_{3}+{}^{8}C_{4}$ as a single ${}^{n}C_{r}$ and evaluate it.
  • 5 If ${}^{18}C_{r}={}^{18}C_{r+2}$, find $r$ and ${}^{r}C_{5}$.
  • 6 In how many ways can a team of $11$ be chosen from $15$ players? In how many ways, if a captain must also be named from the team?
  • 7 Prove that $r\cdot{}^{n}C_{r}=n\cdot{}^{n-1}C_{r-1}$ algebraically, and explain part 6 with it.
  • 8 Which of ${}^{11}C_{0},{}^{11}C_{1},\dots,{}^{11}C_{11}$ is largest, and what is its value?
1 ${}^{12}C_{4}=\dfrac{12\cdot11\cdot10\cdot9}{24}=495={}^{12}C_{8}$: choosing $4$ to take is choosing $8$ to leave.
2 $7\ne5$, so $n=12$; ${}^{12}C_{10}={}^{12}C_{2}=66$.
3 $\dfrac{2n(2n-1)(2n-2)}{n(n-1)(n-2)}=\dfrac{4(2n-1)}{n-2}=10$: $8n-4=10n-20$, $n=8$. Check: ${}^{16}C_{3}=560=10\times56$ ✓.
4 Pascal's rule: ${}^{9}C_{4}=126$ ($56+70$ ✓).
5 $r\ne r+2$, so $r+(r+2)=18$: $r=8$, ${}^{8}C_{5}={}^{8}C_{3}=56$.
6 ${}^{15}C_{11}={}^{15}C_{4}=1365$. With a captain: $1365\times11=15\,015$.
7 $r\cdot\dfrac{n!}{r!(n-r)!}=\dfrac{n!}{(r-1)!(n-r)!}=n\cdot\dfrac{(n-1)!}{(r-1)!\,(n-r)!}=n\cdot{}^{n-1}C_{r-1}$. In part 6: $11\cdot{}^{15}C_{11}=15\cdot{}^{14}C_{10}$ — choose the captain first ($15$ ways), then the other $10$ from $14$; ${}^{14}C_{10}=1001$ and $15\times1001=15\,015$ ✓.
8 $n=11$ is odd: the two middle values ${}^{11}C_{5}={}^{11}C_{6}=462$.
II
Selections with conditions.
  • 1 A student must answer $8$ of $10$ questions. In how many ways can she choose them (a) freely; (b) if the first $3$ are compulsory; (c) if she must answer at least $4$ of the first $5$?
  • 2 A committee of $4$ is chosen from $7$ men and $5$ women. How many committees have at least one woman?
  • 3 A team of $6$ is chosen from $8$ boys and $5$ girls. How many teams have at most $2$ girls?
  • 4 A committee of $5$ is chosen from $10$ people, two of whom refuse to serve together. How many committees are possible?
  • 5 In how many ways can at least one book be chosen from $6$ different books?
  • 6 Find the number of positive divisors of $1800$, the number of divisors other than $1$ and $1800$, and the number of odd divisors.
  • 7 A bag holds $5$ identical red balls, $4$ identical blue balls and $3$ different green balls. How many selections of at least one ball are possible?
  • 8 In how many ways can three different numbers be chosen from $1,2,\dots,20$ so that their sum is even?
  • 9 In how many ways can two squares be chosen on an $8\times8$ chessboard so that they are not in the same row or the same column?
1 (a) ${}^{10}C_{8}=45$. (b) ${}^{7}C_{5}=21$. (c) $4$ from the first five and $4$ from the last five: ${}^{5}C_{4}\,{}^{5}C_{4}=25$; or all $5$ and $3$ from the last five: ${}^{5}C_{3}=10$. Total $35$.
2 Complement: ${}^{12}C_{4}-{}^{7}C_{4}=495-35=460$.
3 $0$ girls ${}^{8}C_{6}=28$; $1$ girl ${}^{5}C_{1}\,{}^{8}C_{5}=280$; $2$ girls ${}^{5}C_{2}\,{}^{8}C_{4}=700$. Total $1008$.
4 All ${}^{10}C_{5}=252$, minus those with both: ${}^{8}C_{3}=56$. Answer $196$.
5 $2^6-1=63$.
6 $1800=2^3\cdot3^2\cdot5^2$: $(4)(3)(3)=36$ divisors; $34$ other than $1$ and $1800$; odd divisors (exponent of $2$ equal to $0$): $3\times3=9$.
7 $(5+1)(4+1)\,2^3-1=6\times5\times8-1=239$.
8 Ten even and ten odd numbers. Even sum: three even (${}^{10}C_{3}=120$) or one even and two odd (${}^{10}C_{1}\,{}^{10}C_{2}=450$). Total $570$.
9 First square $64$ ways, second $49$ ways (not in its row or column), divided by $2$ since the order of the two squares does not matter: $1568$.
III
Counting in geometry.
  • 1 How many diagonals does a $12$-sided convex polygon have?
  • 2 A convex polygon has $44$ diagonals. How many sides has it?
  • 3 How many triangles have their vertices among the vertices of a regular decagon? How many of them have no side in common with the decagon?
  • 4 Fifteen points lie in a plane, exactly $6$ of them on one line and no other three collinear. Find the number of lines and of triangles they determine.
  • 5 A family of $6$ parallel lines is crossed by a family of $5$ parallel lines. How many parallelograms are formed?
  • 6 What is the greatest number of points in which $8$ straight lines can meet? In which $8$ circles can meet?
  • 7 How many rectangles (of all sizes, including squares) can be seen on an $8\times8$ chessboard? How many squares?
  • 8 Five points are marked on one line and seven on a parallel line. How many triangles, and how many quadrilaterals, have their vertices among these $12$ points?
1 $\dfrac{12\times9}{2}=54$.
2 $n(n-3)=88=11\times8$: $n=11$.
3 ${}^{10}C_{3}=120$. Triangles sharing two sides with the decagon (three consecutive vertices): $10$. Sharing exactly one side: choose the side ($10$ ways) and a third vertex not adjacent to either end ($10-4=6$ ways): $60$. So $120-10-60=50$ share no side.
4 Lines ${}^{15}C_{2}-{}^{6}C_{2}+1=105-15+1=91$; triangles ${}^{15}C_{3}-{}^{6}C_{3}=455-20=435$.
5 ${}^{6}C_{2}\times{}^{5}C_{2}=15\times10=150$.
6 Two lines meet in at most one point: ${}^{8}C_{2}=28$. Two circles meet in at most two: $2\times{}^{8}C_{2}=56$.
7 A rectangle is fixed by $2$ of the $9$ horizontal and $2$ of the $9$ vertical grid lines: $({}^{9}C_{2})^2=36^2=1296$. Squares: $k\times k$ squares number $(9-k)^2$, so $8^2+7^2+\cdots+1^2=204$.
8 A triangle takes $2$ points from one line and $1$ from the other: ${}^{5}C_{2}\cdot7+{}^{7}C_{2}\cdot5=70+105=175$. A quadrilateral takes $2$ from each: ${}^{5}C_{2}\,{}^{7}C_{2}=210$.
IV
Selecting and arranging; groups; distributions.
  • 1 From $7$ consonants and $4$ vowels, how many five-letter words can be formed with $3$ different consonants and $2$ different vowels?
  • 2 How many four-letter arrangements can be made from the letters of $\text{BALLOON}$?
  • 3 In how many ways can $9$ different toys be shared among $3$ children so that each gets $3$?
  • 4 In how many ways can $9$ different toys be put into $3$ identical bags of $3$ each?
  • 5 In how many ways can $10$ different books be divided into three bundles of $5$, $3$ and $2$ books?
  • 6 Find the number of non-negative integer solutions of $a+b+c=15$.
  • 7 Find the number of positive integer solutions of $x+y+z+w=20$.
  • 8 In how many ways can $12$ identical pens be given to $4$ students so that each gets at least $2$?
  • 9 In how many ways can $5$ different letters be put into $4$ boxes (any box may hold any number)? In how many ways, if the $5$ letters are identical?
  • 10 How many $3$-element subsets of $\{1,2,\dots,10\}$ contain no two consecutive numbers?
1 ${}^{7}C_{3}\,{}^{4}C_{2}\cdot5!=35\times6\times120=25\,200$.
2 Letters B, A, N once; L, O twice. Four different letters (from B, A, L, O, N): ${}^{5}P_{4}=120$. One doubled letter ($L$ or $O$: $2$ ways) and two different others from the remaining $4$ letters (${}^{4}C_{2}=6$), arranged in $\tfrac{4!}{2!}=12$ ways: $144$. Both doubled ($LLOO$): $\tfrac{4!}{2!2!}=6$. Total $270$.
3 $\dfrac{9!}{3!\,3!\,3!}=1680$.
4 $\dfrac{1680}{3!}=280$ (the bags are identical).
5 Sizes all different: $\dfrac{10!}{5!\,3!\,2!}=2520$.
6 ${}^{15+2}C_{2}={}^{17}C_{2}=136$.
7 ${}^{19}C_{3}=969$.
8 Give $2$ to each first; share the remaining $4$ freely: ${}^{4+3}C_{3}={}^{7}C_{3}=35$.
9 Different letters: each picks a box, $4^5=1024$. Identical letters: stars and bars, ${}^{5+3}C_{3}=56$.
10 Write the chosen numbers $a\lt b\lt c$ with gaps $b-a\ge2$, $c-b\ge2$. Then $a\lt b-1\lt c-2$ is any $3$-subset of $\{1,\dots,8\}$, and conversely: ${}^{8}C_{3}=56$. (Gap view: the $7$ unchosen numbers make $8$ gaps; put the $3$ chosen numbers in different gaps.)
🎯 Exam corner JEE Main · MCQJEE Main · Numerical

E1. JEE Main · MCQ A group of $5$ is to be chosen from $6$ boys and $4$ girls so that it contains at least one boy and at least one girl. The number of ways is (A) $246$ (B) $252$ (C) $240$ (D) $186$

Complement All groups ${}^{10}C_{5}=252$. All boys: ${}^{6}C_{5}=6$. All girls: impossible (only $4$ girls).
Answer (A) $252-6=246$.
⏱ Shortcut Option (C) subtracts an "all girls" term that does not exist; (D) is "at least two girls". With a complement, check each excluded case can actually happen.

E2. JEE Main · Numerical Find the number of triangles whose vertices are three of the nine points $(x,y)$ with $x,y\in\{0,1,2\}$. Give the answer to the nearest integer.

All triples ${}^{9}C_{3}=84$.
Collinear triples $3$ rows, $3$ columns and $2$ diagonals of the $3\times3$ grid: $8$. (No other line contains three of the points.)
Answer $84-8=76$.

E3. JEE Main · MCQ The number of ways of choosing $4$ cards from a standard pack of $52$ so that there is one card of each suit is (A) ${}^{52}C_{4}$ (B) $4\times13^3$ (C) $13^4$ (D) $4!\times13^4$

Count One spade (${}^{13}C_{1}$), one heart, one diamond, one club: $13\times13\times13\times13$.
Answer (C) $13^4=28\,561$.
⏱ Shortcut (D) multiplies by $4!$ as if the cards were dealt in order — but a hand is a selection. The suits already label the four choices.

E4. JEE Main · Numerical Find the number of integer solutions of $x+y+z+w=16$ with $x\ge1$, $y\ge1$, $z\ge2$ and $w\ge0$. Give the answer to the nearest integer.

Shift $x=x'+1$, $y=y'+1$, $z=z'+2$: $x'+y'+z'+w=12$ with all four $\ge0$.
Stars and bars ${}^{12+3}C_{3}={}^{15}C_{3}$.
Answer $455$.
⏱ Shortcut Remaining total $R=16-(1+1+2)=12$; answer ${}^{R+k-1}C_{k-1}$ with $k=4$.

E5. JEE Main · MCQ Eight students are to be paired up for a lab session (four pairs, the pairs not labelled). The number of ways is (A) $2520$ (B) $105$ (C) $420$ (D) $70$

Groups Four equal groups of $2$, unlabelled: $\dfrac{8!}{(2!)^4\,4!}=\dfrac{40320}{16\times24}$.
Answer (B) $105$.
⏱ Shortcut Student 1 chooses a partner ($7$ ways), the lowest-numbered unpaired student chooses ($5$), then $3$, then $1$: $7\times5\times3\times1=105$. (A) $2520$ forgets to divide by $4!$.

E6. JEE Main · Numerical On a $5\times5$ square grid (like a small chessboard), find the number of rectangles formed by the grid lines that are not squares. Give the answer to the nearest integer.

Rectangles $6$ horizontal and $6$ vertical lines: $({}^{6}C_{2})^2=15^2=225$.
Squares $5^2+4^2+3^2+2^2+1^2=55$.
Answer $225-55=170$.
🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. How likely are you to win a national lottery — and is any lottery a fair bet?

Why it matters. Lotteries run in dozens of countries raise money for public causes, and millions of people buy tickets every week. Their prizes and odds are published, but few buyers can turn "choose $6$ numbers out of $49$" into a probability. Combinations make the odds exact and show how the design of a game controls its fairness.

What to do.

  1. Find the rules of two real lotteries in different countries (for example a "6 from 49" game and a game with a main draw and a separate bonus ball). Write each as a selection problem.
  2. Compute the number of possible tickets with ${}^{n}C_{r}$ (and the multiplication principle for a bonus ball). The jackpot probability is $1$ divided by this number.
  3. For a "6 from 49" game, count the tickets that match exactly $k$ of the $6$ drawn numbers: ${}^{6}C_{k}\,{}^{43}C_{6-k}$. Check that the counts for $k=0,\dots,6$ add up to ${}^{49}C_{6}$.
  4. Using the published prizes, compute the expected winnings per ticket and compare with the ticket price.

Tools: A spreadsheet (the function COMBIN computes ${}^{n}C_{r}$) or a few lines of Python.

Hand in: A table of match counts and probabilities for each lottery, your expected-value calculation, and a paragraph explaining to a friend what "1 in 14 million" means in everyday terms.

Going further. Some games let players choose $7$ or $8$ numbers on one ticket. How many $6$-number tickets is such an entry worth (${}^{7}C_{6}$, ${}^{8}C_{6}$)? Is it priced fairly?

Instructor note: ${}^{49}C_{6}=13\,983\,816$; the match counts are $6\,096\,454$, $5\,775\,588$, $1\,851\,150$, $246\,820$, $13\,545$, $258$, $1$ for $k=0,\dots,6$, which sum to ${}^{49}C_{6}$ — a nice instance of Vandermonde's identity. Expected values typically come out at about half the ticket price.

🧪 Self-check quiz

0/5 correct

Q1. If ${}^{n}C_{2}=45$, then $n$ equals

Q2. The number of diagonals of a hexagon is

Q3. A team of $3$ is chosen from $7$ people and one particular person must be included. The number of teams is

Q4. The number of solutions of $x+y+z=5$ in non-negative integers is

Q5. ${}^{n}C_{r}+{}^{n}C_{r-1}$ is equal to