1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Related question on Computational Science scicomp.stackexchange.com/q/31083/659 $\endgroup$ – Pierre-Yves Gaillard Feb 18 at 20:41
  • $\begingroup$ 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. $\endgroup$ – Anton Menshov Feb 21 at 0:32
  • $\begingroup$ @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\})$? $\endgroup$ – Pierre-Yves Gaillard Feb 21 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.