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
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.
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.
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$
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$?
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.
- Particular objects. If $p$ particular objects must be included, choose the other $r-p$ from the remaining $n-p$: ${}^{n-p}C_{r-p}$. If they must be excluded: ${}^{n-p}C_{r}$.
- Groups. Choosing $a$ from one group and $b$ from another: ${}^{m}C_{a}\times{}^{k}C_{b}$.
- "At least" / "at most". Split into the exact cases and add, or use the complement (all minus the forbidden cases) — whichever has fewer cases.
- 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$.
- 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$.
- 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$
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.
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$
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.
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.
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.
Seven identical sweets are shared among three children; a child may get none. In how many ways can this be done?
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$.
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.
- 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 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 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 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?
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$
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.
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$
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.
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$
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.
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.
- 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.
- 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.
- 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}$.
- 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?
🧪 Self-check quiz
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