TITLE: Number of regions of a venn diagram satisfying $S_1 \subseteq S_2 \supseteq S_3 \subseteq S_4 \supseteq \dotsm S_k$.
QUESTION [3 upvotes]: Question take from 5(d) of this handout.
Let $S$ be a set of $n$ elements. Let $k$ be a fixed integer, and you want to find the number of $k$-tuples $(S_1, S_2, \dots, S_k)$ satisfying:

each $S_1 \subset S$.
$S_1 \subseteq S_2 \supseteq S_3 \subseteq S_4 \supseteq \dotsm S_k$ where the subset and supset are alternating.

I think that first, the problem can be reduced to a venn-diagram question. For example of what I mean, see this question and its accepted answer.
So my question is then, if we have a venn diagram of $S_1, \dots, S_k$ satisfying $S_1 \subseteq S_2 \supseteq S_3 \subseteq S_4 \supseteq \dotsm S_k$, how many regions does it have? Lets denote this number by $V(k)$.
By brute force, I compute the following first few values, $V(2) = 3, V(3) = 5, V(4) = 8, V(5) = 13$.
Question: How can I find can prove a formula for $V(k)$? After such a formula is obtained, then the answer to the orginal question will be ${V(k)}^n$.
Thanks for the help! Any other ways of doing this question will also be very welcome.
Edit. Corrected $V(3)=5$ as mentioned by Mike Earnest.

REPLY [1 votes]: It should be $V(3)=5$. The sequence $V(1),V(2),V(3),\dots$ goes like $2,3,5,8,13,\dots,$ Are these numbers familiar? ; )
It seems that $V(k)$ is a Fibonacci number; to prove that, it would suffice to prove that $V(k)=V(k-1)+V(k-2)$, and then to check two base cases.
Here is a good way of looking at the problem. A region in the Venn diagram is specified by a sequence of $k$ zeroes and ones, where the $i^{th}$ symbol being one means the region is inside the $i^{th}$ set, and zero otherwise. Such a sequence $a_1,\dots,a_k$ must satisfy $a_1\le a_2 \ge a_3\le a_4 \ge \dots a_k$, to agree with the inclusion restrictions on the sets. Therefore, $V(k)$ is the number of such binary sequences satisfying those alternating inequalities. We have now reduced the problem to this other question on the site: How to simplify complicated Recursion.
{"set_name": "stack_exchange", "score": 3, "question_id": 3847249}