MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G$ be a finite group acting on a finite set $\Omega$. A general question is to determine the sequence $o_k(\Omega)$, where $o_k(\Omega)$ is the number of orbits on $G$ for the natural action of $G$ on the set of $k$-subsets of $\Omega$. It's well-known that if $G=S_n$ and the action on $\Omega =[n] := \{1, \ldots, n \}$ is the standard permutation action, that $o_k(\Omega) = 1$ (i.e. since $S_n$ is $n$-fold transitive the induced action on $k$-sets is transitive). I'm interested in being able to figure out the sequence $o_k(\Omega_r)$ where $G=S_n$, but where $\Omega$ is the set of all $r$-subsets of $[n]$, say for $r=2$ or $3$. I had hesitated asking this question since I thought that the answer must be well-known, but after a little while looking around I haven't been able to find it.

What I have been able to figure out is the following: if $A$ is a set of $r$-subsets of $[n]$ I'll define its signature: Let $U$ denote the multiset which is the multiset union of the elements of $A$ -- i.e. the multiplicity of an element $x \in U$ is the number of elements of $A$ which contain $x$. The signature of $A$ is the multiset of multiplicities in $U$. Then the action of $S_n$ is transitive on sets of a fixed signature. So the answer to my question is to count the number of possible signatures.

[Addition: if $s$ is the signature of a set $A$ of $k$-subsets of the set of $r$-subsets of $[n]$, then the sum of the elements (with multiplicity) of $s$ is $r k$. Thus a signature is a partition of of $rk$ into $\le n$ parts. However, it's not clear to me that all such partitions actually occur as signatures]

share|cite|improve this question
Are you sure about the transitivity of $S_n$ on the sets of fixed signature? For $r=2$ - using the shortcut $ab$ for the set $\{a, b\}$ - the two sets $A = \{12, 23, 13, 45, 56, 46\}$ and $B = \{12, 23, 34, 45, 56, 16\}$ have the same signature, but I doubt that they are both in the same orbit of $S_n$. I'd expect $\omega_k(\Omega_2)$ to be the number of isomorphic classes of (unordered) graphs with $k$ edges on $n$ vertexes. – Someone Jul 20 '11 at 14:38
I'll have to think about this. I had thought that I could use the $n$-transitivity of $S_n$ to move all of the elements with the same multiplicity to each other. – Victor Miller Jul 20 '11 at 15:10
up vote 5 down vote accepted

For $r=2$ a $k$-subset can be thought of as a graph with vertices $[n]$ and $k$ edges. Hence the number of orbits is equal to the number of isomorphism classes of graphs on $n$ vertices and $k$ edges. Counting them seems like a fairly intractable problem.

share|cite|improve this answer
Torsten, Thanks. You are right. I found this link – Victor Miller Jul 20 '11 at 16:19
Counting them exactly is quite hard, but asymptotics are easy, since a general graph has trivial automorphism group. – Igor Rivin Jul 20 '11 at 17:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.