Let S={1,2,3,4,5,6}. Then the number of one-one functions f:S→P(S), where P(S) denote the power set of S, such that f(n)⊂f(m) where n < m is
Explanation
Solution
f(1)⊂f(2)⊂f(3)⊂f(4)⊂f(5)⊂f(6)
\text{Let } |f(i)| = k_i, \text{ where } 0 \le k_1 < k_2 < k_3 < k_4 < k_5 < k_6 \le 6
Case 1: Sizes {0,1,2,3,4,5} or {1,2,3,4,5,6}
2×(6×5×4×3×2×1)=1440
Case 2: One size gap in {0,1,2,3,4,5,6}
Gaps possible at index 1, 2, 3, 4, or 5.
5×(Ways to choose subsets with one gap of size 2)
5×(2!6!)=5×360=1800
Explanation
Solution
f(1)⊂f(2)⊂f(3)⊂f(4)⊂f(5)⊂f(6)
\text{Let } |f(i)| = k_i, \text{ where } 0 \le k_1 < k_2 < k_3 < k_4 < k_5 < k_6 \le 6
Case 1: Sizes {0,1,2,3,4,5} or {1,2,3,4,5,6}
2×(6×5×4×3×2×1)=1440
Case 2: One size gap in {0,1,2,3,4,5,6}
Gaps possible at index 1, 2, 3, 4, or 5.
5×(Ways to choose subsets with one gap of size 2)
5×(2!6!)=5×360=1800