Question

Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is _______

Answer 1

Explanation:

Let’s take an example of 4 element set

{ a, b, c, d}

Now we need to find “tuples of the form (A,B) such that A and B are subsets of S”.

• Let’s take A as {a} , now calculate how many B’s are possible such that  A⊆B.

({a} , {a})	({a} ,{a, b})	({a} , {a, c})	({a} , {a, d})
({a} , {a, b, c})	({a} , {a, c, d})	({a} , {a, b, d})	({a} , {a, b, c, d})

 

8 tuples are possible.

Now if we take Φ as A then total 16 tuples are possible . and

If we take {a, b} as A then total 4 tuples are possible and for A we can chose ⁿC₂  ways so total ⁿC₂ × 4 tuples are possible for 2 element in A. And so on we can calculate for 2 element subsets and 3 element subsets.

So its general form for no of tuples possible (if n elements are given :

ⁿC₀×(2ⁿ)  + ⁿC₁×(2^n-1) + ⁿC₂×(2^n-2) + ...+ ⁿC_n×(2⁰) = (2+1)ⁿ

Calculation :

We have given number of elements as 10 so total number of tuples will be (2+1)¹⁰ = 3¹⁰ = 59049.