1
$\begingroup$

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}

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Sep 26 '16 at 21:13
  • $\begingroup$ @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$). $\endgroup$ – Robert Israel Sep 26 '16 at 21:28
  • $\begingroup$ I apologize if the wording is not great, I don't know the math notation very well. @RobertIsrael is correct in assuming they are not proper subsets. $\endgroup$ – mpgaillard Sep 26 '16 at 22:10
  • $\begingroup$ @RobertIsrael Thank you for explaining the answer. (+1). $\endgroup$ – Marko Riedel Sep 26 '16 at 22:13
  • $\begingroup$ Awesome. Thanks! $\endgroup$ – mpgaillard Sep 26 '16 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.