Let $n$ be a nonnegative integer. Determine the number of ways to choose sets $S_{i j} \subseteq\{1,2, \ldots, 2 n\}$, for all $0 \leq i \leq n$ and $0 \leq j \leq n$ (not necessarily distinct), such that
- $\left|S_{i j}\right|=i+j$, and
- $S_{i j} \subseteq S_{k l}$ if $0 \leq i \leq k \leq n$ and $0 \leq j \leq l \leq n$.
The answer is $(2 n)!\cdot 2^{n^{2}}$. First, we note that $\varnothing=S_{00} \subsetneq S_{01} \subsetneq \cdots \subsetneq S_{n n}=\{1, \ldots, 2 n\}$ and thus multiplying by $(2 n)$ ! we may as well assume $S_{0 i}=\{1, \ldots, i\}$ and $S_{i n}=\{1, \ldots, n+i\}$. We illustrate this situation by placing the sets in a grid, as below for $n=4$; our goal is to fill in the rest of the grid.
$$
\left[\begin{array}{ccccc}
1234 & 12345 & 123456 & 1234567 & 12345678 \\
123 & & & & \\
12 & & & & \\
1 & & & & \\
\varnothing & & & &
\end{array}\right]
$$

We claim the number of ways to do so is $2^{n^{2}}$. In fact, more strongly even the partial fillings are given exactly by powers of 2 .
Claim - Fix a choice $T$ of cells we wish to fill in, such that whenever a cell is in $T$, so are all the cells above and left of it. (In other words, $T$ is a Young tableau.) The number of ways to fill in these cells with sets satisfying the inclusion conditions is $2^{|T|}$.

An example is shown below, with an indeterminate set marked in red (and the rest of $T$ marked in blue).
$$
\left[\begin{array}{ccccc}
1234 & 12345 & 123456 & 1234567 & 12345678 \\
123 & 1234 & 12346 & 123467 & \\
12 & 124 & 1234 \text { or } 1246 & & \\
1 & 12 & & & \\
\varnothing & 2 & & &
\end{array}\right]
$$

Proof. The proof is by induction on $|T|$, with $|T|=0$ being vacuous.
Now suppose we have a corner $\left[\begin{array}{ll}B & C \\ A & S\end{array}\right]$ where $A, B, C$ are fixed and $S$ is to be chosen. Then we may write $B=A \cup\{x\}$ and $C=A \cup\{x, y\}$ for $x, y \notin A$. Then the two choices of $S$ are $A \cup\{x\}$ (i.e. $B$ ) and $A \cup\{y\}$, and both of them are seen to be valid.

In this way, we gain a factor of 2 any time we add one cell as above to $T$. Since we can achieve any Young tableau in this way, the induction is complete.