RankRizz
JEE MAIN 2023 · 30 JAN S1+4 / −1HARDTRANSCRIBED

JEE Main 2023 Mathematics question — One-one, onto functions and counting functions

Let S={1,2,3,4,5,6}S = \{1, 2, 3, 4, 5, 6\}. Then the number of one-one functions f:S→P(S)f: S \to P(S), where P(S)P(S) denote the power set of SS, such that f(n)⊂f(m)f(n) \subset f(m) where n<mn < m is

SOLUTION

Step 1: Understand the conditions on the function

We are given the set S={1,2,3,4,5,6}S = \{1, 2, 3, 4, 5, 6\} which contains 6 elements.

We need to find the number of one-one functions f:S→P(S)f: S \to P(S) such that if n<mn < m, then f(n)⊂f(m)f(n) \subset f(m).

This implies that the images of the elements under ff form a strictly increasing chain of nested subsets:

f(1)⊂f(2)⊂f(3)⊂f(4)⊂f(5)⊂f(6)f(1) \subset f(2) \subset f(3) \subset f(4) \subset f(5) \subset f(6)

Step 2: Analyze the sizes of the subsets

Let si=∣f(i)∣s_i = |f(i)| denote the number of elements in the set f(i)f(i). Since the subsets are strictly contained within one another, their sizes must be strictly increasing integers:

0≤s1<s2<s3<s4<s5<s6≤60 \le s_1 < s_2 < s_3 < s_4 < s_5 < s_6 \le 6

Thus, the sequence of sizes (s1,s2,s3,s4,s5,s6)(s_1, s_2, s_3, s_4, s_5, s_6) is formed by choosing 6 distinct integers from the 7 possible values in the set {0,1,2,3,4,5,6}\{0, 1, 2, 3, 4, 5, 6\}. This means exactly one size will be missing from the sequence.

Step 3: Count the number of valid chains for each case of the missing size

Case 1: The missing size is 0

The sizes of the sets must be (1,2,3,4,5,6)(1, 2, 3, 4, 5, 6).

To form this chain, we start with 1 element for f(1)f(1), add 1 element to get f(2)f(2), add 1 element to get f(3)f(3), and so on.

The number of ways to choose which elements are added at each step is equal to the number of permutations of the 6 elements:

Ways=6!=720\text{Ways} = 6! = 720

Case 2: The missing size is 6

The sizes of the sets must be (0,1,2,3,4,5)(0, 1, 2, 3, 4, 5).

Here, f(1)=∅f(1) = \emptyset. At each subsequent step, exactly 1 element is added until f(6)f(6) has 5 elements, leaving exactly 1 element out of the final set.

The number of ways to distribute the elements into this sequence of additions is:

Ways=6!=720\text{Ways} = 6! = 720

Case 3: The missing size is mm, where m∈{1,2,3,4,5}m \in \{1, 2, 3, 4, 5\}

There are 5 possible values for the missing size. For any such choice, the size sequence includes 0 and 6, but skips mm.

This means that at the transition from size m−1m-1 to size m+1m+1, we must add exactly 2 elements at once, while all other transitions add exactly 1 element.

The number of ways to arrange the 6 elements of SS into these specific increments (one group of 2 elements, and four groups of 1 element) is given by the multinomial coefficient:

Ways=6!2!×1!×1!×1!×1!=7202=360\text{Ways} = \frac{6!}{2! \times 1! \times 1! \times 1! \times 1!} = \frac{720}{2} = 360

Since there are 5 such missing sizes, the total number of ways for this case is:

Ways=5×360=1800\text{Ways} = 5 \times 360 = 1800

Step 4: Sum all the possible cases

The total number of such one-one functions is the sum of the possibilities from all cases:

Total=720+720+1800=3240\text{Total} = 720 + 720 + 1800 = 3240

Conclusion:

The number of one-one functions satisfying the given conditions is 3240.

Tagged One-one, onto functions and counting functions. Machine-assigned, so read it as a strong shortlist rather than a verdict.

ChapterFunctions
TopicOne-one, onto functions and counting functions
TypeNumerical answer