# Number of $S_n$-orbits in $P^k(\{1,\dots,n\})$

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)$$.

• Related question on Computational Science scicomp.stackexchange.com/q/31083/659 – Pierre-Yves Gaillard Feb 18 at 20:41
• Hmm, but that (Knuth's up-arrow for $a(2,k)$) does not give a lot of insight on what to do with $a(3,2)$. I kind of feel that there will be many more Knuth arrows, possibly nested, but I cannot see anything yet. – Anton Menshov Feb 21 at 0:32
• @Anton - Note that $a(3,2)$ is less that $2^8=256$, so it's not a huge number. Which programming language would you use to list the $256$ elements of $P^2(\{1,2,3\})$? – Pierre-Yves Gaillard Feb 21 at 12:44