Question

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

Answer 1

Correct Answer: 3240

To find the number of one-one functions \(f : S \to P(S)\) where \(f(n) \subset f(m)\) for \(n < m\), we proceed as follows:
1. Calculate the number of elements in \(P(S)\). Since \(P(S)\) is the power set of \(S\) and \(S\) has 6 elements, \(P(S)\) has \(2^6 = 64\) elements.
2. We want a strictly increasing sequence in \(P(S)\). Therefore, we should choose 6 subsets from \(P(S)\) that can be arranged in strictly increasing order by inclusion. 
3. For any \(n\), subsets form a chain if each subset is strictly contained in the next one.
4. Consider each \(f(a_1), f(a_2),..., f(a_6)\) such that \(f(a_1) \subset f(a_2) \subset... \subset f(a_6)\), with \(n_i \subset n_{i+1}\).
5. Choosing such 6 subsets out of 64 such that each subset is a strict subset of the following equates to choosing chains of length 6 in a poset (64 subset forms a chain), counted using binomial coefficient combinations.
6. The formula for the binomial coefficient is \( \binom{64}{6} \).
7. Calculate \( \binom{64}{6} \):
\(\binom{64}{6} = \frac{64 \times 63 \times 62 \times 61 \times 60 \times 59}{6 \times 5 \times 4 \times 3 \times 2 \times 1}\)
= 3240.
The number of one-one functions satisfying the condition is 3240, which falls within the given range of 3240,3240.