# Finding the number of k-tuples of sets.

Find the number of k-tuples of sets $<S_1,...,S_k>$ where $S_1,...,S_k ⊆$ {1,...,n} and where:
$S_1⊆S_2⊇S_3⊆S_4⊇S_5⊆S_6⊇ ...$

So I think it will look something like this: picture but can't figure how to find the answer. Any ideas?

• Your picture suggests that $S4, S5, S6, S7, S8... \subseteq S2$ but I imagine there is no such constraint ? Jun 15, 2017 at 12:52
• Yes, you're right, it will look more like this sketchtoy.com/68158449 So maybe I could choose the intersections then divide them into 2 sections, then divide the whole thing into floor(k/2) sections??? hmm Jun 15, 2017 at 13:45
• Nevermind wrong idea Jun 15, 2017 at 13:51
• Let's say $k=2r$. My intuition would rather be to pick first $r$ distincts sets $S_1, S_3,..., S_{2r-1}$ and then build $S2$ as $S1\cup S3 \cup${anything else}. But then checking that $S_2$ and $S_4$ are different and counting cases will be a mess. Btw, we have no indication either that the intersection of $S_1$ and $S_3$ should be empty ? Jun 15, 2017 at 14:11
• nope. I double-checked. None Jun 15, 2017 at 15:16

The answer to your question is: $$(F_{k+2})^n$$ Where F is the fibbonacci function, defined as: $$F_{n} = F_{n-1} + F_{n-2}$$ $$F_{1} = F_{2} = 1$$

The core idea behind this is that each of the n elements in {1,...,n} can be considered separately for the purpose of building the k-tuple. Then, once we have the number of k-tuples over a set of 1 element, we just raise it to the n'th power to account for the rest of the set.

 Proof:

For clarity, let's denote the number of such k-tuples over {1,...,n} to be f(n,k). First, we look at the special case of n=1; that is, a set of one element.

There are 2 cases:

Case 1: S_1 is empty

This implies that there are  no restriction on what we can place in S_2.
This means that there f(1,k-1) sets satisfying case 1.
Case 2: S_1 contains 1

This implies that S_2, being a superset of S_1, contains 1. This in turn
means that there is no restriction on S_3. Thus there are f(1,k-2) sets
satisfying case 2.


Clearly Case 1 and Case 2 partition the space, and so we must have:

$$f(1,k) = f(1,k-1) + f(1,k-2)$$

Looking at some base cases and counting manually, we get that:

$$f(1,1)=2=F_3$$

$$f(1,2)=3=F_4$$

Thus, $$f(1,k) = F_{k+2}$$.

Moving back to general n, notice that we can break the problem into n steps:

Choose which sets in <S_1, ... ,S_k> 1 goes into

Choose which sets in <S_1, ... ,S_k> 2 goes into

.

.

.

Choose which sets in <S_1, ... ,S_k> n goes into


Clearly, these represent independent actions. It follows then that:

$$f(n,k) = f(1,k)^n$$

Substituting our expression for f(1,k) we finally get that:

$$f(n,k) = (F_{k+2})^n$$