Question

. Consider a universe S of n(S) = 8 distinguishable elements. a. How many subsets of size 1 can be distinguished? b. How many subsets of size 2 can be distinguished? c. How many subsets of size 3 can be distinguished?an be distinguished? d. how many subsets of size 4 can be distinguished? e. How many total subsets of all sizes (NOT counting the empty set and the set S itself) can be distinguished?

Answer 1

Let S={ a,b,c,d,e,f,g,h }

(a) There are 8 different subsets each containing 1 element.

(b) There are ⁸C₂=8.7/(1.2)=28 different subsets each containing 2 elements:

{ a,b }, { a,c }, { a,d }, { a,e }, { a,f }, { a,g }, { a,h }, 

{ b,c }, { b,d }, { b,e }, { b,f }, { b,g }, { b,h }, { c,d }, 

{ c,e }, { c,f }, { c,g }, { c,h }, { d,e }, { d,f }, { d,g }, 

{ d,h }, { e,f }, { e,g }, { e,h }, { f,g }, { f,h }, { g,h }.

(c) ⁸C₃=8.7.6/(1.2.3)=56 subsets of size 3.

(d) ⁸C₄=8.7.6.5/(1.2.3.4)=70 subsets of size 4.

(e) There are 8+28+56+70+56+28+8=254=2⁸-2 subsets of all sizes excluding the empty set and S itself.

The above are properties of Pascal's Triangle. The 8th row coefficients are:

1 8 28 56 70 56 28 8 1, sum to 2⁸, which is all subsets including the empty set and S itself.