# Increasing tower of subsets of ${1, ..., k}$

Suppose $k$ is fixed. Consider a set $X$ of subsets of the ground set $\{1, \dots, k \}$, with the following property: there is some ordering of the elements of $X$, as $X = \{ x_1, \dots, x_n \}$, such that the chain of sets $Y_j = \cup_{i=1}^j x_i$ is strictly increasing, i.e. $$\emptyset \subsetneq Y_1 \subsetneq Y_2 \dots \subsetneq Y_n$$

Note that $X$ cannot contain the empty set. When $k = 2$, the set $X$ can be equal to $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{ \{1 \}, \{1, 2 \} \}$, $\{ \{2 \}, \{1, 2\} \}$, or $\{ \{1 \}, \{2 \} \}$, or $\{ \{1, 2 \} \}$. But $X$ is not allowed to be $\{ \{1 \}, \{2 \}, \{1, 2\} \}$.

Is there a simpler way of expressing this criterion for the set $X$? (That does not require a reference to an explicit ordering of its elements) Has this type of structure been studied before? For example, how many possibilities are there for $X$?

It appears based on some examples that $X$ can be written in this way iff the set $X$ is linearly independent over $GF(2)^k$ (with the obvious correspondence between subsets of $\{1, ... k \}$ and vectors over $GF(2)^k$. I have some trouble proving this criterion

• You can rephrase it algebraically in ter Commented Feb 7, 2014 at 17:29
• No, the description with linear independency does not work. The vectors 1100, 1010, 1001, and 1110 are linearly inepenent. However, you will not find a suitable order of the corresponding sets because there is four of them and you must start with a set of at least 2 elements. Btw., your condition is somewhat similar to the barycentric subdivision of a simplex (but not completely the same). You get more options than just simplices of the barycentric subdivision. Still, maybe there is a nice topological description. Commented Feb 7, 2014 at 20:56
• Sorry for the interrupt: ... in terms of the existence of n distinct elements of a join semilattice satisfying y_i+1 = y_i join some x, but it seems easier to say that there is some order on the x's such that. In terms of number of ways, it depends on the join relations of the x's, and can go from 0 on up to n! many ways. Commented Feb 7, 2014 at 21:56
• If you can calculate the answer for $k=3$, you may have enough information to consult the Online Encyclopedia of Integer Sequences. Commented Feb 7, 2014 at 23:49
• For $k=3$, I count 53; 7 with $n=1$, 15 with $n=2$ and at least one singleton; 6 with $n=2$ and no singleton; 10 with $n=3$ and 2 or more singletons; 15 with $n=3$ and just one singleton. Confirm? Refute? Commented Feb 10, 2014 at 5:10

One can give a generating function for the number $f_n(k)$ of $n$-tuples $(X_1,\dots, X_n)$ of subsets of $\{1,2,\dots,k\}$ such that if $Y_j=X_1\cup X_2\cup \cdots\cup X_j$, then the $Y_j$'s are strictly increasing and $Y_n=\{1,\dots,k\}$. This is a kind of labelled'' version of the proposed problem. Let $F_n(x)=\sum_k f_n(k)\frac{x^k}{k!}$. Fix a strictly increasing sequence $\emptyset=Y_0,Y_1, \dots, Y_n=\{1,\dots,k\}$ and set $a_j=\#(Y_j-Y_{j-1})$. Then there is one choice for $X_1$ (namely, $X_1=Y_1$), then $2^{a_1}$ choices for $X_2$ (namely, the union of $Y_2-Y_1$ with any subset of $Y_1$, then $2^{a_1+a_2}$ choices for $Y_3$ (namely, the union of $Y_3-Y_2$ with any subset of $Y_2$), etc. Standard properties of exponential generating functions give $$F_n(x) = \prod_{j=0}^{n-1} (e^{2^jx}-1).$$ If we don't want the condition $Y_n=\{1,2,\dots,k\}$, simply multiply $F_n(x)$ by $e^x$. The actual question seems much harder to me.

You can construct such all such tower as follows:

First, consider towers where you add exactly one element in each step. In the first step, you have $k$ choices, and in step $i$, you have $(k-i)$ choices. Therefore, $k!$ choices total.

Now, each block of $b_i$ such consecutive step can be "compressed" into a bigger one, so we need to partition the steps in consecutive blocks. So, we get in total $$\sum_{b_1 + b_2 + \dotso + b_k = k} \frac{k!}{b_1!b_2!\dotsc b_k!}$$ where we sum over all integer compositions of $k$. We need to divide by the factorials of the block sizes, since the order in which we add the elements does not matter. Now, the multinomial theorem states that this is exactly $k^k$.

• I realized that I missed a case in my example $k = 2$. When $k = 2$, the total number of possibilities is 5. One key point is that it is possible for the tower to increase by more than one element at a time. Commented Feb 7, 2014 at 20:29
• @Per the problem is that even if "you add exactly one element in each step", you may or may not keep preceding elements. E.g. you can start with 1,12 like you can start with 1,2. The unions $Y_j$ are the same in both cases. Commented Feb 8, 2014 at 13:44

For $k=4$ the sets $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,4\}$ and $\{2,3,4\}$ are linearly independent as elements of $\mathbb Z_2^4$. However, the chain of $Y_i$ can not be strictly increasing.

In the other direction, linear independence is obvious: if a "sum" of some of the $X_i$ is zero, then every element appears in an even number of them. But there is an element in the $X_i$ for the largest $i$ which is not in any of the others.