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]



The number of orbits of a permutation action
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.


