number of ways of choosing sets of integers

Question

Let $k$ be a nonnegative integer. Determine the number of ways to choose $(k+1)^2$ sets $S_{i,j}\subseteq [2k] := \{1,2,\cdots ,2k\}$ for integers $i,j$ with $0\leq i, j \leq k$ so that for all $0\leq i\leq c\leq k, 0\leq j\leq d \leq k, S_{i,j}\subseteq S_{c,d}.$

The number of subsets of $\{1,2,\cdots, 2k\}$ is $2^{2k}$. There are thus $2^{2k}$ ways to choose the subset $S_{0,0}$. Suppose it has $a_0$ elements. Then the set $S_{1,0}$ must contain these $a_0$ elements and a subset of the complement of these $a$ elements in $\{1,2,\cdots, 2k\}$. In general, if $S_{i,0}$ has $a_i$ elements then $S_{i+1, 0}$ must have at least $a_i$ elements and the set of elements in $S_{i+1,0}\backslash S_{i,0}$ is a subset of $[2k]\backslash S_{i,0}$. This chain of reasoning does not seem very useful however, because it's largely dependent on what the sizes of the sets $S_{i,j}$ are. Would generating functions be useful and if so, how? Obviously one can't just choose $(k+1)^2$ subsets from the set of all subsets of $[2k]$ and order them because subsets only form a partial order under inclusion; some aren't even comparable.

Answer 1

The question contains some distractions. There’s no connection between the occurrence of $k$ in $[2k]$ on the one hand and in $0\le i,j\le k$ on the other hand; so we can generalize to $S_{i,j}\subseteq M$ for arbitrary $M$. Also, we can choose for each element of $M$ independently which $S_{i,j}$ to include it in, so the result is just $n^{|M|}$, where $n$ is the number of ways to distribute a given element over the $S_{i,j}$. There’s a natural correspondence between these ways and the monotonic lattice paths from $(0,k+1)$ to $(k+1,0)$ on $[0,k+1]^2$, of which there are $\binom{2(k+1)}{k+1}$. Thus, the answer is $\binom{2(k+1)}{k+1}^{|M|}$, or in your special case, $\binom{2(k+1)}{k+1}^{2k}$.

In response to the comment: For a given element $m\in M$, for each $i$, there is some $j_i$ such that $m\notin S_{i,j}$ for $j\lt j_i$ and $m\in S_{i,j}$ for $j\ge j_i$. Furthermore, for $i_2\gt i_1$, we have $j_{i_2}\le j_{i_1}$. The $j_i$ correspond to a monotonic lattice path from $(0,k+1)$ to $(k+1,0)$ with horizontal steps from $(i,j_i)$ to $(i+1,j_i)$ for all $i$ (and the necessary vertical steps to connect them).