Skip to main content
spelling, grammar
Source Link
Ben McKay
  • 26.3k
  • 7
  • 67
  • 102

Symmentric Symmetric group acting on the set of boolean functions

Let $S_n$ is actingact on the set of boolean functions of size $n$ in the following way:

If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean vector of size $n$;

Let $p$ isbe the number of orbits. Since each orbit can have no more than $n!$ elements it is obvious that $p\ge\frac{2^{2^n}}{n!}$.

I am interested in an upper bound of $p$. Do you know any results related to itresults?

Symmentric group acting on the set of boolean functions

Let $S_n$ is acting on set of boolean functions of size $n$ in the following way:

If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean vector of size $n$;

Let $p$ is number of orbits. Since each orbit can have no more than $n!$ elements it is obvious that $p\ge\frac{2^{2^n}}{n!}$.

I am interested in upper bound of $p$. Do you know any results related to it?

Symmetric group acting on the set of boolean functions

Let $S_n$ act on the set of boolean functions of size $n$ in the following way:

If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean vector of size $n$;

Let $p$ be the number of orbits. Since each orbit can have no more than $n!$ elements it is obvious that $p\ge\frac{2^{2^n}}{n!}$.

I am interested in an upper bound of $p$. Do you know any related results?

Source Link
Ashot
  • 337
  • 1
  • 9

Symmentric group acting on the set of boolean functions

Let $S_n$ is acting on set of boolean functions of size $n$ in the following way:

If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean vector of size $n$;

Let $p$ is number of orbits. Since each orbit can have no more than $n!$ elements it is obvious that $p\ge\frac{2^{2^n}}{n!}$.

I am interested in upper bound of $p$. Do you know any results related to it?