Let $n$ and $k$ be integers with $n\ge1$, $k\ge0$, and let $a(n,k)$ be the number of orbits of the symmetric group $S_n$ on the $k$-th iterated power set $$ P^k(\{1,\dots,n\}) $$ of the set $\{1,\dots,n\}$.
Have the $a(n,k)$ been studied?
How can one compute the $a(n,k)$?
We of course have $a(n,0)=1$, $a(n,1)=n+1$, $a(1,k+1)=2^{a(1,k)}$ and $$ \frac{b(n,k)}{n!}\le a(n,k)\le b(n,k), $$ where $b(n,k)$ is the cardinality of $P^k(\{1,\dots,n\})$.
We also have $a(2,2)=12$. Indeed, the twelve orbits of the two-element group $S_2$ in $P^2(\{1,2\})$ can be described as follows.
The set $P^2(\{1,2\})$ having sixteen elements, it suffices to give the eight fixed points. The complement of a fixed point being a fixed point, it suffices to give four fixed points $F_1,F_2,F_3,F_4$ such that, for all $i,j$, the subset $F_i$ is not the complement of $F_j$. A possible choice of the $F_i$ is $$ \varnothing,\ \{\varnothing\},\ \{\{1,2\}\},\ \{\varnothing,\{1,2\}\}. $$
Can anybody compute, say, $a(2,3),a(3,2)$ and $a(3,3)$?
What is the computational complexity of $a(n,k)$?
Note the inequality $a(n,k+1)\ge2^{a(n,k)}$ due to the fact that $S_n$ has $2^{a(n,k)}$ fixed points on $P^{k+1}(\{1,\dots,n\})$.
Edit. In fact $a(2,k)$ can be computed inductively via the formulas $$ a(2,0)=1 $$ and $$ a(2,k)=\frac12\left((2\uparrow\uparrow k)+2^{a(2,k-1)}\right)\qquad(1), $$ where Knuth's up-arrow notation has been used.
Equality $(1)$ can be proved as follows. The two statements below are clear:
$(2)$ If a group $G$ acts on a finite set $X$ with $r$ orbits, then $G$ acts on $P(X)$ with $2^r$ fixed points.
$(3)$ If the group $S_2$ acts on a finite set $X$ of cardinality $m$ with $f$ fixed points and $r$ orbits, then we have $r=(m+f)/2$.
Proof of $(1)$: The cardinality of $P^k(\{1,2\})$ is $2\uparrow\uparrow k$. By $(2)$ the number of fixed points of $S_2$ in $P^k(\{1,2\})$ is $2^{a(2,k-1)}$. Now $(1)$ follows from $(3)$.
I'm still unable to compute $a(3,2)$.