1
$\begingroup$

This is a particular case of a question I asked on Mathematics Stackexchange, question which got no answer so far.

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\}$.

We 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)$?

If you don't feel like computing these three integers, I'd be most grateful if you could nevertheless explain to me a simple (perhaps not efficient) way of computing them.

Sadly, I know nothing about programming languages.

Edit 1. Here are more details about the equality $a(2,2)=12$. We have $$ P(\{1,2\})=\{\varnothing,\{1\},\{2\},\{1,2\}\}. $$ So $$ P^2(\{1,2\})=P(\{\varnothing,\{1\},\{2\},\{1,2\}\}) $$ has $16$ elements, one of cardinality $0$ (that is, with zero elements), which is the empty set $$ \varnothing, $$ four of cardinality $1$, which are $$ \{\varnothing\},\{\{1\}\},\{\{2\}\},\{\{1,2\}\}, $$ six of cardinality $2$, which are $$ \{\varnothing,\{1\}\}, \{\varnothing,\{2\}\}, \{\varnothing,\{1,2\}\}, $$ $$ \{\{1\},\{2\}\}, \{\{1\},\{\{1,2\}\}, \{2\},\{\{1,2\}\} $$ four of cardinality $3$, which are $$ \{\varnothing\}^c,\{\{1\}\}^c,\{\{2\}\}^c,\{\{1,2\}\}^c, $$ where $A^c$ denotes the complement of $A$ in $P(\{1,2\})$, and one of cardinality $4$, which is $$ P(\{1,2\}). $$ Now let $X$ be one of the sixteen above expressions.

If you swap the symbols $1$ and $2$ in $X$, you get either $X$ itself, or a different expression $Y$, and if you perform the same operation $Y$, you get $X$ back.

So the non-invariant expressions (the "non-fixed points") come in pairs.

By inspection one sees that there are $8$ invariant expressions and $4$ pairs of non-invariant expressions, that is $12$ "orbits".

Edit 2. An inductive formula for $a(2,k)$ is given in an edit to this Mathematics Stackexchange post, but I'm still unable to compute $a(3,2)$.

$\endgroup$

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.