# How many combinations are there when we have K subsets where each subset is a subset of the following subset?

Let the universe S be the natural numbers between 1 and N. And let's say we have K consecutive subsets $A_1 \subseteq A_2 \subseteq \ldots \subseteq A_K \subseteq S$, where all the subsets $$A_i$$ must be a subset of $$A_i+1$$ and subset $$A_K$$ must be a subset of the universe S.

Note: the subsets do not need to be proper subsets.

If we are given N and K, how many different subset chains are there?

Example 1: N = 2, K = 1

There are 4 ways to make 1 valid subset chain.

{} (selecting the empty set)

{1}

{2}

{1,2}

Example 2: N = 1, K = 2

There are 3 ways to make 2 valid subset chains.

{},{}

{},{1}

{1},{1}

Example 3: N = 2, K = 2

{},{}

{},{1}

{},{2}

{},{1, 2}

{1},{1}

{1},{1,2}

{2}, {1,2}

{2}, {2}

{1,2},{1,2}

A solution $A_1 \subseteq A_2 \subseteq \ldots \subseteq A_K \subseteq S$ corresponds to a partition of $S$ into $K+1$ disjoint subsets $A_1, A_2 \backslash A_1, \ldots, A_K \backslash A_{K-1}, S \backslash A_K$. The number of these is easily seen to be $(K+1)^N$, as each member of $S$ can go into any one of the $K+1$ subsets.
• This question is not well worded, I think the OP also admits subsets that are equal as opposed to proper subsets. Also it is not clear that OP uses all $N$ values. – Marko Riedel Sep 26 '16 at 21:13
• @MarkoRiedel I'm not assuming proper subsets, and I'm not assuming using all $N$ values in the $A_i$ (that's why there's the $S \backslash A_K$). – Robert Israel Sep 26 '16 at 21:28