Counting Transitive Relations

Götz Pfeiffer Department of Mathematics National University of Ireland, Galway Ireland

                  goetz.pfeiffer@nuigalway.ie

Abstract

In order to count partial orders on a set of n points, it seems necessary to explicitly construct a representative of every isomorphism type. While that is done, one might as well determine their automorphism groups. In this note it is shown how several other types of binary relations can be counted, based on an explicit enumeration of the partial orders and their automorphism groups. A partial order is a transitive, reflexive, and antisymmetric binary relation. Here we determine the number of quasi-orders q(n) (or finite topologies or transitive digraphs or reflexive transitive relations), the number of “soft” orders s(t) (or antisymmetric transitive relations), and the number of transitive relations t(n) on n points in terms of numbers of partial orders with a given automorphism group.

1 Introduction.

A partial order on a set X with n elements is a binary relation on X which is transitive, reflexive and antisymmetric. We denote by P(n) the number of different partial orders on n labelled points (sequence \underline{A001035}), and by p(n) the number of partial orders on n unlabelled points (sequence \underline{A000112}). In this note we assume the numbers P(n) and p(n) to be available. For p(n) we even assume the availability of an explicit list, or an enumeration procedure like the ones developed by Heitzig and Reinhold [5], or more recently by Brinkmann and McKay [2]. From the latter article, p(n) is known for n ≤ 16 and P(n) is known for n ≤ 18.

A “labelled” binary relation on X is a set of pairs R ⊆ X × X. If the actual names of the points being related are of no importance we talk about “unlabelled” binary relations. Technically, these are orbits of the action of the symmetric group Sym(X) on X × X. Here the image of a binary relation R on X under a permutation α ∈ Sym(X) is the relation R.α = {(x.α, y.α) | (x, y) ∈ R}.

Figure 1: Different types of binary relations.

Figure 1 shows the different kinds of binary relations that can be defined in terms of the properties reflexive (R), symmetric (S), transitive (T), antisymmetric (A), irreflexive (I), and all possible combinations thereof. Clearly no relation on n > 0 points can be both reflexive and irreflexive. The shaded areas indicate other impossible combinations: transitive and irreflexive implies antisymmetric; antisymmetric and symmetric implies transitive. The dotted areas indicate singleton sets: the only antisymmetric equivalence relation on n > 0 points is the identity relation; the only irreflexive transitive relation on n > 0 points which is both symmetric and antisymmetric is the empty relation.

Partial orders are particularly difficult to enumerate, be it labelled or unlabelled. Table 1 lists the different kinds of relations together with formulas and references to integer sequences (from the Online Encyclopedia of Integer Sequences [11]) for the numbers of such relations, both labelled and unlabelled. The numbers of many kinds of labelled binary relations are given by simple formulas. Kinds of irreflexive relations (if they exist) have the same number formulas as the corresponding reflexive kinds and therefore have been left out. The terms Q(n), S(n), T(n), and their lowercase counterparts will be introduced below, E(n) denotes the number of equivalence relations on n points, a sequence known as the Bell numbers, and e(n) is the number of partitions of n. Classical sources for some of these sequences and the formulas relating them are for example the books by Harary and Palmer [4], or by Graham, Knuth and Patashnik [3]. Some types of unlabelled binary relations can be easily enumerated with the help of Pólya theory, a group theoretical technique that translates the orbit counting problem into a problem of counting fixed points (see for example [8]). The problem of counting the types of transitive relations does not seem to have received much attention so far.

However, in order to count partial orders on a set of n points, it seems necessary to explicitly construct a representative of every isomorphism type. While that is done, one might as well determine their automorphism groups. This is the point of view taken here. In this note it is shown how several other types of binary relations can be counted, based on an explicit enumeration of the partial orders and their automorphism groups. More precisely, we determine the number of quasi-orders q(n) (or finite topologies or transitive digraphs or

Properties # Labeled Relations  # Unlabeled Relations on n points
(none) 2^{n^{2}} = \underline{A002416}(n)  \underline{A000595}(n)  all relations
R  4^{\binom{n}{2}} = \underline{A053763}(n)  \underline{A000273}(n)  reflexive
S  2^{\binom{n+1}{2}} = \underline{A006125}(n+1) \underline{A000666}(n)  symmetric
T  T(n) = \underline{A006905}(n)  t(n) = \underline{A091073}(n)  transitive
A 2^{n}3^{\binom{n}{2}} = \underline{A083667}(n)  \underline{A083670}(n)  antisymmetric
RS  2^{\binom{n}{2}} = \underline{A006125}(n)  \underline{A000088}(n)  simple graphs
R T  Q(n) = \underline{A000798}(n)  q(n) = \underline{A001930}(n)  quasi-orders
R A 3^{\binom{n}{2}} = \underline{A047656}(n)  \underline{A001174}(n)
ST  E(n+1) = \underline{A000110}(n+1) e(0) + ⋯ + e(n) = \underline{A000070}(n)
TA S(n) = \underline{A091566}(n)  s(n) = \underline{A079265}(n)  soft orders
RST  E(n) = \underline{A000110}(n)  e(n) = \underline{A000041}(n)  equivalences
R TA P(n) = \underline{A001035}(n)  p(n) = \underline{A000112}(n)  partial orders
STA 2^{n} = \underline{A000079}(n)  n+1 = \underline{A000027}(n+1) subsets

Table 1: Numbers of binary relations.

reflexive transitive relations), the number of “soft” orders s(n) (or antisymmetric transitive relations), and the number of transitive relations t(n) on n points in terms of numbers of partial orders with a given automorphism group.

Quasi-Orders. A binary relation ⪯ on X that is only required to be transitive and reflexive is called a quasi-order. Such a relation may allow both x ⪯ y and y ⪯ x to hold for certain pairs x, y ∈ X. But then, the symmetric core ≡ of ⪯, defined by

x ≡ y if and only if x ⪯ y and y ⪯ x,  (1)

clearly is an equivalence relation on X. Moreover, ⪯ can be used to define a relation ⊑ on the quotient set X/≡ of equivalence classes [x] = {y ∈ X : x ≡ y} as

[x] ⊑ [y] if and only if x ⪯ y.  (2)

Clearly, the relation ⊑ is a partial order on X/≡. Conversely, given an equivalence relation ≡ on X together with a partial order ⊑ on the equivalence classes X/≡ = {[x] : x ∈ X}, condition (2) defines a quasi-order ⪯ on X.

Thus a quasi-order on X is a partition L of X together with a partial order on L. If we denote by 𝒫(S) the set of partial orders on a set S, by 𝒬(X) the set of quasi-orders on X, and by Λ(X, k) the set of partitions of X into k nonempty parts L_{1}, …, L_{k}, then

#𝒬(X) = ∑_{k} ∑_{L∈Λ(X,k)} #𝒫(L) = ∑_{k} P(k) #Λ(X, k).  (3)

We denote by Q(n) the number of labelled quasi-orders on n points (sequence \underline{A000798}) and by q(n) the number of unlabelled quasi-orders on n points (sequence \underline{A001930}). The number of partitions of a set X of size |X| = n into k nonempty parts is given by a Stirling number of the second kind,

|Λ(X, k)| = \left⟨{n \atop k}\right⟩ .  (4)

It follows that the total number Q(n) of reflexive transitive relations on n labelled points can be expressed in terms of the numbers P(k) of labelled partial orders on k points as

Q(n) = ∑_{k} \left⟨{n \atop k}\right⟩ P(k).  (5)

Thus the sequence Q(n) is the Stirling transform of the sequence P(n), just like E(n) = ∑ _{k} \left\{{n \atop k}\right\} is the Stirling transform of the constant 1-sequence. In section 2 we derive a formula that allows us to calculate the number q(n) of quasi-orders on n unlabelled points up to n = 12.

A quasi-order ⪯ on a finite set X defines on X a topological structure: the open sets are the order ideals {y ∈ X | x ⪯ y}. Conversely, a topology on a finite set X defines a quasi-order ⪯ via

x ⪯ y if and only if every open set that contains x also contains y.  (6)

Thus the number of types of topologies on n points is given by q(n) as well. The Encyclopedia [11] currently lists the values q(n) for n ≤ 7.

Soft Orders. Let us call a binary relation ⪯ on X that is only required to be transitive and antisymmetric a soft order. (There does not seem to be a particular name for this kind of relation in widespread use. I suggest to use the term “soft order” for a partial order that is soft on the reflexive condition.) Every soft order ⪯ on X determines a partial order on X (as its reflexive closure) and a subset

Y = {x ∈ X | x ⪯̸ x}  (7)

of irreflexive points. Conversely, every partial order on a set X together with a subset Y ⊆ X determines a soft order on X.

Thus a soft order on X is a partial order on X together with a distinguished subset Y ⊆ X of irreflexive elements. If we denote by 2^{X} the power set of X and by 𝒮(X) the set of soft orders on X then

#𝒮(X) = #(2^{X} × 𝒫(X)) = #2^{X} #𝒫(X).  (8)

We denote by S(n) the number of labelled soft orders on n points (sequence \underline{A091566}) and by s(n) the number of unlabelled soft orders on n points (sequence \underline{A079265}). It follows that

S(n) = 2^{n} P(n).  (9)

In section 2 we derive a formula that allows us to calculate s(n) up to n = 12.

Binary relations of this type have been introduced by Taylor and Hilton [13] as structure diagrams of balanced complete experimental designs. There they are also known as mixed models. The values s(n) for n ≤ 9 are listed on Lygeros’ web page [1].

Transitive Relations. Assume X ∩ 2^{X} = ∅. Let us call a set A an augmented partition of X, if for Y = A ∩ X the set A \ Y is a partition of the set X \ Y. Then an augmented partition of X is the union of a subset Y ⊆ X and a partition of its complement X \ Y.

Given a transitive relation ⪯ on X, let Y = {x ∈ X | x ⪯̸ x} be its set of irreflexive points. Then the symmetric core ≡ (defined by x ≡ y if and only if x ⪯ y and y ⪯ x) is an equivalence relation on X \ Y, since x ≡ y implies x ⪯ x (and y ⪯ y) for all x, y ∈ X. Denote by X//≡ the resulting augmented partition (X \ Y)/≡ ∪ Y of X. Furthermore, the relation ⪯ defines a partial order ⊑ on X//≡, where

[x] ⊑ [y] if and only if x ⪯ y.  (10)

Here [x] means the ≡-class of x if x ∈ X \ Y, and the element x if x ∈ Y. Conversely, every choice of a subset Y ⊆ X, a partition L of its complement X \ Y and a partial order ⊑ on the augmented partition L ∪ Y yields via (10) a transitive relation ⪯ on X.

Thus a transitive relation on X is an augmented partition L ∪ Y of X together with a partial order on L ∪ Y. If we denote by 𝒯(X) the set of transitive relations on X then

#𝒯(X) = ∑_{k=0}^{n} ∑_{s=0}^{k} ∑_{Y} ∑_{L} #𝒫(L ∪ Y}),  (11)

where the sum is over all subsets Y ∈ \binom{X}{s} and all partitions L ∈ Λ(X\Y, k−s). We denote the number of labelled transitive binary relations on n points by T(n) (sequence \underline{A006905}), and the number of unlabelled transitive binary relations on n points by t(n) (sequence \underline{A091073}). It follows from the above description, using #𝒫(L ∪ Y) = P(k), #Λ(X \ Y, k − s) = \left\{{n−s \atop k−s}\right\} and #\binom{X}{s} = \binom{n}{s}, that

T(n) = ∑_{k=0}^{n} (∑_{s=0}^{k} \binom{n}{s} \left|{n − s \atop k − s}\right∥ ) P(k),  (12)

(see [6]). In section 2 we derive a formula that allows us to calculate t(n) up to n = 12.

2 Unlabelled kinds of transitive relations.

In this section we derive formulas for the numbers q(n) of unlabelled quasi-orders, s(n) of unlabelled soft orders, and t(n) of unlabelled transitive relations on n points. We begin with two general facts about finite group actions.

Lemma 1. Suppose a finite group G acts on finite sets X and Y. Let f: X ) Y be a G-map, i.e., f(x.g) = f(x).g for all x ∈ X, g ∈ G. Then

x.G ∩ f^{−1}(y) = x.G_{y}  (13)

for all x ∈ X, y = f(x) ∈ Y. Moreover, the number of G-orbits on X is given by

#X/G = ∑_{y.G∈Y/G} #f^{−1}(y)/G_{y},  (14)

where the sum is taken over representatives y of G-orbits y.G on Y.

Proof. Let H = G_{y}, the stabilizer of y in G. Clearly x.H ⊆ x.G. Moreover, H acts on f^{−1}(y) since for z ∈ f^{−1}(y) and h ∈ H we have f(z.h) = f(z).h = y.h = y. It follows that x.H ⊆ f^{−1}(y). Conversely, let z ∈ x.G ∩ f^{−1}(y). Then f(z) = y and z = x.g for some g ∈ G. But y = f(z) = f(x.g) = f(x).g = y.g implies g ∈ G_{y} = H whence z ∈ x.H.

Now let y ∈ Y. Then by (13) the map z.G ) z.G ∩ f^{−1}(y) = z.G_{y} is a bijection between f^{−1}(y.G)/G and f^{−1}(y)/G_{y}. Moreover X is the disjoint union of the sets f^{−1}(y.G), where y runs over a set of representatives of G-orbits y.G on Y (and #∅/G = 0).

Lemma 2. Suppose a finite group G acts on finite sets X and Y. Then the number of G-orbits on the Cartesian product X × Y is given by the formula

#(X × Y)/G = ∑_{r.G∈X/G} #Y/G_{r} = ∑_{[H]∈Sub(G)/G} m_{X}(H) #Y/H,  (15)

where the first sum is over representatives r ∈ X of G-orbits r.G on X, the second sum is over representatives H of conjugacy classes [H] of subgroups of G and where

m_{X}(H) = #{r.G ∈ X/G | G_{r} ∈ [H]}  (16)

is the multiplicity of H as stabilizer of a G-orbit in X.

Proof. Apply Lemma 1 to the projection X × Y ) X.

We need a bit of notation before we can formulate and prove the main theorems. For n ∈ ℕ_{0} we denote by 𝒫(n) the partial orders on {1, …, n}, like we denote the symmetric group on this set by Sym(n). And for H ≤ Sym(n) we denote by μ_{n}(H) the number of unlabelled partial orders P on n points with automorphism group Aut(P) conjugate to H in Sym(n). (More precisely, μ_{n}(H) is defined by the equation |N_{Sym(n)}(H)| μ_{n}(H) = |H|ν_{n}(H), where ν_{n}(H) is the number of labelled partial orders P on the n points {1, …, n} with Aut(P) = H.) Let ℛ_{n} be a transversal of the conjugacy classes of subgroups of Sym(n). Then we have

p(n) = ∑_{H∈ℛ_{n}} μ_{n}(H),  P(n) = ∑_{H∈ℛ_{n}} \frac{n!}{|H|}μ_{n}(H)  (17)

for n ≥ 0.

Theorem 1. The number s(n) of unlabelled soft orders on n points is given by

s(n) = ∑_{H∈ℛ_{n}} μ_{n}(H) #2^{X}/H,  (18)

where X = {1, …, n}.

Proof. We have s(n) = #𝒮(X)/Sym(X) = #(𝒫(X) × 2^{X})/Sym(X), and by Lemma 2,

#(𝒫(X) × 2^{X})/Sym(n) = ∑_{P∈𝒫(X)} #2^{X}/Aut(P)= ∑_{H∈ℛ_{n}} μ_{n}(H) #2^{X}/H,  (19)

as claimed.

Theorem 2. The number q(n) of unlabelled quasi-orders on n points is given by

q(n) = ∑_{k=1}^{n} ∑_{H∈ℛ_{k}} μ_{k}(H) #M(k, n)/H,  (20)

where M(k, n) is the set of maps {f: {1, …, k} ) {1, …, n} | f(1) + ⋯ + f(k) = n}.

Proof. Let X = {1, …, n}. The map f: 𝒬(X) ) Λ(X) which associates to each quasi-order Q ∈ 𝒬(X) the partition X/≡_{Q} ∈ Λ(X) induced by its symmetric core ≡_{Q} on X is a G-map for G = Sym(X). Hence, by Lemma 1,

#𝒬(X)/G = ∑_{L.G∈Λ(X)/G} #f^{−1}(L)/G_{L}.  (21)

Now let L = {L_{1}, …, L_{k}} ∈ Λ(X) be a partition of X into k parts. Then the stabilizer G_{L} contains a normal subgroup N = Sym(L_{1}) × ⋯ × Sym(L_{k}) which lies in the kernel of the G_{L}-action on f^{−1}(L). Let H ≤ Sym(L) be the group of permutations of L induced by G_{L}, i.e., H = {ᾱ : L ) L | α ∈ G_{L}} where L_{i}.ᾱ = L_{i}.α = {j.α : j ∈ L_{i}}. Then G_{L}/N ≅ H and

#f^{−1}(L)/G_{L} = #f^{−1}(L)/H = #𝒫(L)/H,  (22)

since the set 𝒫(L) of partial orders on L is H-equivalent to f^{−1}(L). Now the map L ) {1, …, k} defined by L_{i} ) i translates 𝒫(L) into 𝒫(k) and H into a subgroup H̃ of Sym(k).

A composition of n is a sequence c = (c_{1}, …, c_{k}) of nonnegative integers c_{i} with c_{1} + ⋯ + c_{k} = n. The shape of the composition c = (c_{1}, …, c_{k}) is the partition [c_{1}, …, c_{n}] of n, usually written as a decreasing list of the entries in c.

Here H̃ is the stabilizer of the composition c = (|L_{1}|, …, |L_{k}|) of n in the action of Sym(k) on the set of all compositions of length k. For a partition π of n denote by C(π) the set of all compositions of n with shape π. Note that, if π is the shape of the composition c then C(π) = c.Sym(k). Hence applying Lemma 2 twice yields

#𝒫(L)/H = #𝒫(k)/H̃ = #(𝒫(k) × C(π))/Sym(k) = ∑_{U∈ℛ_{k}} μ_{k}(U) #C(π)/U,  (23)

since μ_{k}(U) is the multiplicity of U as stabilizer of a Sym(k)-orbit on 𝒫(k).

Finally, the map which associates to every partition L = {L_{1}, …, L_{k}} ∈ Λ(X) the partition [|L_{1}|, …, |L_{k}|] of n = |X| given by the sizes of the parts of L is a bijection between Λ(X)/G and Π(n), the set of all partitions of n = |X|. Thus

#𝒬(X)/G = ∑_{π∈Π(n)} ∑_{U∈ℛ_{l(π)}} μ_{l(π)} (U) #C(π)/U,  (24)

where l(π) denotes the length of the partition π, i.e., its number of nonzero parts. The desired formula follows from the fact that M(k, n) is the union of the sets C(π) for partitions π of n of length k (if a composition c = (c_{1}, …, c_{k}) of n is regarded as a map c: {1, …, k} ) {1, …, n} with c(1) + ⋯ + c(k) = n).

Theorem 3. The number t(n) of unlabelled transitive relations on n points is given by

t(n) = ∑_{k=1}^{n} ∑_{H∈ℛ_{k}} μ_{k}(H) #M′(k, n)/H,  (25)

where M′(k, n) is the set of maps {f: {1, …, k} ) {−1} ∪ {1, …, n} | |f(1)| + ⋯ + |f(k)| = n}.

Proof. We argue along the same lines as in the proof of Theorem 2, taking the subsets Y of irreflexive points into account.

Let X = {1, …, n} and let G = Sym(X). Denote by Λ_{s}(X) the set of all augmented partitions A of X with |A ∩ X| = s. The map h: 𝒯(X) ) ⋃_{s≥0} Λ_{s}(X) which associates to each transitive relation R ∈ 𝒯(X) the augmented partition X//≡_{R} ∈ Λ_{s}(X) induced by its symmetric core ≡_{R} on X is a G-map. Moreover, G acts on Λ_{s}(X) for every s ≥ 0. Hence, by Lemma 1,

#𝒯(X)/G = ∑_{s≥0} ∑_{K.G∈Λ_{s} (X)/G} h^{−1}(K)/G_{K}.  (26)

Now let K = L ∪ Y, where Y ⊆ X is a subset of size s, and L = {L_{1}, …, L_{k−s}} ∈ Λ(X \ Y) is a partition of X \ Y with k − s parts. Then the stabilizer G_{K} contains a normal subgroup N = Sym(L_{1}) × ⋯ × Sym(L_{k}) which lies in the kernel of the G_{K}-action on h^{−1}(K). Let H ≤ Sym(K) be the group of permutations of K induced by G_{K}, i.e., H = {ᾱ : K ) K | α ∈ G_{K}} where L_{i}.ᾱ = L_{i}.α for all L_{i} ∈ L and x.ᾱ = x.α for all x ∈ Y. Then G_{K}/N ≅ H and

#h^{−1}(K)/G_{K} = #h^{−1}(K)/H = #𝒫(K)/H,  (27)

since the set 𝒫(K) of partial orders on K is H-equivalent to h^{−1}(K). Now the map K ) {1, …, k} defined by L_{i} ) i and x_{j} ) j, where Y = {x_{k−s+1} , …, x_{k}}, translates 𝒫(K) into 𝒫(k) and H into a subgroup H̃ of Sym(k).

Let us call signed composition of n a sequence c = (c_{1}, …, c_{k}) of nonzero integers c_{i} ∈ ℤ \ {0} such that |c_{1}| + ⋯ + |c_{k}| = n. The positive shape of the signed composition c = (c_{1}, …, c_{k}) is the partition π given by the sorted list of the nonnegative entries c_{i} > 0.

Then H̃ is the stabilizer of the signed composition c = (|L_{1}|, …, |L_{k−s}|, −1, …, −1) of n with s entries −1 in the action of Sym(k) on all signed compositions of length k. For a partition π of n − s let C_{s}(π) be the set of all signed compositions of n with s entries −1 that have positive shape π. Note that, if π is the positive shape of c then C_{s}(π) = c.Sym(k). Hence applying Lemma 2 twice yields

#𝒫(L)/H = #𝒫(k)/H̃ = #(𝒫(k) × C(π))/Sym(k) = ∑_{U∈ℛ_{k}} μ_{k}(U) #C(π)/U,  (28)

since μ_{k}(U) is the multiplicity of U as stabilizer of a Sym(k)-orbit on 𝒫(k).

Finally, the map which associates to every augmented partition K = L ∪ Y ∈ Λ_{s}(X) the partition [|L_{1}|, …, |L_{k−s}|] of n − s given by the sizes of the parts of L = {L_{1}, …, L_{k−s}} is a bijection between Λ_{s}(X)/G and Π(n − s). Thus

#𝒯(X)/G = ∑_{s≥0} ∑_{π∈Π(n−s)} ∑_{U} μ_{l(π)+s} (U) #C_{s}(π)/U.  (29)

where the inner sum is over all U ∈ ℛ_{k} for k = l(π) + s. Summing over k and the fact that M′(k, n) is the union of all sets C_{s}(π) for s ≥ 0 and partitions π of n − s of length k − s yield the desired formula.

3 Results.

An implementation in GAP [10] of the algorithm for the enumeration of all types of partial orders as described in [5] was used to enumerate the partial orders on up to 12 points and to determine their automorphism groups. In difficult cases Brendan McKay’s nauty [7] was used for the computation of the automorphism group. This program is accessible from within GAP through Leonard Soicher’s GRAPE [12] package. The results of the enumeration process were recorded in a table, listing for every conjugacy class of subgroups of Sym(n) how often it occurs as a stabilizer of an (unlabelled) partial order on n points. After determining the numbers of orbits of the groups occurring in the list on the various domains, Theorems 1, 2, and 3 have been used to calculate the sequences s(n), q(n), and t(n). The tables of subgroups of Sym(n) with their multiplicities as stabilizers of partial orders are available from the author on request.

partial orders quasi-orders soft orders

transitive relations

n  p(n)  q(n)  s(n)  t(n)
0  1  1  1  1
1  1  1  2  2
2  2  3  7  8
3  5  9  32  39
4  16  33  192  242
5  63  139  1 490  1 895
6  318  718  15 067  19 051
7  2 045  4 535  198 296  246 895
8  16 999  35 979  3 398 105  4 145 108
9  183 231  363 083  75 734 592  90 325 655
10  2 567 284  4 717 687  2 191 591 226  2 555 630 036
11  46 749 427  79 501 654  82 178 300 654  93 810 648 902
12  1 104 891 746  1 744 252 509 3 984 499 220 967 4 461 086 120 602

Table 2: Numbers of unlabelled kinds of transitive relations.

Table 2 shows the numbers q(n), s(n), and t(n) for n = 0, 1, …, 12. The additional column with the numbers p(n) of partial orders on n points allows comparisons.

In practice, out of the many conjugacy classes of subgroups of Sym(n) (sequence \underline{A000638}) only very few do actually occur as automorphism groups of partial orders (sequence \underline{A091070}). For comparison, Table 3 also lists the number of conjugacy classes of Sym(n) that occur as normalizers of a subgroup (sequence \underline{A091071}). (See [9] for a detailed list of subgroups of Sym(12).)

n  1 2 3 4 5 6 7 8 9 10 11  12
classes of subgroups 1 2 4 11 19 56 96 296 554 1593 3094 10723
automorphism groups 1 2 3 6 8 16 21 41 57 103 140 276
normalizers  1 1 2 4 5 12 19 42 72 127 196 500

Table 3: Numbers of Subgroups.

4 Concluding Remarks and Questions.

The enumeration of all the partial orders on n points and their automorphism groups takes a considerable amount of time. Due to huge numbers of partial orders and the quick exponential growth of these numbers, it will be difficult to calculate many more terms of the sequences s(n), q(n), and t(n) using this method. On the other hand, the number of automorphism groups that occur is tiny by comparison. It might be interesting to approach the problem of counting partial orders from that side: Is it possible to characterize the subgroups of Sym(n) that occur as automorphism groups of partial orders? Is it possible to enumerate partial orders with a given automorphism group more efficiently?

Acknowledgments. I am grateful to Jerome Sheahan for explaining the statistical connection and to Britta Wienand for useful comments.

Note added in proof. I have learned from Brendan McKay that in unpublished work in 2001, using a modification of their program [2], he and Brinkmann have obtained the numbers q(n) for n ≤ 16 and the numbers s(n), t(n) for n ≤ 15; their numbers are consistent with the numbers in Table 2.

References

[1] R. Bayon, N. Lygeros, and J.-S. Sereni, Enumeration of fixed effects and mixed models,

    http://igd.univ-lyon1.fr/home/lygeros/models.html.

[2] Gunnar Brinkmann and Brendan D. McKay, Posets on up to 16 points, Order 19 (2002), no. 2, 147–179. MR 2003e:05002

[3] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1989, A foundation for computer science. MR 91f:00001

[4] Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York, 1973. MR 50 #9682

[5] Jobst Heitzig and Jürgen Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000), no. 4, 333–341 (2001). MR 2002a:06001 [6] Jiří Klaška, Transitivity and partial order, Math. Bohem. 122 (1997), no. 1, 75–82. MR

98c:05006

[7] Brendan D. McKay, nauty user’s guide (version 1.5), technical report tr-cs-90-02, Australian National University, Computer Science Department, ANU, 1990, Home page:

    http://cs.anu.edu.au/people/bdm/nauty.

[8] Walter Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann. 174 (1967), 53–78. MR 36 #1342

[9] Götz Pfeiffer, The subgroups of S_{12}, http://schmidt.nuigalway.ie/subgroups, 2003, 597 pages.

[10] Martin Schönert et al., GAP – Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, fifth

    ed., 1995, Home page: http://www.gap-system.org.

[11] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically

    at http://www.research.att.com/~njas/sequences/, 2003.

[12] Leonard H. Soicher, GRAPE: a system for computing with graphs and groups, Proceedings of the 1991 DIMACS Workshop on Groups and Computation (L. Finkelstein and B. Kantor, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11, American Mathematical Society, 1993, Home page:

    http://www.gap-system.org/Share/grape.html., pp. 287–291.

[13] W. H. Taylor and H. G Hilton, A structure diagram symbolization for analysis of variance, The American Statistician 35 (1981), 85–93.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 06A07. Keywords: binary relation, partial order, quasi-order, soft order, transitive relation, symmetric group, group action, finite topology, automorphism group, enumeration.

(Concerned with sequences \underline{A000027}, \underline{A000041}, \underline{A000070}, \underline{A000079}, \underline{A000088}, \underline{A000110}, \underline{A000112}, \underline{A000273}, \underline{A000595}, \underline{A000638}, \underline{A000666}, \underline{A000798}, \underline{A001035}, \underline{A001174}, \underline{A001930}, \underline{A002416}, \underline{A006125}, \underline{A006905}, \underline{A047656}, \underline{A053763}, \underline{A079265}, \underline{A083667}, \underline{A083670}, \underline{A091070}, \underline{A091071} \underline{A091073}, and \underline{A091566}.)

Received January 22 2004; revised version received July 9 2004. Published in Journal of Integer Sequences, August 2 2004.

Return to Journal of Integer Sequences home page.