4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Your picture suggests that $S4, S5, S6, S7, S8... \subseteq S2$ but I imagine there is no such constraint ? $\endgroup$
    – Evargalo
    Jun 15, 2017 at 12:52
  • 1
    $\begingroup$ 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 $\endgroup$
    – Veeper
    Jun 15, 2017 at 13:45
  • $\begingroup$ Nevermind wrong idea $\endgroup$
    – Veeper
    Jun 15, 2017 at 13:51
  • $\begingroup$ 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 ? $\endgroup$
    – Evargalo
    Jun 15, 2017 at 14:11
  • $\begingroup$ nope. I double-checked. None $\endgroup$
    – Veeper
    Jun 15, 2017 at 15:16

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .