Combinatorial counting with symmetry Let $A$ be a set of objects where $|A|=n$. We want to count all the possible ways that we can arrange these objects into $n$ bags with exactly $n$ objects in each. We can reuse any object, however, no repetition is allowed inside the bags. 
With $A=\{a,b,c\}$, for example, $[(a,b,c), (a,b,c), (b,c,a)]$ is a valid outcome.
Obviously there are $(n!)^n$ ways to do this. 
Now we want to add two extra constraints:


*

*The order of bags is not important. 


For example, $[(a,b,c), (a,b,c), (b,c,a)]$ would be identical to $[(b,c,a), (a,b,c), (a,b,c)]$.


*

*The label of objects inside the bags do not matter. Only the relative positions are important.


For example, $[(a,b,c), (a,b,c), (b,c,a)]$ would be identical to $[(c,b,a), (c,b,a), (b,a,c)]$ and is identical to $[(a,c,b), (a,c,b), (c,b,a)]$ etc.
Questions are:


*

*How many ways can we set these bags given the above constrains ?

*Is there any algorithm to output all these possible combinations?

 A: Write the permutations as the rows of a matrix.  For example $[(a,b,c),(a,c,b),(b,c,a)]$ becomes
$$\begin{matrix} a & b & c\\ a & c & b\\ b & c & a\end{matrix}~~.$$ So far we just have an $n\times n$ matrix whose rows are permutations.  Now we have some equivalence rules: 
(1) permuting the rows gives an equivalent matrix
(2) permuting the names of the symbols gives an equivalent matrix
Since (1) and (2) are a bit dissimilar, we can instead write the inverses of the permutations in each row (identifying the columns in order as $a,b,c,\ldots\,$).
In this example: $$\begin{matrix} a & b & c\\ a & c & b\\ c & a & b\end{matrix}~~.$$
Now the equivalence rules are nicer:
(1) permuting the rows gives an equivalent matrix
(2') permuting the columns gives an equivalent matrix
We can consider this situation as a representation of the permutation group $S_n\times S_n$: the points are the matrices with permutations in each row, and $(g,h)\in S_n\times S_n$ acts by applying $g$ to the columns and $h$ to the rows. The enumeration question is to determine the number of orbits of this permutation group.  The standard method for doing this is Pólya's Theorem, which is a sort of Burnside's Lemma on steroids, but it would be some work and the answer might be a horrible summation.  The similar problem when the rows are 0-1 vectors rather than permutations is solved here. I'm not so good at this sort of calculation, but if Ira Gessel comes by he might tell us how to do it.
Some ideas don't work: to borrow terminology from Latin squares, we can call the matrix reduced if the first row and first column are in numerical order.  Each orbit contains at least one reduced matrix, but the number of reduced matrices in an orbit varies so counting reduced matrices doesn't help much. Something similar works, see below.
Standard computational methods of listing orbit representatives would work here but will run out of steam quickly as the number of orbits is at least $(n!)^{n-2}$.  For $n\le 5$ it would be easy, for $n=6$ a big computation, and for $n=7$ exhaustive generation is out of the question. Finding the count for slightly larger $n$ is possible since Burnside's lemma can be applied by computer: it is the sum over $(g,h)\in S_n\times S_n$ of some expression that depends only on the cycle lengths of $g$ and $h$. Since we know how many permutations have a given multiset of cycle lengths, we can write it as a sum of some expression over pairs of partitions of $n$.
The fact that rows are permutations gives this generation algorithm: Given matrix $A$, for $1\le i\le n$ define $A^{(i)}$ like this: starting with $A$, swap row $i$ with row 1, permute the colums so that row 1 is the identity, permute rows $2,\ldots,n$ into lexicographic order. Define $\hat A$ to be the lexicographically largest of $A^{(1)},\ldots,A^{(n)}$. I claim that $\hat A=\hat B$ iff $A$ and $B$ are equivalent.  Therefore the matrices $A$ such that $\hat A=A$ are a set of distinct orbit representatives.
A: With the relative order constraint, it would seem that the number of permutations is back to n!. 
