for the set $ A=\{1,2,...,n\} $ for each $0<k\leq n$ how many chains of subsets are there that satisfy the condition?
$$ A_1 \Delta_1 A_2 \Delta_2 ... \Delta_{k-1} A_k \subseteq A$$
$$ \Delta_i \in \{ {\supseteq} , {\subseteq} \} $$
What I've gotten so far is for $k=1$ we have $2^n$ chains (since it's only $A_1$ and it can be any set)
And for $k=2$ we have $\sum_{i=0}^n \binom{n}{k}2^k$ + $\sum_{i=0}^n \binom{n}{k}(2^{(n-k)}-1)$ where first sum is for where $A_1$ is a superset of $A_2$ and the second one is for when $A_1$ is a subset of $A_2$
My question is, is there a formula for each $n$, $k$?
If we divide into cases according to the number of elements in $A_1$, we can write down a recurrence and find that you're looking for the bottom right element (or any of the corner elements, really; they'll be equal) of the exponentiated matrix
$$ \begin{pmatrix} 1 & \binom{1}{0} & \binom{2}0 & \cdots & \binom{n-1}0 & \binom{n}0 \\ \binom{n}{n-1} & 1 & \binom{2}{1} & \cdots & \binom{n-1}n & \binom{n}1 \\ \binom{n}{n-2} & \binom{n-1}{n-2} & 1 & \cdots & \binom{n-1}2 & \binom n2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \binom n 1 & \binom{n-1}1 & \binom{n-2}1 & \cdots & 1 & \binom n{n-1} \\ \binom n 0 & \binom{n-1}0 & \binom{n-2}0 & \cdots & \binom 10 & 1 \end{pmatrix} ^ {\textstyle k+1} $$
I doubt there is any nice arithmetic-looking formula for that, but viewing it as matrix exponentiation would let you exploit tricks such as exponentiation-by-squaring to compute your number faster than step-by-step.