On Relations

Jaime Rangel-Mondragón

Permission is hereby granted to reproduce part or all of this file for any purpose other than direct profit providing that the source is acknowledged.

Given a set A, the set of all possible relations defined on it has found a prominent place as a natural framework  both in applied and theoretical research. A relation on A is any subset of A × A.  This notebook includes the generation and enumeration of important families of relations. The enumeration of  these families is accomplished under conjugacy equivalence by means of Burnside’s lemma following the ideas of Davis. The families include relations in general, symmetric relations, reflexive relations, graphs, partial and total orders, lattices and functions. File onRelations.pdf containing all figures refered to in the text complements this notebook.

Relation seems to be the principle of order. 
At least it can be said that the various conceptions of order which appear in the greats books involve the idea of relation and of different kinds of relationship.
	The order of the universe or of nature, for example, seems to be differently conceived according as things are causally related to one another, related as lower and higher species in a hierarchy of grades of being, or as the parts of one all-embracing whole. 
	In each case, it makes a difference, as we have already observed, whether the relations involved are thought to be real or logical, and internal or external to the things related.
	Relations similarly enter into conceptions of psychological, political, and moral order - the order of the parts of the soul, the order of classes or functions in the state, the order of goods, of means and ends, of duties, of loves. 
	
	RELATION
	The Syntopicon Vol. II
	Great Books
	Encyclopaedia Britannica, Inc.
	Sixth Printing, 1996

References

[1] http://mathworld.wolfram.com/

[2] The number of structures of Finite Relations
R. L. Davis,  
Proc. Amer. Math. Soc., 4 (1953)  483-495

[3] Concrete Mathematics
R. L. Graham, D. E. Knuth and O. Patashnik,
Addison-Wesley, 1994

[4] Applied Combinatorics
A. Tucker,
John-Wiley, 1984

[5] Discrete Mathematical Structures with Applications to Computer Science
J. P. Tremblay and R. Manohar, 
Mc. Graw-Hill, 1988

[6] Finite Groups Acting on sets with Applications
L. W. Shapiro, 
Mathematics Magazine, May-June, 1973 p. 136-147

[7]  Fundamental Algorithms
D. E. Knuth,
Third Edition. Addison-Wesley, 1998

[8] Discrete and Combinatorial Mathematics
R. P. Grimaldi,
Fourth Edition. Addison-Wesley, 2000

[9] The On-line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/index.html

In dealing with a problem of high complexity, a first attempt at its solution is often made through dividing the problem into cases. In mathematics this division arises naturally by imposing a relation on the elements of the set under study. Supporting this point of view, prominent categories of relations have found a plethora of applications; among those categories we can consider those of  functions, equivalence relations, partial orders, lattices, Boolean algebras, etc., which are defined according to their compliance to a handful of very general and primitive structural characteristics such as transitivity. Their relevance to Computer Science is commonplace as they offer a natural framework for the setting and analysis of problems in the areas of pattern classification and enumeration of classes [3]. 

Even in dealing with finite structures, however, once a relation has been specified, it is often the case that further distinction is needed among the classes due to their abundance. This simplification is achieved through setting up an isomorphism. The idea behind it resides in specifying when can two configurations be regarded as equal, leading to a significant reduction of complexity and hence providing insight into the fine structure of the problem at hand. 

We divide our work in two main parts. The first one addresses the problem of generation of all relations and prominent families and their enumeration. By their prolific nature we consider only a limited range of relations. The second part distinguishes among non-isomorphic structures following David´s ideas to consider the action of a group of symmetries in accordance to Polya´s theory.

PART I GENERATION

Let ℜ\(TraditionalForm\`\_n\) be the set of all relations on the set Range[n], that is all possible subsets of  Range[n]x Range[n]. The members of (Subscript[ℜ, n]) are often conveniently  represented as binary matrices of size n x n.

(Subscript[ℜ, n])_ := (Subscript[ℜ, n]) = 
        Map[Partition[IntegerDigits[#, 2, (n^2)], n] &, 
          Range[0, (2^((n^2))) - 1]]

MatrixForm  /@  (Subscript[ℜ, 2])

The first and last members of the above list are refered to as the empty and universal relations respectively. The number of relations grows exponentially:

\(\(Length[ℜ\_#] &\) /@ Range[4]\)

The above numbers start as (seq A002416 in [8]):

(2^(Range[7]^2))

Even when trying to compute (Subscript[ℜ, 5]), Mathematica disconnects the kernel for lack of memory (in a 160Mb environment), rendering the generation of all relations for n≥6 unfeasible. In the following we process the ones already generated in order to select prominent subfamilies.

Testing Relations

We consider the families of reflexive, symmetric, transitive, equivalence, graph, anti-symmetric, partial order, total order and lattice and design predicates to test a given relation for its inclusion to these classes.

leq[m1_, m2_] := 
      Apply[And, NonPositive  /@  Flatten[m1 - m2]]
square[
        m_] := (m . 
            m  /.  {x_  /;  x > 0  -> 
              1})

reflexiveQ[m_] := 
      leq[IdentityMatrix[Length[m]], m]

symmetricQ[{x_Integer}] := True
symmetricQ[m_] := (Transpose[m] == m)

transitiveQ[m_] := leq[square[m], m]

equivalenceQ[
        m_] := reflexiveQ[m]&&symmetricQ[m]&&transitiveQ[
          m]

graphQ[
        m_] := reflexiveQ[m]&&symmetricQ[
          m]

antiSymmetricQ[m_] := 
      leq[Partition[Flatten[m] Flatten[Transpose[m]], Length[m]], 
        IdentityMatrix[Length[m]]]

partialOrderQ[
        m_] := reflexiveQ[m] && antiSymmetricQ[
          m] && transitiveQ[
          m]

totalOrderQ[
        m_] := partialOrderQ[
          m]&&(Length[Cases[Flatten[m] + Flatten[Transpose[m]], 0]] == 
            0)

lubGlbQ[m_] := 
      Module[{n = Range[Length[m]], i, j, t}, 
t = 
          Flatten[Outer[List, n, n], 1]; 
And  @@ 
          Map[({i, 
                    j} = #; (m[[i, 
                        j]] == 
                      1) || ((Length[
                            Select[n, 
                              m[[i, #]] == 
                                  m[[
                                    j, #]] == 1 &, 1]] > 
                          0) && (Length[
                            Select[n, 
                              m[[#, i]] == 
                                  m[[#, 
                                    j]] == 1 &, 1]] > 
                          0))) &, t]]

latticeQ[m_] := partialOrderQ[m] &&  lubGlbQ[m]

1.- Reflexive Relations

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, reflexiveQ]] &\) /@ 
      Range[4]\)

Those numbers start off  as (see sequences A053763 and A053773 in [8]):

(2^(Range[7] (Range[7] - 1)))

2.- Symmetric Relations

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, symmetricQ]] &\) /@ 
      Range[4]\)

Those numbers start as (see sequence A006125 in [8]):

(2^(((Range[7] (Range[7] + 1))/2)))

3.- Transitive Relations

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, transitiveQ]] &\) /@ 
      Range[4]\)

(Sequence A006905 in [8])

4.- Equivalence Relations

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, equivalenceQ]] &\) /@ 
      Range[4]\)

(Sequence A000110 in [8])

5.- Graphs

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, graphQ]] &\) /@ 
      Range[4]\)

numbers that start as (sequence A006125 in [8]):

(2^(((Range[7] (Range[7] - 1))/2)))

6.- Anti-symmetric Relations

\(\(Length[
          Select[\(\(ℜ\)\(\ \)\)\_#, antiSymmetricQ]] &\) /@ 
      Range[4]\)

A different and quite illustrative way of testing for anti-symmetry is the following:

antiQ[
        m_] := (Length[
            Cases[Flatten[m - 2 IdentityMatrix[Length[m]]] + 
                Flatten[Transpose[m]], 2]] == 0)

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, antiQ]] &\) /@ 
      Range[4]\)

Those numbers start off as:

(2^Range)[7] (3^(((Range[7] (Range[7] - 1))/2)))

Note they are not the same as:

\(\(Length[
          Select[\(\(ℜ\)\(\ \)\)\_#, 
            Not[symmetricQ[#]] &]] &\) /@ Range[4]\)

7.- Partial Orders

\(\(Length[
          Select[\(\(ℜ\)\(\ \)\)\_#, partialOrderQ]] &\) /@ 
      Range[4]\)

(Sequence A001035 in [8])

8.- Total Orders

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, totalOrderQ]] &\) /@ 
      Range[4]\)

They start off as:

Range[7]!

9.- Lattices

\(\(Length[Select[\(\(ℜ\)\(\ \)\)\_#, latticeQ]] &\) /@ 
      Range[4]\)

(Sequence A055512 in [8])

10.- Other types

Further computations can also be performed. For instance, to find the number of symmetric-antisymmetric relations:

\(\(Length[
          Select[\(\(ℜ\)\(\ \)\)\_#, 
            symmetricQ[#] && antiSymmetricQ[#] &]] &\) /@ Range[4]\)

numbers that start as:

(2^Range)[7]

or also a unique occurrence:

\(\(Length[
          Select[\(\(ℜ\)\(\ \)\)\_#, 
            reflexiveQ[#] && symmetricQ[#] && antiSymmetricQ[#] &]] &\) /@ 
      Range[4]\)

We can also consider further classifications. Take for instance the relations mod m on Range[n]:

m = 3;
n = 10;
Table[If[Mod[i - j, m] == 0, 1, 0], {i, n}, {j, n}] // 
      MatrixForm

which can also be considered more generally:

m = 11;
n = 20;
ListDensityPlot[Table[Mod[i  j, m], {i, n}, {j, n}]];

Summary

n = 4;
Print["Of the ", 
        Length[(Subscript[ℜ, n])], " relations on a set of ", 
        n, " elements, there are:"];
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              reflexiveQ]], " reflexive relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              symmetricQ]], " symmetric relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              transitiveQ]], " transitive relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              equivalenceQ]], " equivalence relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              graphQ]], " graph relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              antiSymmetricQ]], " antiSymmetric relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              partialOrderQ]], " partial order relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              totalOrderQ]], " total order relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, 
              v}]]]]]
Print[
      v = Length[
          u = Select[(Subscript[ℜ, n]), 
              latticeQ]], " lattice relations like ", 
      MatrixForm[
        u[[Random[
            Integer, {1, v}]]]]]

Now, to each relation M let us associate a binary vector v of size 9 with entries corresponding to each of the above classes, wherein v[i]=True iff M is of type i. There are (2^9)=512 such, coded by the corresponding decimal digits. For a given n, let us compute a vector of length 512 whose i-th entry includes the number of relations in (Subscript[ℜ, n]) obeying the properties described by the binary number i.

data[n_] := 
      Map[{reflexiveQ[#], symmetricQ[#], transitiveQ[#], equivalenceQ[#], 
            graphQ[#], antiSymmetricQ[#], partialOrderQ[#], totalOrderQ[#], 
            latticeQ[#]} &, (Subscript[ℜ, n])]

v = Table[0, {512}];
Map[v[[# + 
                1]]++ &, FromDigits[#, 
              2] & /@  ( 
            data[4]  /.  {True -> 1, 
                False -> 0})];
v

So, there are 49228 relations not enjoying any property, 7650 being only antisymmetric (because the number 7650 occupies position (Subscript[000001000, 2])=8, counting the first as the "zero-th" one), 332 being only transitive, etc.  In order to find out the number of antisymmetric relations we have to add the numbers at positions

FromDigits[#, 2] & /@ 
        Select[IntegerDigits[Range[0, (2^9) - 1], 2, 
            9], #[[-4]] == 1 &] + 
      1

Plus @@  v[[%]]

The inmense majority of relations avoid our classification and there is only one enjoying all of them.

Equivalence Relations and Partial Orders

It seems that equivalence relations and partial orders are scarse and worth of being generated differently. They are both reflexive and transitive so first we generate such relations. We observe that the inclusion of the elements of the diagonal has no effect on the transitity law. Given an already transitive matrix, we add one element to it and add those elements implied by its presence in order to preserve transitivity.

Table[
      Length[u[[n]] = 
          Select[(Subscript[(ℜ ), n]), 
            reflexiveQ[#] && transitiveQ[#] &]], {n, 4}]

(Sequence A000798 in [8])

The following function extend takes a pair of elements forming a relation and extends it so that it becomes transitive (transitive closure)

extend[p_] := 
      Module[{t}, 
t[
            u : {___, {a_, b_ }, ___, {b_, c_ }, ___}] := 
          Append[u, {a, c} ]  /; (c ≠ a) && 
              Not[MemberQ[u, {a, c}]]; 
t[
            u : {___, {b_, c_ }, ___, {a_, b_}, ___}] := 
          Append[u, {a, c} ]  /; (c ≠ a) && 
              Not[MemberQ[u, {a, c}]]; 
t[x_] := 
          x; 

FixedPoint[t, 
          p]]

extend[{{1, 3}, {1, 2}, {2, 1}, {7, 1}}]

Function trans below works by extending (in the Do loop) throughout all possible elements, one at a time.

trans[n_] := trans[n] = 
        Module[{Ω, tr = {{}}, j, m, ans = {}, 
            b}, 
Ω = 
            Select[Flatten[Table[{i, j}, {i, n}, {j, n}], 1], 
              First[#] ≠ 
                  Last[#] &]; 

Do[
tr = 
              Union[Flatten[
                  Map[(m = #; 
b = 
                          Complement[Ω, 
                            m]; 
Sort[
                              extend[Join[{#}, m]]] & /@ b) &, tr], 
                  1]]; 
ans = 
              Join[ans, 
                tr], {n (n - 
                    1)}]; 

ans = 
            Union[ans]; 
(j = 
                  IdentityMatrix[
                    n]; 
m = #; 
(j[[First[#], Last[#]]] = 1) & /@ 
                  m; 
j) & /@ ans]

MatrixForm /@ trans[3]

Timing[Table[Length[trans[n]] + 1, {n, 5}]]

(+1 to include the identity. Timing taken on a 700 Mhz PC)

So, the number of equivalence relations is:

Table[Length[Select[trans[n], symmetricQ]] + 1, {n, 5}]

and the number of partial orders is:

Table[Length[Select[trans[n], antiSymmetricQ]] + 1, {n, 5}]

and the number of relations that are both equivalence and partial orders is:

Table[
      Length[Select[trans[n], (symmetricQ[#] && antiSymmetricQ[#]) &]] + 
        1, {n, 5}]

Set Partitions

If we are interested only in the enumeration of equivalence relations, Bell and Stirling numbers arise. The relation between set partitions and equivalence relations allow us to further simplify their enumeration and generation. For a positive integer m, let 𝒫(m) denote the set of all partitions of Range[m] into non-empty subsets. For positive integers m and n with n≤m, let 𝒫(m, n) denote the set of all partitions of Range[m] into exactly n non-empty subsets. The Bell numbers ℬ(m) = | 𝒫(m) | and the Stirling numbers of the second kind 𝒮(m, n) = | 𝒫(n, m) | are such that ℬ(m) = (∑_(n = 1)^m) S(n,  m). Moreover, they satisfy the following recursive definitions:

ℬ[0] := 1
ℬ[
        m_] := (∑_(i = 0)^(m - 1))Binomial[m - 1, 
            i] ℬ[
            i]

𝒮[0, 0] := 1
𝒮[_, 0] := 0 
𝒮[m_, n_] := 
      0  /;  n == m + 1
𝒮[m_, n_] := 0  /;  n > m
𝒮[m_, n_] := 
      n  𝒮[m - 1, n] + 𝒮[m - 1, 
          n - 1]

Table[ℬ[n], {n, 10}]

Table[𝒮[n, m], {n, 10}, {m, 10}]  //  
      MatrixForm

The sum of the last row must be equal to ℬ[10]. The numbers below or to the right of the 1´s form familiar sequences.

The following provides a function to generate set partitions in lexicographic order.

part[n_Integer] := part[Range[n]]
part[{x_}] := {{{x}}}
part[{x_, y___}] := 
      Module[{p = part[{y}], u}, 
Flatten[
          Map[(u = #; 
Join[{Join[{{x}}, u]}, 
                  MapIndexed[ReplacePart[u, Join[{x}, #1], #2] &,  u]]) &, 
            p], 1]]

part[4]

Visually more appealing:

\(t[{p__}] := \(StringJoin[ToString /@ {p}]\)\&_\)
(t /@ #) & /@ part[4]

Or, if  it is required the number 1 to appear in the first partition:

Sort[
      Map[(t /@ #) &, Sort[#, First[#1] < First[#2] &] &  /@  
          part[4]]]

Table[Length[part[n]], {n, 6}]

From the list of partitions we can recover all matrices corresponding to equivalence relations.

Conversely, an equivalence relation induces a partition of the base set. The identification of partitions and equivalence relations allows us to easily visualize the truth of non-trivial results such as the following:

If | A | = n,  then, for any n ≤ h ≤ (n^2), there is an equivalence relation H on A, with | H | = h, if and only if there exists a sequence of positive integers (Subscript[n, 1]), (Subscript[n, 2]), ..., (Subscript[n, k]) such that

(∑_(i = 1)^k) (Subscript[n, i]) = n    and    (∑_(i = 1)^k) ((Subscript[n, i])^2) = h

To see the correctness of this assertion, we only have to interpret k as the number of classes, (Subscript[n, i]) as the number of elements belonging to class i and recall the fact that an equivalence relation has associated a binary matrix in which the rows and columns can be relabeled in such a way that the matrix consists of diagonal blocks of ((Subscript[n, i])^2) 1´s each [4].

Functions

Functions are a special kind of relations, namely, those matrices having just a 1 in each row,  hence there are (n^n)of them, instead of (2^((n^2))), (for n = 4 there are 256 functions out of 65536 relations). It is easy to see that there is only one reflexive function, which also happens to be the only symmetric one, the only partial order, and the only equivalence relation.

\(\(#\^# &\) /@ Range[7]\)

(Sequence A000312 in [8])

Instead of filtering all relations to obtain those corresponding to functions, we directly generate them. We generate all type of rows first (n types with all zeroes except a single 1). Then we generate all numbers from 1 to (n^n) in a number system of base n, which provides us with a way to actually enumerate the functions. Each number in base n describes which type of corresponds to the associated function.

functions[1] := {{1}}
functions[n_] := functions[n] = 
        Module[{z, f, i}, 
z = 
            Table[0, {n}]; 
f = 
            1 + IntegerDigits[Range[0, (n^n) - 1], n, 
                n]; 
r = 
            Table[ReplacePart[z, 1, i], {i, n, 
                1, -1}]; 
Map[
            r[[#]] &, f]]

MatrixForm  /@  functions[3]

Let us now find out which of those are transitive

MatrixForm  /@  Select[functions[3], transitiveQ]

and symmetric:

MatrixForm  /@  Select[functions[3], symmetricQ]

Table[Length[Select[functions[n], transitiveQ]], {n, 6}]

(See sequence A000248 in [8])

Table[Length[Select[functions[n], symmetricQ]], {n, 6}]

(See sequence A000085 in[8])

Table[
      Length[Select[functions[n], transitiveQ[#] && symmetricQ[#] &]], {n, 
        6}]

To check for surjectivity we only have to check the transpose being also a function. Automatically we are checking for injectivity as all surjective functions are also injective ones.

surjectiveQ[m_] := 
      Positive[ Times  @@ Map[Plus  @@ # &,  Transpose[m]]]

MatrixForm  /@  Select[functions[3], surjectiveQ]

Table[Length[Select[functions[n], surjectiveQ]], {n, 2, 6}]

The above counts the number of permutations.They can be readily generated as:

\(permutations[n_] := 
      Module[{z = Table[0, {n}], f = Permutations[Range[n]], i}, 
		r = 
          Table[ReplacePart[z, 1, i], {i, n, 1, \(-1\)}]; 
		Map[
          r[[#]] &, f]]\)

MatrixForm  /@  permutations[3]

Conjecture: Symmetry implies surjectivity.

Table[
      Length[ Select[functions[n], 
          symmetricQ[#] && Not[surjectiveQ[#]] &]], {n, 2, 6}]

Connected Relations and Trees

Any relation can be depicted as a multigraph. In order to find out quickly whether the matrix of a relation corresponds to a connected multigraph we examine its power:

connectedQ[m_] := 
      Module[{n = Length[m], r}, 
r = 
          m + IdentityMatrix[n]; 
Position[
            MatrixPower[r, n], 0] == {}]

MatrixForm /@  Select[(Subscript[ℜ, 2]), connectedQ]

\(\(Length[Select[ℜ\_#, connectedQ]] &\) /@ \ 
      Range[4]\)

MatrixForm  /@  Select[functions[3], connectedQ]

Length[Select[functions[#], connectedQ]] & /@  Range[6]

Trees are connected acyclic graphs; equivalently, graphs having 3 |m| -2 1´s

treeQ[
        m_] := ((Plus @@  Flatten[m]) == 3  Length[m] - 2) && 
        graphQ[m]

\(\(MatrixForm /@ Select[ℜ\_#, treeQ] &\) /@ \ 
      Range[4]\)

(See sequences A003150 and A006963 in [8])

PART II SELECTIVE ENUMERATION

Of the 16 relations forming the set (Subscript[ℜ, 2]), only 10 are different under relabeling. By renaming the elements {1,2,3} as, say, {3,1,2} respectively, matrix m below gets transformed into a structurally  equivalent (isomorphic) one:

m=(({{0, 1, 1}, {1, 0, 0}, {1, 1, 1}}));
Plus  @@  
      m
Transpose[Transpose[
            m[[{3, 1, 
                2}]]][[{3, 1, 
            2}]]]  // MatrixForm

The 10 non-isomorphic relations we mentioned previously are obtained through the following:

n = 2;
ans = {};
u = (Subscript[ℜ, n]);
p = Permutations[Range[n]];
While[u ≠ {}, 
        AppendTo[ans, 
          First[u]]; 
t = (Transpose[Transpose[First[
                          u][[#]]][[#]]] & /@ 
              p); 
u = 
          Complement[u, t]
];
MatrixForm /@  ans

Note that the identity relation and the one obtained by swapping its rows are non-isomorphic. Similarly, from the relations on Range[3], only 104 are non-isomorphic.

n = 3;
ans = {};
u = (Subscript[ℜ, n]);
p = Permutations[Range[n]];
While[u ≠ {}, 
        AppendTo[ans, 
          First[u]]; 
t = (Transpose[Transpose[First[
                          u][[#]]][[#]]] & /@ 
              p); 
u = 
          Complement[u, t]
];
Length[ans]

However, if we want to find out how large is the set of non-isomorphic relations by exhaustive enumeration on Range[4] we find it intolerably time-consuming (on a 700 MHz PC) when using this procedure.

This section will aim at solving the problem of counting how many distinct relations, taken from a number of important categories, can be defined on a finite set, the distinction being made upon non-isomorphic structures. We accomplish this by using a tool from computational group theory called Burnside´s Lemma, which applies whenever the criteria to distinguish two configurations depends heavily on symmetry properties of the underlying set; this symmetry is described by the action of a group on the set [3, 5].

In the following, we will obtain a formula for the number of non-isomorphic relations by exploiting symmetry properties of the set of permutations that give rise to isomorphic versions of each of the possible relations.

	Let (Subscript[𝔖, n]) be the symmetric group, that is, the group of all permutations on Range[n]. For every relation A ϵ (Subscript[ℜ, n]) and permutation π ϵ (Subscript[𝔖, n]), we define a transformation  (Subscript[𝔱, π]) : (Subscript[ℜ, n]) ->(Subscript[ℜ, n]) by the rule

\(\(𝔱\_π\) \((A)\) = \(\(𝔱\_π\) \((\([a\_\(i, j\)]\))\) = \([a\_\(\(π\^\(-1\)\) \((i)\), \(π\^\(-1\)\) \((j)\)\)]\)\)\)

For example, if A=(({{0, 1, 1, 1}, {1, 0, 0, 1}, {0, 1, 1, 0}, {0, 0, 1, 0}})) ϵ  (Subscript[ℜ, 4]) and π=(({{1, 2, 3, 4}, {4, 1, 2, 3}}))ϵ (Subscript[𝔖, 4]), then (π^(-1))=(({{1, 2, 3, 4}, {2, 3, 4, 1}})) and (Subscript[𝔱, π])(A)=(({{0, 0, 1, 1}, {1, 1, 0, 0}, {0, 1, 0, 0}, {1, 1, 1, 0}})). These results can be obtained by using definition (1) or, alternatively, by interpreting it as the result of rows and columns swapping, that is, first we move the rows of A according to π to obtain (({{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 0, 1, 0}, {0, 1, 1, 1}}))and then the columns to obtain the final result.

Now, let A, B ∈ (Subscript[ℜ, n]). We say that A and B are isomorphic if there is a π ϵ (Subscript[𝔖, n]) such that (Subscript[𝔱, π])(A)=B. 

As the algebraic structure of the set { (Subscript[𝔱, π]) |  π ϵ (Subscript[𝔖, n])} is identical with that of (Subscript[𝔖, n]) itself, the concept of isomorphism as equivalence can be seen as an action of (Subscript[𝔖, n]) onto (Subscript[ℜ, n]) [5]. So, the question of counting the number of non-isomorphic relations on (Subscript[ℜ, n]) is the same as aking how many orbits does this action induce on (Subscript[ℜ, n]). By Burnside´s Lemma [1, 5], this number, denoted by struct(n), is given by

\(struct \((n)\) = \(1\/\(n!\)\) \(∑\+\(π\ ϵ\ 𝔖\_n\)Fix \((𝔱\_π)\)\)\)

where Fix((Subscript[t, π])) is the number of relations fixed by (Subscript[t, π]). Equivalently, by just counting over representatives of conjugation classes:

struct (n) = (∑_([π]))n (π) 
          Fix ((Subscript[𝔱, π]))

Wherein, if the cycle structure of π, or any representative of its class is \(TraditionalForm\`\(\(x\_1!\)\ \(1\^x\_1\) \(x\_2!\)\ 2\^x\_2 ... \) \(x\_n!\)\ n\^x\_n\), then

n (π)=(1/(\(\(\(x\_1!\)\ \(1\^x\_1\) \(x\_2!\)\ 2\^x\_2 ... \) \(x\_n!\)\ n\^x\_n\)))

Our problem can then be stated as follows: given a conjugate class of (Subscript[𝔖, n]), how many relations are fixed by any of its representatives (hence by all members of the class)?

Let  π ϵ (Subscript[𝔖, n]). If  π is an n-cycle [6], then there are only two relations fixed by (Subscript[𝔱, π]), namely those in which the elements of their matrices are all zero or all unity. Let us then assume that this is not the case and that (Subscript[𝔱, π])(A)=A for some relation A and that π contains the cycles ((Subscript[x, 1])  (Subscript[x, 2]) ... (Subscript[x, h])) and ((Subscript[y, 1]) (Subscript[y, 2]) ... (Subscript[y, k])). Let (Subscript[A, 0]) be the submatrix of A consisting exclusively of the rows (Subscript[x, 1]), (Subscript[x, 2]), ..., (Subscript[x, h]) and columns (Subscript[y, 1]), (Subscript[y, 2]), ..., (Subscript[y, k]) of A. (Subscript[A, 0]) is, in general, build up from disconnected parts of A.

The effect of π on A completely resides on (Subscript[A, 0]); the cycles of  π are disjoint, so, in computing 𝔱(A) row movements are not followed by column movements and viceversa as was the case previously. Further, the requirement (Subscript[𝔱, π])(A) = A forces the following hk equations to hold:

Let (Subscript[a, (Subscript[x, i]), (Subscript[y, j])]) be a typical entry of (Subscript[A, 0]); then

(Subscript[a, (Subscript[x, i]), (Subscript[y, j])])=(Subscript[a, (Subscript[x, i + 1]), (Subscript[y, j + 1])])=(Subscript[a, (Subscript[x, i + 2]), (Subscript[y, j + 2])])= ... = (Subscript[a, (Subscript[x, i + hk]), (Subscript[y, j + hk])])

where the row and column indices are computed mod h and mod k respectively (mod operations will be taken over positive representatives 1, 2, ..., n. For instance, if n=6, then 5+5=4 and 4+2=6). This corresponds to a path traversed by a bishop over a toroidal chessboard, which may possibly lead to a complete traversal of (Subscript[A, 0]) (see Figure 1), reminding of the well-known fact [3, 4] that, if n and m are co-prime and Cn denotes the set of all residual classes mod n, then, regarded as group structures, the sets Cn × Cm and Cnm are isomorphic.

Example 1

Let π=(1 4 2)(3)(5 6) and let A=(({{1, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 1, 0}, {0, 0, 1, 1, 0, 0}, {0, 0, 1, 1, 0, 0}, {0, 1, 0, 0, 1, 0}, {1, 0, 0, 0, 0, 1}})) be a candidate to be tested as fixed by (Subscript[𝔱, π]). Let us, for instance, consider the cycles (1 4 2) and (5 6). Then (Subscript[A, 0])=(({{0, 1}, {1, 0}, {0, 0}}))(note that the internal order of the cycles does not matter). Also, the equation (Subscript[𝔱, π]) (A) = A  implies that \(a\_\(1, 5\) = \(a\_\(4, 6\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = \(a\_\(4, 5\) = a\_\(2, 6\)\)\)\)\)\)  . This amounts to say that all elements of  (Subscript[A, 0 
])should be equal. Hence, A is not fixed by (Subscript[𝔱, π]). Let us note that, if h and k are co-prime, only the first LCM(h, k) equations are different, while the other merely repeat them. For instance, if π = (1 2)(3 4 5 6), then (Subscript[A, 0])=(({{0, 0, 0, 1}, {0, 0, 1, 0}}))and

\(\(𝔱\_π\) \((A)\) = \(A\ \ \ \ \ ⟹\ \ \ \ a\_\(1, 3\) = \(a\_\(2, 4\) = \(a\_\(1, 5\) = \(a\_\(2, 6\) = \(a\_\(1, 3\) = \(a\_\(2, 4\) = \(a\_\(1, 5\) = 
                    a\_\(2, 6\)\)\)\)\)\)\)\)\)

Therefore, instead of eight equations, we will have four (the last four were written following the indices combinations and to point out that redundant information can arise this way). To span the complete set of possibilities, that is, encompass all elements of (Subscript[A, 0]) as indicated, we have to choose a new entry and repeat the procedure, that is,

\(a\_\(1, 4\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = \(a\_\(2, 3\) = \(a\_\(1, 4\) = \(a\_\(2, 5\) = \(a\_\(1, 6\) = a\_\(2, 3\)\)\)\)\)\)\)\).

In this case, as we needed to iterate the process twice, we will say that (Subscript[A, 0]) has 2 degrees of freedom. In other words, there are two families that arise in this manner and can independently be assigned local equal values. In general, the degree of freedom of (Subscript[A, 0]) under π is equal to GCD(h, k).

Extending the concept of degrees of freedom to the original matrix A we note that, by disjointness, the degrees of freedom of each block of π are unaffected by those in any other block. So, the degree of freedom of A, denoted by d(π), can be taken as the sum of the degrees of every pair of cycles of A. As an illustration of this consider the following example. Let us compute d(π) for π=(1 4 2)(3)(5 6) for an arbitrary matrix R of size 6x6. All possible pairings of cycles follow the pattern described in Figure 2. The results are given in Table 1.

Hence, the degree of freedom of R is d(π)=12. Consequently, π induces the following subdivision of R, where elements of the same tag must coincide; the subindices correspond to several choices made locally to span all elements of the corresponding blocks, these choices amount to the respective degrees of freedom of their blocks (see Figure 3)

(({{(Subscript[A, 1]), (Subscript[A, 3]), B, (Subscript[A, 2]), C}, {(Subscript[A, 2]), (Subscript[A, 1]), B, (Subscript[A, 3]), C}, {D, D, E, D, F}, {(Subscript[A, 3]), (Subscript[A, 2]), B, (Subscript[A, 1]), C}, {G, G, H, G, (Subscript[I, 1])}, {G, G, H, G, (Subscript[I, 2])}}))

Therefore, there are (2^12) relations fixed by (1 4 2)(3)(5 6). We can conclude that, in general, Fix((Subscript[𝔱, π]))=(2^(d(π))).

To get an explicit expression for d(π) for any permutation π we only need to count how many pairs of cycles are considered. It is easy to see that, if π is of type (Subscript[(1^x), 1]) (Subscript[(2^x), 2])  ...  (Subscript[(n^x), n]), there are (((Σ(Subscript[x, i])))^2) different pairings. A pairing of a cycle of length h with one of length k will contribute to d(π) with an amount of GCD(h, k); as there are (Subscript[x, h]) of type h and (Subscript[x, k]) of type k, its local contribution to the grand total will be (Subscript[x, h])(Subscript[x, k]) GCD(h, k) (Note: as d( (1 2 ... n) ) = n and d( (1)(2) ...(n) ) = (n^2), we know that n ≤ d(π) ≤ (n^2) . More generally, if π is of type (i^a)(j^b) where ai + bj = n, then d(π)=(a^2) i +2ab GCD(i, j) + (b^2) j).  We thus arrive at the following result.

Theorem 1. 	The number of non-isomorphic relations on a set of n elements is given by

(∑_([π]))n (π) (2^(d (π)))

where the sum is taken over representatives π of the conjugacy classes of (Subscript[𝔖, n]) having type (Subscript[(1^x), 1]) (Subscript[(2^x), 2]) ...  (Subscript[(n^x), n]) and

d (π) = (∑_(h, k = 1)^n) (Subscript[x, h]) (Subscript[x, k]) 
          GCD (h, k)
\(n \((π)\) = 
      1\/\(\(\(x\_1!\) \(1\^x\_1\) \(x\_2!\) 2\^x\_2 ... \)\ \(x\_n!\) n\^x\_n\)\)

The latter result can be readily implemented. Given a permutation per, functions getType, d and n below compute its type as a weighted vector, d[per] and n[per] from Theorem 1:

<< DiscreteMath`Combinatorica`

getType[per_] := 
      Module[{t = Table[0, {Length[per]}], 
          c = Map[Length[#] &, 
              ToCycles[
                per]]}, 
Map[t[[#]]++ &, 
          c]; 
t]

d[per_] := 
      Module[{t = getType[per], h, k, 
          n = Length[per]}, 
Sum[
          t[[h]] t[[
              k]] GCD[h, k], {h, n}, {k, 
            n}]]

n[per_] := 
      Module[{t = getType[per]}, 
1/
          Apply[Times, t! (((Range[Length[t]]))^t)]]

For example, to obtain the type of all the permutations comprising (Subscript[𝔖, 3]):

s3 = Permutations[Range[3]]
getType[#] & /@  s3

That is, permutation {1, 2, 3} is the product of 3 cycles of length 1, permutation {3, 2, 1} is the product of a cycle of length 1 and a cycle of length 2, etc. Similarly, we obtain their respective d and n values and calculate their contribution to the final sum in theorem 1 as follows:

n /@ s3
d /@ s3
n[#] (2^d)[#] & /@ s3

Finally, to implement the full expression we need to add only those values in the last of the vectors above corresponding to class representatives, which in this case occupy the first, second and fourth positions, providing the answer 104 to the question of how many non-isomorphic relations on a set of 3 elements do exist in the latter example. In general, this value can be computed by just adding those corresponding to permutations of different types. In the code below, this mechanism is implemented in the Do block, which relies on the Mathematica function Union to remove repeated elements thereafter.

numRelations[m_] := 
      Module[{p = Permutations[Range[m]], t, i, 
          q}, 
t = getType[#] & /@ 
            p; 
Do[
If[
            MemberQ[Take[t, i - 1], 
              t[[i]]], 
            p[[i]] = First[p]], {i, 
            2, m!}]; 
p = 
          Union[p]; 
Plus  @@  
          Map[n[#] (2^d)[#] &, p]]

numRelations[3]

Although this implementation of theorem 1 is adequate, it is time-consuming. We can produce a more satisfactory design by removing the overhead caused by generating all permutations in order to select representatives of conjugacy classes. This optimization arises from first solving the following problem:

To obtain all the solutions in non-negative integers of the equation:

(Subscript[x, 1]) + 2  (Subscript[x, 2]) +   ...   +  n (Subscript[x, n]) = m

where n and m are two given non-negative integers.

The function that computationally solves this problem is:

generate[1, m_] := {{m}}
generate[n_, m_] := 
      Module[{i, s = {}}, 
        Do[s = Join[s, Map[Append[#, i] &, generate[n - 1, m - n i]]], {i, 
            0, ⌊m/
                n⌋}]; 
s]

For instance, to find out the solutions to the Diophantine equation  (Subscript[x, 1])+2(Subscript[x, 2])+3(Subscript[x, 3])+4(Subscript[x, 4])+5(Subscript[x, 5])=5:

generate[5, 5]

Note: we could also have used the following non-recursive method for the case n=m:

f[d_, m_] := 
      Module[{s = Table[0, {m}]}, 
        Map[s[[#]]++ &, d]; 
        s]

buildTypes[m_] := f[#, m] &  /@  
        Partitions[m]

buildTypes[5]

Function numRel below makes use of such vectors as descriptions of the types of representatives of conjugate classes and improves substantially on the straighforward approach adopted in our previous design of function numRelations.

d[t_] := 
      Module[{h, k, n = Length[t]}, 
Sum[
          t[[h]] t[[
              k]] GCD[h, k], {h, n}, {k, 
            n}]]

n[t_] := 1/
        Apply[Times, t! (((Range[Length[t]]))^t)]

numRel[m_] := 
      Module[{g = 
            buildTypes[
              m]}, 
Plus  @@  ((n /@  
                  g) (2^((d  /@  g))))]

Finally, a table comparing the first ten values of the total number of relations and the total number of non-isomorphic relations can be obtained through the following:

Table[{i, (2^((i^2))), numRel[i]}, {i, 8}] // TableForm

(See sequence A000595 in [8])

Reflexive and Symmetric Relations

Let us now specialise Burnside’s theorem firstly to the counting of non-isomorphic reflexive relations and subsequently to non-isomorphic symmetric relations. The result is contained in the following theorem.

Theorem 2	The number of non-isomorphic reflexive relations on an n-set is given by

\(∑\+\([π]\)n \((π)\) 2\^\(d´ \((π)\)\)\)

where  d´(π)=d(π)-(∑_(k = 1)^n) (Subscript[x, k]), with n(π) and d(π) as in theorem 1.
 
Proof:	In a reflexive relation, all diagonal elements (Subscript[a, i,  i]) are equal to unity. Also, the diagonal elements are always permuted among themselves by every (Subscript[𝔱, π]). Hence, the number of degrees of freedom is equal to the number of cycles in π, that is, Σ(Subscript[x, k]). □

numRelReflexive[m_] := 
      Module[{g = 
            buildTypes[
              m]}, 
Plus  @@ ((n /@ 
                  g) (2^((d /@ g) - ((Plus  @@ #) & /@ g))))]

Table[{i, (2^(i (i - 1))), numRelReflexive[i]}, {i, 8}] // 
      TableForm

(See sequence A000273 in[8])

Note that the number of non-isomorphic reflexive relations coincide with that for irreflexive relations, i.e., those for which all diagonal elements of the associated matrix are null.

Let us now approach the problem of finding out how many non-isomorphic symmetric relations can be defined on an n-set. Concerning example 1, our new condition implies a reduction in the degrees of freedom of the matrix A because symmetry implies (Subscript[A, 2])= (Subscript[A, 3]), B = D, C = G and F = H, and hence, its degrees of freedom reduce to 12-4 = 8 and Fix(\(TraditionalForm\`𝔱\_\(\((1\ 2\ 4)\) \((3)\) \((5\ 6)\)\)\)) = (2^8).

Example 2

Let us compute d(π) for π=(1)(2 3)(4 5)(6) for an arbitrary matrix 6 × 6. All possible pairings of cycles follow the pattern described in Figure 4, inducing the subdivision of A shown therein, where elements of the same tag must coincide. The results are summarised in Table 2. Then, the degree of freedom of A is d(π)=20. If symmetry is considered, we will have: B = E, C = I, D =M, (Subscript[J, 1]) = (Subscript[G, 1]), (Subscript[J, 2]) = (Subscript[G, 2]), H = N and L =O.

We sum up our results in the following theorem.

Theorem 3	The number of non-isomorphic symmetric relations on an n-set is given by

sym(n)=(∑_([π]))n(π) 
          (2^(dsym(π)))

where

dsym (π) = (∑_(h = 1)^n) 
                (Subscript[x, h]) (⌊(h/2)⌋ + 
                1) + (∑_(h = 1)^n) 
                (Subscript[x, h]) ((h ((Subscript[x, h]) - 1))/2) + (∑_(h < k))(Subscript[x, h]) 
            (Subscript[x, k]) GCD (h, k)

and n(π) is as in theorem 1.

Let us classify the blocks (Subscript[A, 0]) induced by the pairing of the cycles as diagonal or non-diagonal according to whether they contain elements of the main diagonal of A or not. (In example 2, F is a diagonal block whereas G and B are not; in example 1, blocks A and E are diagonal (the fact that A is disconnected makes no difference) while B and C are not.

Non-diagonal blocks subdivide further into squares and non-square ones. In example 2, block G is square and H is not; in example 1, block C is square while F is not.

Non-diagonal blocks fall into transpose pairs; symmetry thus makes no change in d(π) within each block but since every one determines its reflection, the d(π) for all of these can be determined from half of them, say those below the diagonal. The third sum counts the non-square ones below the diagonal.

A diagonal block has its rows and columns permuted by the same h-cycle and will have h degrees of freedom.

Example 3

For the permutation (1 2 3 4 5)(1 2 3 4 5) the block has the form

(({{(Subscript[A, 1]), (Subscript[A, 2]), (Subscript[A, 3]), (Subscript[A, 4]), (Subscript[A, 5])}, {(Subscript[A, 5]), (Subscript[A, 1]), (Subscript[A, 2]), (Subscript[A, 3]), (Subscript[A, 4])}, {(Subscript[A, 4]), (Subscript[A, 5]), (Subscript[A, 1]), (Subscript[A, 2]), (Subscript[A, 3])}, {(Subscript[A, 3]), (Subscript[A, 4]), (Subscript[A, 5]), (Subscript[A, 1]), (Subscript[A, 2])}, {(Subscript[A, 2]), (Subscript[A, 3]), (Subscript[A, 4]), (Subscript[A, 5]), (Subscript[A, 1])}}))

and symmetry implies that (Subscript[A, 2])=(Subscript[A, 5]) and (Subscript[A, 3])=(Subscript[A, 4]). 

In general, the symmetry property will reduce their h degrees of freedom to  d(π) = ⌊h/2⌋ + 1. There are (Subscript[x, h]) of them, hence the first sum in theorem 3. Since, for each value of h the non-diagonal square blocks have h degrees of freedom and there are (Subscript[x, h])((Subscript[x, h]) - 1)/2 of them, the second sum accounts for it. For instance, we dissect  example 2 at Figure 4. Note that the same result is obtained by applying the induced symmetry conditions B=E, C=I, D=M, (Subscript[J, 1])=(Subscript[G, 1]), (Subscript[J, 2])=(Subscript[G, 2]), H=N and L=O.

Also, in example 1:

\(dsym \((\((1\ 4\ 2)\) \((3)\) \((5\ 6)\))\) = \(\([\(x\_1\) \((1)\) + \(x\_2\) \((2)\) + \(x\_3\) \((2)\)]\) + 
\([\(\(x\_1\) \((x\_1 - 1)\)\)\/2 + \(x\_2\) \((x\_2 - 
                    1)\) + \(x\_3\) \(3 \((x\_3 - 1)\)\)\/2]\) + 
\([\(x\_1\) \(x\_2\) GCD \((1, 2)\) + \(x\_1\) \(x\_3\) 
                GCD \((1, 3)\) + \(x\_2\) \(x\_3\) GCD \((2, 3)\)]\) = \(5 + 
            0 + 3 = 8\)\)\)

Finally, the following code implements function dSym referred to in theorem 3.

dSym[per_] := 
      Module[{h, k, n = Length[per]}, 
        Sum[per[[h]] (⌊h/
                      2⌋ + 1), {h, n}] + 
          Sum[per[[
                h]] h (per[[
                      h]] - 1)/2, {h, n}] + 
          Sum[per[[
                h]] per[[
                k]] GCD[h, k], {h, n}, {k, h + 1, 
              n}]]

numRelSym[m_] := 
      Module[{g = 
            buildTypes[
              m]}, 
Plus  @@ ((n /@ 
                  g) (2^dSym) /@ g)]

Table[{i, (2^(((i (i + 1))/2))), numRelSym[i]}, {i, 8}] // 
      TableForm

(See sequence A000666 in[8])

Functions

As our final case study, we will proceed with the counting of non-isomorphic functions. Let A be the matrix of a given function, i.e., having only one digit 1 in each row. We want to find out how many of the (n^n) functions mapping the set {1, ..., n} to itself are non-isomorphic.

Lemma		If (Subscript[A, 0]) is a d × k block under  of the functional matrix A then

1)  If k is not a factor of d, (Subscript[A, 0]) consists entirely of zeroes

2)  If k is a factor of d, (Subscript[A, 0]) has d 1's or none. Moreover, there are k different ways in which d 1's can be chosen in (Subscript[A, 0]).

Proof:	CASE 1. If k is not a factor of d, then LCM(d, k)>d so that, if (Subscript[a, i, j])=1 then there is a  distinct entry in the i-th row, namely (Subscript[a, i + d,  j + d]) which is also 1, contradicting the assumption that A is a function.
For instance, if π=(1 4 2)(3)(5 6) and (Subscript[A, 0]) is the block corresponding to the cycles (1 4 2) and (5 6), (Subscript[t, π])(A)=A , which means that all elements of (Subscript[A, 0]) must be the same.
CASE 2. If k is a factor of d, any one of the k elements of the d-th row can be chosen to take the value 1 and this choice determines all k 1's of the block.	□

For instance, if π=(1 2 3 4)(5 6),  (Subscript[A, 0])=(({{x, y}, {y, x}, {x, y}, {y, x}}))  and, if π=(1 2 3 4 5 6)(7 8 9),  (Subscript[A, 0])=(({{x, y, z}, {z, x, y}, {y, z, x}, {x, y, z}, {z, x, y}, {y, z, x}}))

Theorem 4	The number of non-isomorphic functions from a set of n elements to itself is given by:

fun (n) = (∑_([π]))n (π) 
          Fix ((Subscript[𝔱, π]))

where  Fix((Subscript[t, π]))=\(TraditionalForm\`∏\+\(k = 1\)\%n\((∑\+\(h | k\)h\ x\_h)\)\^x\_k\) and n(π) is as in theorem 1.

Proof:	The different possible ways of choosing the 1's in the matrix A can be counted in terms of horizontal bands across A corresponding to the cycles of  as shown in Figure 6. □

The previous theorem establishes that, for each k-cycle of the (Subscript[x, k]) present, there will be (∑_(h | k))h (Subscript[x, h]) ways of choosing the 1's. For instance, in example 1, blocks A and B have together 4 ways of choosing the 1's as k=3 and 1(Subscript[x, 1])+3(Subscript[x, 3]) = 4.
Independence of the choices in different bands determines the result. 

Example 4.	In example 1, the function property forces the matrix A to be of the form

(({{(Subscript[A, 1]), (Subscript[A, 3]), B, (Subscript[A, 2]), 0, 0}, {(Subscript[A, 2]), (Subscript[A, 1]), B, (Subscript[A, 3]), 0, 0}, {0, 0, 1, 0, 0, 0}, {(Subscript[A, 3]), (Subscript[A, 2]), B, (Subscript[A, 1]), 0, 0}, {0, 0, H, 0, (Subscript[I, 1]), (Subscript[I, 2])}, {0, 0, H, 0, (Subscript[I, 2]), (Subscript[I, 1])}}))

and Fix ((Subscript[t, π])) = 12 as shown in Figure 7.

fix[per_] := 
      Module[{p = 1, s, h, k}, 
Do[
          s = 0; 
Do[
            If[Mod[k, h] == 0, 
              s = s + h*per[[h]]], {h, 
              k}]; 
If[
            per[[k]] == 0, , 
            p = p (s^per)[[k]]], {k, 
            Length[per]}];  
p]

numFun[m_] := 
      Module[{g = 
            buildTypes[
              m]}, 
Plus  @@ ((n /@ g) (fix /@ 
                  g))]

Table[{i, (i^i), numFun[i]}, {i, 8}] // TableForm

(See sequence A001372 in[8])