JEE Mains Maths · Permutations and Combinations

Counting Functions, Matrices and Subsets

Counting mathematical objects: one-one or increasing functions under conditions, matrices whose entries satisfy a sum condition, and subsets with a property of their elements.

All Permutations and Combinations notes JEE Mains Maths strategy

Why this matters

Eighteen PYQs, thirteen of them numerical answer. Each object is a choice made position by position: a function assigns values, a matrix fills cells, a subset includes or leaves out each element. Four count functions, eight count matrices and six count subsets. Three ideas cover the page.

Concept 1 of 3: Counting functions

A one-one function from an

m

-set to an

n

-set is an arrangement:

{}^nP_m

. Handle the constrained inputs first, then fill the rest. A strictly increasing function is fixed by its set of values, so it is a choice:

\binom nm

. If some inputs must take decreasing values, choose those values and their order is forced.

Definition

All functions $A\to B$ : $n^m$ . One-one: ${}^nP_m$ .
Strictly increasing: $\binom nm$ .
Constrained inputs first, then the free ones.
Values forced into an order: choose the set, the order is automatic.

One-one and increasing

\#\{\text{one-one}\}={}^nP_m,\qquad\#\{\text{strictly increasing}\}=\binom nm

Worked example

How many one-one functions

f:\{1,2,3\}\to\{1,\dots,5\}

have

f(1)=2

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2024 · 5 Apr 2024 · Q67Moderate

Example 1 · Permutations and Combinations · Counting Functions, Matrices and Subsets

Let

\mathbf{A = \{ 1,3,7,9,11\}}

and

\mathbf{B = \{ 2,4,5,7,8,10,12\}}

. Then the total number of one-one maps

f:A \rightarrow B

, such that

f(a) + f(c) = 14

, is:

Constrained inputs first

Assigning free inputs first can use up a value a constrained input needs, and the count then depends on earlier choices. Fix the constrained values first so every later step has a fixed number of options.

Drill 3 more on counting functions

Concept 2 of 3: Counting matrices by their entries

A matrix is a list of entries, so a condition on the sum of entries is a distribution problem, and a condition on

\operatorname{tr}(A^TA)

is a condition on the sum of squares of all entries. Break the target into squares (

0,1,4,9

), choose positions for each, and multiply by the sign choices of the non-zero entries.

Definition

$\operatorname{tr}(A^TA)=\operatorname{tr}(AA^T)=\sum_{i,j}a_{ij}^2$ .
Entries $0/1$ with $k$ ones: $\binom{\text{cells}}{k}$ .
Each non-zero entry from $\{\pm1,\pm2\}$ doubles the count for its sign.
Rows and columns each summing to 1 (0/1 entries): permutation matrices, $n!$ .

Trace of AᵀA

\operatorname{tr}(A^{T}A)=\sum_{i,j}a_{ij}^{2}

Worked example

How many

2\times2

matrices with entries in

\{-1,0,1\}

have

\operatorname{tr}(A^TA)=2

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2022 · 29 July 2022 · Q86Moderate

Example 2 · Permutations and Combinations · Counting Functions, Matrices and Subsets

The number of matrices of order

3 \times 3

, whose entries are either 0 or 1 and the sum of all the entries is a prime number, is

Signs multiply only non-zero entries

A zero entry has one form; each non-zero entry from

\{-2,-1,1,2\}

has two signs. Multiply by

2^{(\text{number of non-zero entries})}

, not

2^{(\text{cells})}

Drill 7 more on counting matrices by their entries

Concept 3 of 3: Subsets with a property

n

-set has

2^n

subsets and

\binom nk

of size

k

. A property is often easier through its complement: 'product even' means 'not all odd'. For a condition on the sum modulo 3, group the elements by remainder and count the ways to pick remainders that add to a multiple of 3. Subsets with no two consecutive elements follow the Fibonacci numbers.

Definition

Subsets: $2^n$ ; of size $k$ : $\binom nk$ .
Containing at least one of $m$ special elements: $2^n-2^{n-m}$ .
Sum $\equiv0\pmod3$ : combine counts by remainder class.
No two consecutive from $\{1,\dots,n\}$ : $F_{n+2}$ (1, 2, 3, 5, 8, 13, …).

Complement

\#\{\text{contains an even}\}=2^n-2^{\#\text{odd}}

Worked example

How many subsets of

\{1,2,\dots,6\}

have an even product (the empty set's product is 1)?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

JEE Mains · 2023 · 8 Apr 2023 · Q78Moderate

Example 3 · Permutations and Combinations · Counting Functions, Matrices and Subsets

Let the number of elements in sets A and B be five and two respectively. Then the number of subsets of A

\times

B each having at least 3 and at most 6 element is:

The empty set

Check whether the question counts the empty set. Its sum is 0 — a multiple of 3 — and its product is taken as 1; 'non-empty' removes it.

Drill 5 more on subsets with a property

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (3)

Counting functions
One-one and increasing
$\#\{\text{one-one}\}={}^nP_m,\qquad\#\{\text{strictly increasing}\}=\binom nm$
Counting matrices by their entries
Trace of AᵀA
$\operatorname{tr}(A^{T}A)=\sum_{i,j}a_{ij}^{2}$
Subsets with a property
Complement
$\#\{\text{contains an even}\}=2^n-2^{\#\text{odd}}$

Watch out for (3)

Constrained inputs first
→ Counting functions
Signs multiply only non-zero entries
→ Counting matrices by their entries
The empty set
→ Subsets with a property

Test yourself on Permutations and Combinations

20 past JEE Mains questions from this chapter, timed at 48 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Permutations and Combinations chapter test Drill all 18 questions