MathematicsRelations and FunctionsJEE

Relations and Functions · Part 7 of 20

Bijections, Counting Functions and Composites

Functions that are both one-one and onto, how to count functions, injections, surjections and bijections between finite sets, and which properties pass through a composite gof.

Builds on: Part 6 · One-One, Many-One, Onto and Into Functions.

Bijections, Counting Functions and Composites

Video coming soon

Bijective

sin(πx/2) on [−1, 1]

πx/2 runs over [−π/2, π/2], where sine increases from −1 to 1. So sin(πx/2) : [−1, 1] → [−1, 1] is one-one and onto: a bijection.

Graph inside the square [−1, 1] × [−1, 1]. — Increasing, and the range equals the codomain.

Counting

Maps from n to m elements

Functions $m^{n}$ ; one-one $^{m} P_{n}$ (m ≥ n); onto $\sum (- 1)^{r}^{m} C_{r} (m - r)^{n}$ ; bijections n! when m = n.

Example

Onto maps from 5 to 3 elements

$3^{5} - 3 \cdot 2^{5} + 3 \cdot 1^{5} = 243 - 96 + 3 = 150$ .

Table of terms adding to 150. — Each row is one inclusion–exclusion term.

Three-set arrow diagram. — First function one-one, last function onto.

Composites

gof bijective, f not onto, g not one-one

f, g one-one ⇒ gof one-one; f, g onto ⇒ gof onto. Backwards: gof one-one forces only f one-one, and gof onto forces only g onto. Here gof is a bijection while f misses r and g sends q and r to y.

Summary

Key formulas

functions A \to B : m^{n}

Bijective functions and counting mappings

one-one:^{m} P_{n} (m \geq n)

Bijective functions and counting mappings

onto: \sum_{r = 0}^{m} (- 1)^{r}^{m} C_{r} (m - r)^{n}

Bijective functions and counting mappings

bijections (m = n) : n!

Bijective functions and counting mappings

Worked examples

From the video

1. Onto functions from a 5-element set to a 3-element set?

150.

2. f(x) = 0 (x rational), x (x irrational); g(x) = 0 (x irrational), x (x rational). Find f − g and its nature.

−x for rational x, x for irrational x; a bijection.

3. f : R → [0, ∞), x² and g : R → R, x are onto. Is gof : R → R onto?

No: the codomain of f is not the domain of g.

JEE-style question

Your turn

The number of onto functions from {1, 2, 3, 4} to {a, b} is:

(a)16

(b)14

(c)12

(d)2

Show the answer and the traps

2⁴ − 2·1⁴ = 16 − 2 = 14: remove the two constant maps. Option (b).

16 counts every function, onto or not. 12 = ⁴P₂ counts one-one maps the wrong way round.

2 counts only the constant maps: the ones that are not onto.

Watch out

Common mistakes

Reversing which function is forcedgof one-one ⇒ f one-one; gof onto ⇒ g onto.

Counting onto maps as m^nSubtract the maps that miss elements (inclusion–exclusion).

Calling a function onto without the codomainOnto is always onto a stated set.

Practice

Try these

1. One-one functions from {1, 2, 3} to {a, b, c, d, e}?

⁵P₃ = 60.

2. Onto functions from a 4-element set to a 3-element set?

81 − 48 + 3 = 36.

3. f : A → B, g : B → C, gof one-one. Must g be one-one?

No; only f must be.

4. Bijections from a 5-element set to itself?

5! = 120.