Let . Then the number of one-one functions , where denote the power set of , such that where is
Step 1: Understand the conditions on the function
We are given the set which contains 6 elements.
We need to find the number of one-one functions such that if , then .
This implies that the images of the elements under form a strictly increasing chain of nested subsets:
Step 2: Analyze the sizes of the subsets
Let denote the number of elements in the set . Since the subsets are strictly contained within one another, their sizes must be strictly increasing integers:
Thus, the sequence of sizes is formed by choosing 6 distinct integers from the 7 possible values in the set . 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 .
To form this chain, we start with 1 element for , add 1 element to get , add 1 element to get , 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:
Case 2: The missing size is 6
The sizes of the sets must be .
Here, . At each subsequent step, exactly 1 element is added until 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:
Case 3: The missing size is , where
There are 5 possible values for the missing size. For any such choice, the size sequence includes 0 and 6, but skips .
This means that at the transition from size to size , 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 into these specific increments (one group of 2 elements, and four groups of 1 element) is given by the multinomial coefficient:
Since there are 5 such missing sizes, the total number of ways for this case is:
Step 4: Sum all the possible cases
The total number of such one-one functions is the sum of the possibilities from all cases:
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.