Sequences
A091057
through
A091062
count equivalence classes of matrices or arrays. The matrices have a given
number of rows: r, columns: c, and each cell in the matrix is
filled with a value from a symbol set which has z elements. Two matrices
are equivalent if one can be transformed to the other through any combination
of permutations of the rows, columns or the symbol set. For example: consider
the following 3×3 matrix with symbol set {1, 2, ..., 9}:
This matrix is equivalent to:
by permuting the first two rows. It's also equivalent to:
by permuting the first two columns. It's also equivalent to:
by permuting `3' and `5' in the symbol set. It is not equivalent to:
since `8' appears twice and no symbol appears twice in the original.
While there are 99 = 387420489 different matrices there are only
777 equivalence classes as can be seen in
A091057.
There are 9 equivalence classes for a 2×2 with 4 symbols available.
Those classes are:
To calculate the number of equivalence classes of such matrices, let
Sr, Sc, and Sz be the sets of permutations
of the rows, columns and symbols respectively. Each permutation p
has a type (p1, p2, p3, ...) where
p1 is the number of 1-cycles in the permutation, p2
is the number of 2-cycles, etc. For example, the permutation (1234)(67)(89) in
S9 has type (1,2,0,1) for one 1-cycle (5), two 2-cycles
(67) and (89), no 3-cycles and one 4-cycle (1234). The number of types of
permutations in Sn is the number of partitions of n. (See
A000041.)
Let s, t and u be permutations from
Sr, Sc, and Sz respectively. The value:
fix A[s1, s2, s3, ...;
t1, t2, t3, ...;
u1, u2, u3, ...] =
prodi,j>=1 (sumd|lcm(i,j)
dud)gcd(i,j)sitj
is the number of matrices fixed or unmodified by a permutation of the rows of
type (s1, s2, s3, ...), a permutation of the
columns of type (t1, t2, t3, ...) and a
permutation of the symbol set of type
(u1, u2, u3, ...).
To calculate the number of equivalence classes, we must sum through each
triplet of permutation types as follows:
ar,c,z = sum1s1+2s2+...=r,
1t1+2t2+...=c,
1u1+2u2+...=z
fix A[s1, s2, ...;
t1, t2, ...;
u1, u2, ...]
/
(1s1s1!2s2s2!...
1t1t1!2t2t2!...
1u1u1!2u2u2!...)