Join WhatsApp Icon JEE WhatsApp Group
Question 85

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


Correct Answer: 3240

Step 1: Understand the conditions on the function

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

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

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

$$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 $$s_i = |f(i)|$$ denote the number of elements in the set $$f(i)$$. Since the subsets are strictly contained within one another, their sizes must be strictly increasing integers:

$$0 \le s_1 < s_2 < s_3 < s_4 < s_5 < s_6 \le 6$$

Thus, the sequence of sizes $$(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\}$$. 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)$$.

To form this chain, we start with 1 element for $$f(1)$$, add 1 element to get $$f(2)$$, add 1 element to get $$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:

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

Case 2: The missing size is 6

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

Here, $$f(1) = \emptyset$$. At each subsequent step, exactly 1 element is added until $$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:

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

Case 3: The missing size is $$m$$, where $$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 $$m$$.

This means that at the transition from size $$m-1$$ to size $$m+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 $$S$$ into these specific increments (one group of 2 elements, and four groups of 1 element) is given by the multinomial coefficient:

$$\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:

$$\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:

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

Conclusion:

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

Get AI Help

Create a FREE account and get:

  • Free JEE Mains Previous Papers PDF
  • Take JEE Mains paper tests
Ask AI