Given, S = {1,2 ..... n} First chose a k element subset B of S.This can be done in (
n
k
) ways Given the subset B,A has 2k−1 options(since the numbers of proper subset of a k- element let is 2k−1) Hence, the total number of pairs of sets (A B) such that A ⊆ B is given by