What if the sets were equal in size? Would $\alpha$ and $\beta$ be the same?

If $|X| = |Y| = n$, then both one-one and onto functions are simply bijections. In that case, $\alpha = \beta = n!$. It is a beautiful symmetry that collapses the complexity of the problem into a single factorial!

JEE Advanced 2018

LEVELJEE Advanced

Animated Solution for Mathematics - Permutations and Combinations: Let $X$ be a set with exactly $5$ elements and $Y$ be a set with exactly $7$ elements. If $α$ is the number of one-one functions from $X$ to $Y$ and $β$ is the number of onto functions from $Y$ to $X$ , then the value of $\frac{1}{5 !} (β - α)$ is ________.

Q: Why can't we just use the inclusion-exclusion formula for onto functions? It seems more direct.

You absolutely can! The inclusion-exclusion formula $\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m$ is the rigorous, universal way to solve this. However, for small sets like $7$ and $5$, the grouping method is a fantastic way to build intuition about how elements are partitioned. It helps you see the 'anatomy' of the function rather than just plugging numbers into a formula.

Q: Is $\alpha$ always smaller than $\beta$ for these set sizes?

Not necessarily, but in this specific case, yes. $\alpha$ represents the number of ways to embed a smaller set into a larger one, while $\beta$ represents the number of ways to cover a smaller set using a larger one. As the size difference increases, the number of onto functions grows much faster than the number of one-one functions.

Enter Numerical Value:

Progressive Hints

Hint 1

Hint 1: Visualize the mapping. For a one-one function from a set of 5 to a set of 7, you are essentially selecting 5 distinct targets and assigning them to the 5 sources. For an onto function from 7 to 5, you are partitioning the 7 elements into 5 non-empty buckets, where each bucket corresponds to an element in the target set.

Hint 2

Hint 2: Recall the combinatorial tools for these mappings. For one-one functions, use permutations or combinations followed by arrangements. For onto functions, the inclusion-exclusion principle is standard, but the 'grouping method' (partitioning 7 into 5 non-empty sets) is often more intuitive for small numbers.

Hint 3

Hint 3: Start by calculating the number of ways to partition 7 distinct items into 5 non-empty groups. If the group sizes are

n_{1}, n_{2}, n_{3}, n_{4}, n_{5}

, the number of ways to form these groups is given by

\frac{7 !}{n _{1} ! n _{2} ! n _{3} ! n _{4} ! n _{5} ! \times ( symmetry factor )}

. Once you have the partitions, multiply by

5!

to assign them to the distinct elements of

X

Visualized Solution

Problem Breakdown

Set $X$ has $5$ elements, Set $Y$ has $7$ elements.
$α =$ Number of one-one functions from $X \to Y$ .
$β =$ Number of onto functions from $Y \to X$ .
We need to evaluate: $\frac{1}{5 !} (β - α)$ .

Calculating $α$ (One-One Functions)

A one-one function maps each element of $X$ to a distinct element of $Y$ .
Choose $5$ elements from $Y$ : $^{7} C_{5}$ ways.
Arrange them among $5$ elements of $X$ : $5!$ ways.
$α =^{7} C_{5} \times 5!$

Evaluating $\frac{α}{5 !}$

$\frac{α}{5 !} =^{7} C_{5}$
$^{7} C_{5} = \frac{7 \times 6}{2 \times 1} = 21$

Understanding Onto Functions ( $β$ )

An onto function from $Y \to X$ means every element in $X$ has at least one pre-image in $Y$ .
This is equivalent to distributing $7$ distinct elements of $Y$ into $5$ distinct boxes of $X$ such that no box is empty.

Formation of Groups

Divide $7$ elements into $5$ non-empty groups.
Possible group sizes:
Case 1: $3, 1, 1, 1, 1$
Case 2: $2, 2, 1, 1, 1$

Group Formation: Case 1

Case 1: $3, 1, 1, 1, 1$
Number of ways = $\frac{7 !}{3 ! \times ( 1 ! ) ^{4} \times 4 !}$
$= \frac{7 !}{3 ! \times 24} = 35$

Group Formation: Case 2

Case 2: $2, 2, 1, 1, 1$
Number of ways = $\frac{7 !}{( 2 ! ) ^{2} \times 2 ! \times ( 1 ! ) ^{3} \times 3 !}$
$= \frac{7 !}{4 \times 2 \times 6} = \frac{5040}{48} = 105$

Total Ways to Form Groups

Total group formations = $35 + 105 = 140$
These $140$ group formations must now be assigned to the $5$ distinct elements of $X$ .
$β = 140 \times 5!$

Evaluating $\frac{β}{5 !}$

$\frac{β}{5 !} = 140$

Final Calculation

$\frac{1}{5 !} (β - α) = \frac{β}{5 !} - \frac{α}{5 !}$
$= 140 - 21$
$= 119$
Key Takeaway: Grouping method simplifies onto function calculations significantly compared to the inclusion-exclusion formula.

00:00 / 00:00

The Sigma Insight: Formation of Groups

Solution Diagram

Analyzing the Setup

We are working with two sets:

X

containing

5

elements and

Y

containing

7

elements. We define

α

as the number of one-one functions from

X

Y

, and

β

as the number of onto functions from

Y

X

Our objective is to calculate the value of

\frac{β - α}{5 !}

The Precision of One-One Functions

A one-one function requires each of the

5

elements in

X

to be mapped to a unique element in

Y

. We first select

5

elements out of

7

from set

Y

, which can be done in

(5 7)

ways.

Since the elements are distinct, we then arrange these

5

elements in

5!

ways to map them to the

5

elements of

X

. Thus, the total number of one-one functions is:

α = (5 7) \times 5!

Dividing this by

5!

, we obtain:

\frac{α}{5 !} = (5 7) = \frac{7 \times 6}{2 \times 1} = 21

The Complexity of Onto Functions

To find the number of onto functions

β

from

Y

(

7

elements) to

X

(

5

elements), we partition the

7

elements of

Y

into

5

non-empty groups. The possible partitions of

7

into

5

parts are

(3, 1, 1, 1, 1)

and

(2, 2, 1, 1, 1)

For the partition

(3, 1, 1, 1, 1)

, the number of ways to form the groups is:

\frac{7 !}{3 ! \times 1 ! ^{4} \times 4 !} = \frac{5040}{6 \times 24} = 35

For the partition

(2, 2, 1, 1, 1)

, the number of ways to form the groups is:

\frac{7 !}{2 ! ^{2} \times 2 ! \times 1 ! ^{3} \times 3 !} = \frac{5040}{4 \times 2 \times 6} = 105

The total number of ways to partition the elements is

35 + 105 = 140

. Since the elements of

X

are distinct, we assign these

5

groups to the

5

elements of

X

5!

ways:

β = 140 \times 5!

Final Calculation

We now compute the normalized difference as requested:

\frac{β}{5 !} - \frac{α}{5 !} = 140 - 21

Performing the final subtraction, we arrive at the result:

119

Common Traps & FAQs

Why can't we just use the inclusion-exclusion formula for onto functions? It seems more direct.

You absolutely can! The inclusion-exclusion formula

\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}

is the rigorous, universal way to solve this. However, for small sets like

7

and

5

, the grouping method is a fantastic way to build intuition about how elements are partitioned. It helps you see the 'anatomy' of the function rather than just plugging numbers into a formula.

Wait, why do we multiply by

5!

at the end of the grouping method?

Great catch! When you partition 7 elements into 5 groups, you are essentially creating 5 'piles'. But in an onto function, the target set

X

consists of 5 *distinct* elements. Therefore, the order of these piles matters—assigning pile A to element

x_{1}

is different from assigning it to

x_{2}

. Multiplying by

5!

accounts for all possible ways to label these piles with the elements of

X

In the grouping method, why do we divide by

4!

3!

in the denominators?

That is the 'symmetry factor'. When you have multiple groups of the same size (like four groups of size 1), the order in which you list those groups doesn't change the partition itself. Dividing by the factorial of the number of identical-sized groups removes that redundant counting. It's a classic combinatorial correction!

α

always smaller than

β

for these set sizes?

Not necessarily, but in this specific case, yes.

α

represents the number of ways to embed a smaller set into a larger one, while

β

represents the number of ways to cover a smaller set using a larger one. As the size difference increases, the number of onto functions grows much faster than the number of one-one functions.

What if the sets were equal in size? Would

α

and

β

be the same?

∣ X ∣ = ∣ Y ∣ = n

, then both one-one and onto functions are simply bijections. In that case,

α = β = n!

. It is a beautiful symmetry that collapses the complexity of the problem into a single factorial!

Enter Numerical Value:

Visualized Solution

Problem Breakdown

Calculating $α$ (One-One Functions)

Evaluating $\frac{α}{5 !}$

Understanding Onto Functions ( $β$ )

Formation of Groups

Group Formation: Case 1

Group Formation: Case 2

Total Ways to Form Groups

Evaluating $\frac{β}{5 !}$

Final Calculation

The Sigma Insight: Formation of Groups

Analyzing the Setup

The Precision of One-One Functions

The Complexity of Onto Functions

Final Calculation

Similar Questions

Let $α = \frac{( 4 !)!}{( 4 ! ) ^{3!}}$ and $β = \frac{( 5 !)!}{( 5 ! ) ^{4!}}$ . Then :

A group of 9 students $s_{1}, s_{2}, \dots, s_{9}$ is to be divided to form three teams $X, Y$ and $Z$ of sizes 2, 3 and 4 respectively. Suppose that $s_{1}$ cannot be selected for the team $X$ , and $s_{2}$ cannot be selected for team $Y$ . Then the number of ways to form such teams, is ________.

If $n$ is the number of ways five different employees can sit into four indistinguishable offices where any office may have any number of persons including zero, then $n$ is equal to:

The set $S = {1, 2, 3, \dots, 12}$ is to be partitioned into three sets $A, B, C$ of equal size. Thus $A \cup B \cup C = S, A \cap B = B \cap C = A \cap C = ϕ$ . The number of ways to partition $S$ is

Let the set $S = {2, 4, 8, 16, \dots, 512}$ be partitioned into 3 sets $A, B, C$ with equal number of elements such that $A \cup B \cup C = S$ and $A \cap B = B \cap C = A \cap C = ϕ$ . The maximum number of such possible partitions of $S$ is equal to:

In a hotel, four rooms are available. Six persons are to be accommodated in these four rooms in such a way that each of these rooms contains at least one person and at most two persons. Then the number of all possible ways in which this can be done is ____.

The students $S_{1}, S_{2}, \dots, S_{10}$ are to be divided into 3 groups $A, B$ and $C$ such that each group has at least one student and the group $C$ has at most 3 students. Then the total number of possibilities of forming such groups is

Eight persons are to be transported from city A to city B in three cars of different makes. If each car can accommodate at most three persons, then the number of ways, in which they can be transported, is

Enter Numerical Value:

Visualized Solution

Problem Breakdown

Calculating .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } α (One-One Functions)

Evaluating .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } 5!α​

Understanding Onto Functions ( .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } β)

Formation of Groups

Group Formation: Case 1

Group Formation: Case 2

Total Ways to Form Groups

Evaluating .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } 5!β​

Final Calculation

The Sigma Insight: Formation of Groups

Analyzing the Setup

The Precision of One-One Functions

The Complexity of Onto Functions

Final Calculation

Similar Questions

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let α=(4!)3!(4!)!​ and β=(5!)4!(5!)!​. Then :

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } The set S={1,2,3,…,12} is to be partitioned into three sets A,B,C of equal size. Thus A∪B∪C=S,A∩B=B∩C=A∩C=ϕ. The number of ways to partition S is

In a hotel, four rooms are available. Six persons are to be accommodated in these four rooms in such a way that each of these rooms contains at least one person and at most two persons. Then the number of all possible ways in which this can be done is ____.

Eight persons are to be transported from city A to city B in three cars of different makes. If each car can accommodate at most three persons, then the number of ways, in which they can be transported, is

Calculating $α$ (One-One Functions)

Evaluating $\frac{α}{5 !}$

Understanding Onto Functions ( $β$ )

Evaluating $\frac{β}{5 !}$

Let $α = \frac{( 4 !)!}{( 4 ! ) ^{3!}}$ and $β = \frac{( 5 !)!}{( 5 ! ) ^{4!}}$ . Then :

The set $S = {1, 2, 3, \dots, 12}$ is to be partitioned into three sets $A, B, C$ of equal size. Thus $A \cup B \cup C = S, A \cap B = B \cap C = A \cap C = ϕ$ . The number of ways to partition $S$ is