Mỗi tập con sẽ được mô tả bằng dãy ($x_1$,$x_2$,…,$x_k$) trong đó $x_1$<⋯<$x_k$. Đặt f[n] là sô lượng tập con khác rỗng của tập n phần tử ta có f[1]=1.

Ngoài ra:

+) Trường hợp 1: $x_1$ là phần tử nhỏ nhất, khi đó các phần tử còn lại Hoặc không có phần tử nào Hoặc là một tập con của tập n-1 còn lại Do vậy trong trường hợp này số lượng sẽ bằng f[n-1]+1

+) Trường hợp 2: $x_1$ không phải là phần tử nhỏ nhất. Tất nhiên số lượng tập con trong trường hợp này là f[n-1].

Ta có công thức :

    f[n] = (1 + f[n-1]) + f[n-1]