Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.5

Sequences Realized by Oligomorphic Permutation Groups

Peter J. Cameron
School of Mathematical Sciences
Queen Mary and Westfield College
London E1 4NS
U.K.
Email address: p.j.cameron@qmw.ac.uk

Abstract: The purpose of this paper is to identify, as far as possible, those sequences in the Encyclopedia of Integer Sequences which count orbits of an infinite permutation group acting on n-sets or n-tuples of elements of the permutation domain. The paper also provides an introduction to the properties of such sequences and their relations with combinatorial enumeration problems.

Contents

  1. Introduction
  2. Oligomorphic permutation groups
  3. Cycle index
  4. New groups from old
  5. Groups and enumeration
  6. The inverse Euler transform
  7. Examples
  8. Acknowledgments
  9. References
  10. Tables (in a separate file)

1. Introduction

A permutation group on an infinite set is oligomorphic if the number of orbits on ordered n-tuples is finite for all positive integers n. Here a permutation g of a set X acts on the set Xn of all n-tuples of elements of X by the rule
(x1, ..., xn)g = (x1g, ..., xng).
Many important sequences of integers can be realised as sequences counting orbits of an oligomorphic group on n-tuples or n-sets. The purpose of this paper is to document all examples known to the author of such sequences occurring in the Encyclopedia of Integer Sequences. Since this list of examples is unlikely ever to be complete, it is planned to update it from time to time. Please email suggested additions to the author at the address above.

The paper also includes some general theory of oligomorphic permutation groups and their relation to combinatorial enumeration. Further details can be found in references [3] and [5].

Many familiar sequences will be found here (Fibonacci numbers, partitions, graphs, trees, binomial coefficients, powers, ...). It is the author's contention that the occurrence of a sequence as the U- or L-sequence of an oligomorphic group gives it extra interest. Also, if the U-sequence of a group is interesting, then so is the L-sequence, and vice versa - so the blanks in the tables are worth investigating!

The tables also provide data on which to base conjectures about the behavious of U- and L-sequences of oligomorphic permutation groups.

Note that the examples and constructions reported here are closely related to species (see [1]); however, species are more general, and some of the known restrictions for U-sequences of oligomorphic groups (see Section 2.4) do not apply to counting sequences for species. Cross-references will be given where appropriate.

2. Oligomorphic permutation groups

The concept of an oligomorphic permutation group was defined in the Introduction. From the definition, if G is an oligomorphic permutation group on a set X, then each of the following numbers is finite for each positive integer n: By convention, we set f0(G) = F0(G) = F0*(G) = 1. We omit (G) if the group in question is clear.

In what follows, all permutation groups are taken to act on countable sets. This loses no generality: an argument based on the Downward Löwenheim-Skolem Theorem of first-order logic shows that, given any oligomorphic permutation group G, there is an oligomorphic group acting on a countable set which realises the same numbers fn, Fn, and Fn* (see [3]).

2.1. Connection with logic

The third of these sequences arises naturally in connection with the notion of countable categoricity in first-order logic. Let T be a consistent complete theory in a first-order language.

We say that T is countably categorical if it has a unique countable model up to isomorphism.

An n-type over T is a set of formulae in n free variables x1, ..., xn which is maximal with respect to being consistent with T. The n-type S is realized in a model M of T if there exist elements a1, ..., an in M such that the formulae in S are true when the as are substituted for the xs. (Note that the set of all formulae holding on a given tuple of elements in a model of T is a type.)

Now the theorem of Engeler, Ryll-Nardzewski, and Svenonius asserts the following.

Theorem. Let T be a consistent complete theory in a first-order language. Then T is countably categorical if and only if it has only finitely many n-types for each positive integer n. If these conditions hold, and M is the countable model of T, then every type S is realised in M, and the set of tuples realising S is an orbit of the automorphism group of M.

Conversely, let M be a countable structure over a first-order language, and suppose that the automorphism group of M is oligomorphic (as a permutation group on M). Then the first-order theory of M is countably categorical.

In view of this theorem, we apply the term "countably categorical" also to a countable structure whose automorphism group is oligomorphic.

We see that, if M is the countable model of a countably categorical theory T, then the number of n-types of T is equal to Fn*(G), where G is the automorphism group of M.

2.2. U- and L-sequences

Despite the preceding section, this paper will concentrate on the sequences (fn(G)) and (Fn(G)), for reasons which will appear. A sequence of positive integers will be called an U-sequence or an L-sequence if it is realised as the orbit-counting sequence (fn(G)) or (Fn(G)) respectively, for some oligomorphic group G. (The letters U and L stand for "unlabeled" and "labeled". The reason for this will be explained below.) The primary aim of this project is to annotate the Encyclopedia of Integer Sequences with information about which of its entries are U-sequences or L-sequences. The first reason for neglecting (Fn*) is that its values can be determined from those of (Fn by the following formula, in which S(n,k) is the Stirling number of the second kind (the number of partitions of a n-set into k parts):
Fn* = Sumk S(n,k)Fk.

In the terminology of Bernstein and Sloane [2], the starred sequence is the Stirling transform of the unstarred: F*=STIRLING(F). (See also the section on transformations in the On-Line Encyclopedia.)

We will see later that the Stirling transform of an L-sequence is also an L-sequence. So the class of realisable sequences would not be enlarged by including the starred sequences.

A related observation we will also see later is that, for many groups G, there exists a group G* whose U-sequence is the L-sequence of G.

2.3. Two important examples

We conclude this section with two important examples of oligomorphic groups:

2.4. Some restrictions

A number of restrictions on U- and L-sequences are known. Most concern the rate of growth of the sequence. We are very far from having a necessary and sufficient condition!

U-sequences have been studied more than L-sequences. The following results are for the most part due to Dugald Macpherson in [8] and other papers, and are discussed further in the references already cited.

Macpherson also has some results about faster growth rate, related to model-theoretic properties such as stability and the strict order property.

L-sequences are also non-decreasing (though this is much easier to see); in fact, consecutive terms of an L-sequence are equal only if they are both 1. Francesca Merola [10] has recently strengthened Macpherson's exponential growth result by showing that the L-sequence of a primitive but not highly homogeneous group grows at least as fast as cnn!, for some constant c>1.

3. Cycle index

3.1. Generating functions

We represent a U-sequence (fn) by its ordinary generating function (for short, o.g.f.)
f(x) = Sum fnxn,
and an L-sequence (Fn) by its exponential generating function (for short, e.g.f.)
F(x) = Sum Fnxn/n!.
If necessary, we specify the group by writing these power series as fG(x) and FG(x).

3.2. Cycle index

Both these power series are specialisations of a power series in infinitely many variables, the modified cycle index, which we now define in three stages.

If g is a permutation on n points, the cycle index of g is defined to be the monomial

z(g) = s1c1 ... sncn
in indeterminates s1, ..., sn, where ci is the number of i-cycles in the cycle decomposition of g.

Now let G be a permutation group on a set of size n. The cycle index Z(G) of G is obtained simply by summing the cycle indices of its elements and dividing by the order of the group G.

Finally, let G be an oligomorphic permutation group acting on the (usually infinite) set X. The modified cycle index Z(G) is obtained as follows: choose a set of representatives of the orbits of G on finite subsets of X. For each such finite set, consider the group of permutations induced on it by its setwise stabilizer in G, and calculate the cycle index of this finite permutation group. Then add all these cycle indices. (This infinite sum is permissible since any given monomial only arises from sets of fixed finite cardinality n, and there are only finitely many orbit representatives on n-sets to consider since G is oligomorphic.) By convention, we take the term corresponding to the empty set to be 1. Thus Z(G) is a formal power series in the indeterminates s1, s2, ... .

What is important for our purpose are the following facts:

4. New groups from old

4.1. Direct product

Let G and H be permutation groups on sets X and Y respectively. The direct product G Times H acts on the disjoint union X union Y as follows: the ordered pair (g,h) acts on X as g and on Y as h. We have the following:
Z(G Times H)=Z(G)Z(H).
This operation corresponds to the operation of species product of species (see [1]).

Thus the exponential generating function of the L-sequence for G Times H is obtained by multiplying those for G and H; and similarly for the ordinary generating function of the U-sequence. The operations on sequences are CONV for the U-sequence and EXPCONV for the L-sequence.

In particular, the operation of forming the direct product with S replaces the U-sequence by its PSUM transform, whose terms are the partial sums of the original sequence; and replaces the L-sequence by its BINOMIAL transform.

There is another action of the direct product. The product action is on X Times Y, where the pair (g,h) maps (x,y) to (xg,yh). Counting orbits in this action is much more difficult, and is not even solved for S Times S. (The nth term in the U-sequence is A049311, the number of zero-one matrices with n ones and no zero rows or columns, up to row and column permutations; equivalently, bipartite graphs with n edges and no isolated vertices with a prescribed bipartite block.)

4.2. Wreath product

Again let G and H be permutation groups on sets X and Y respectively. The wreath product G Wr H is defined as follows, as a permutation group on X Times Y: it contains a base group B, the set of functions from Y to G, where the function f maps (x,y) to (xf(y),y); and a top group T, a group isomorphic to H, where the element h maps (x,y) to (x,yh). The wreath product of G and H is the (semi-direct) product of B and T.

The operation of wreath product corresponds to species substitution (or partitional composition) of species: see [1].

The L-sequence of G Wr H can be calculated from those of G and H by substitution:

FG Wr H(x) = FH(FG(x)-1).

However, there is no formula for the L-sequence of G Wr H in terms of those of G and H. There is such a formula for the modified cycle index as follows:

Z(G Wr H; s1, s2, ...) = Z(H; Z1-1, Z2-1, ...),
where Zi is obtained from Z(G) by substituting sij for sj, for all j.

From this it follows that the e.g.f. for the U-sequence for G Wr H can be obtained from Z(H) by substituting fG(xi)-1 for si for all i (where fG is the o.g.f. for the U-sequence of G).

In particular, we see that for each oligomorphic permutation group H, there is an operator (also denoted by H) on sequences, with the property that it maps the U-sequence of G to that of G Wr H for any oligomorphic group G. The set of all U-sequences of oligomorphic groups is closed under all these operators. The operators S, A, and C are the operators EULER, INVERT, and CIK. respectively. See [4] for further details.

Various formal identities hold for these products: for example,

Now we can explain why the sequence (Fn*(G)) is an L-sequence - indeed, it is the L-sequence of the group S Wr G. Let S and G act on sets X and Y respectively, so that S Wr G acts on X Times Y. Then there is a function from n-tuples of distinct elements of X Times Y to arbitrary n-tuples of Y, mapping each ordered pair to its second element. Clearly this mapping preserves orbits. Moreover, since X is infinite, any n-tuple of elements of Y lies in the image of the mapping. So

Fn*(G)= Fn(S Wr G).

Indeed, this example shows that the L-sequence of G Wr S is the STIRLING transform of that of G. The substitution rule gives the well-known formula

FS Wr G(x) = FG(ex-1).

The U- and L-sequences for S Wr S are A000041 (partitions) and A000110 (Bell numbers) respectively.

If Sk denotes the finite symmetric group of degree k, then Sk Wr S and S Wr Sk have the same U-sequences, since the number of partitions with parts of size at most k is equal to the number of partitions with at most k parts. However, their L-sequences differ. For k = 2, they are A000085 (self-inverse permutations) and A000079 (powers of two, shifted right one place) respectively. Another interesting example is S2 Wr A, whose U-sequence is A000045 (Fibonacci numbers).

Two further special cases are notable. Let E denote the trivial group acting on a set with two elements. Then

There is another action of the wreath product, the so-called product action on the set of functions from Y to X. This is not oligomorphic unless the top group is finite.

4.3. Stabilizer

Another operation on permutation groups consists of taking the stabilizer of a point. Let G be transitive on X, and let H denote the subgroup consisting of elements of G fixing the point x of X, acting on the points different from x. Then the modified cycle index of H is obtained by differentiating that for G with respect to s1. If G is not transitive, then this derivative is equal to the sum of the modified cycle indices of a set of orbit representatives.

The operation of taking the derivative corresponds to the species derivative for species (see [1]).

It follows (or is easily proved directly) that, if G is transitive, then the L-sequence for a point stabilizer is obtained from that of G by shifting the sequence one place left (deleting the initial 1). This is the operator LEFT.

The U-sequence of the stabilizer is not determined by that of G.

To summarise: The set of e.g.f.s of L-sequences is closed under multiplication, substitution, and (if the first term is 1) differentiation (or left shift). The set of o.g.f.s of U-sequences is closed under multiplication and under the sequence operator associated with any oligomorphic group (in particular, the EULER and INVERT operators).

4.4. Other constructions

This by no means exhausts the possible constructions, though in other cases it is not known how to calculate the L- and U-sequences.

If G is oligomorphic on X, then the permutation group induced by G on any of its orbits on n-sets, n-tuples, etc., for any n, is oligomorphic. For a specific example, let G = S, the infinite symmetric group, in its action on 2-sets. Any set of n 2-sets can be regarded as the edges of a graph, whose vertex set is the union of the n pairs (so that the graph has no isolated vertices). Two n-sets lie in the same orbit if and only if the graphs are isomorphic. So sequence A000664, counting graphs with n edges and no isolated vertices, is a U-sequence.

5. Groups and enumeration

We now come to the most flexible method of constructing oligomorphic groups, namely Fraïssé's Theorem.

5.1. Homogeneous structures

The groups will be automorphism groups of certain structures which we may take to be relational structures, that is, collections of relations of various arities on the ground set X. Structures such as graphs and partial orders can be described by a single binary relation, but in general we do not restrict the arities of the relations, and also permit an infinite number of relations. An induced substructure of a relational structure on a subset Y of its domain is obtained by restricting all of the relations to Y.

A structure M on the domain X is homogeneous if it has the following property: any isomorphism between finite induced substructures of M can be extended to an automorphism of M.

The age of a relational structure M is the class of all finite relational structures which are embeddable in M as induced substructures (that is, which are isomorphic to induced substructures of M).

Now the key observation is the following:

Let M be a homogeneous relational structure, and G its automorphism group. Then the U-sequence and the L-sequence of G enumerate the unlabeled and labeled structures respectively in the age of M.
That is, fn(G) is the number of unlabeled n-element structures embeddable in M: we count structures up to isomorphism. And Fn(G) is the number of labeled n-element structures embeddable in M: that is, structures on the domain {1, 2, ..., n} which are embeddable in M.

This application explains the terms "U-sequence" and "L-sequence".

5.2. Fraïssé's Theorem

Now it is important to know: which enumeration problems arise in this way? That is, how do we recognise the ages of homogeneous relational structures? This question is answered by Fraïssé's Theorem:
Theorem. A class K of finite relational structures is the age of a countable homogeneous relational structure if and only if it satisfies the following four conditions: If these conditions hold, then the countable homogeneous structure whose age is K is unique up to isomorphism.
The class K has the Amalgamation Property if the following holds:
Whenever A, B1, B2 are structures in K and fi is an embedding of A into Bi for i = 1, 2, then there exists a structure C in K and embeddings gi of Bi in C for i = 1, 2 such that g1f1 = g2f2.
Effectively this means that two structures with a common substructure can be glued together along the common substructure.

The first three conditions are automatic in most cases. Indeed, in the situation of oligomorphic groups, we will have the stronger condition that the number of n-element structures in M (up to isomorphism) is finite for each n.

A class of finite structures satisfying the hypotheses of Fraïssé's Theorem is called a Fraïssé class. Thus the sequences enumerating unlabeled and labeled structures in any Fraïssé class are U- and L-sequences respectively. Conversely, it can be shown than any U- or L-sequence counts structures in some Fraïssé class.

The group S arises from the Fraïssé class of finite sets with no structure, and A from the class of finite linearly ordered sets.

For a slightly less simple example, the class of finite graphs is a Fraïssé class; the corresponding homogeneous structure is the so-called countable random graph (see [6]. The corresponding U- and L-sequences are A000088 and A006125 respectively. Many more examples exist.

If the transitive group G is associated with the Fraïssé class K, then the point stabilizer in G is associated with the class of "rooted K-structures" (that is, K-structures with a distinguished point, counted by the number of non-distinguished points).

5.3. Cycle index again

If G is the automorphism group of a homogeneous structure associated with a Fraïssé class K, then the modified cycle index of G is related to K as follows: This approach to enumeration is related to that of Joyal [7]; see also [1].

5.4. Strong Amalgamation

In the Amalgamation Property, we allow the possibility that when we glue the two structures together, the overlap is larger than intended. We say that the class K has the Strong Amalgamation Property if it is possible to make the amalgamation so that no extra points are glued together. Formally, in terms of our statement of the Amalgamation Property, we require the following:
If g1(b1) = g2(b2), for some elements b1, b2 of B1, B2 respectively, then there exists an element a in A such that f1(a) = b1 and f2(a) = b2.

Now suppose that we have two Fraïssé classes K and L, both of which have the Strong Amalgamation Property. Let K and L denote the class of finite sets carrying both a K-structure and an L-structure (independently). Then K and L also has the Strong Amalgamation Property.

Note that the number of labeled n-element structures in K and L is the product of the numbers in K and L. So, if the Strong Amalgamation Property holds, then L-sequences can be multiplied term-by-term. The position for U-sequences is not so straightforward because of the possible existence of automorphisms.

From this construction, we get the following result.

Let G be an oligomorphic group associated with a Fraïssé class K having the Strong Amalgamation Property. Then there is an oligomorphic group G* whose U-sequence is the L-sequence of G.
We take G* to be the group associated with the Fraïssé class K and L, where L is the class of linear orders.

This shows that many L-sequences are also U-sequences.

There is a group-theoretic test for the Strong Amalgamation Property. If G is associated with the Fraïssé class K, then K has the Strong Amalgamation Property if and only if the stabilizer in G of any finite number of points has no additional fixed points.

6. The inverse Euler transform

The EULER transform, as well as being associated with the group S, does several other jobs. One of these concerns graded algebras. If A is a graded algebra which is a polynomial algebra in a family of homogeneous generators (with only finitely many of each degree), then the sequence giving the dimensions of the homogeneous components of A is the EULER transform of the sequence counting generators by degree.

With each oligomorphic permutation group G, we can associate a graded algebra AG, with the property that the dimension of its nth homogeneous component is fn(G). (Details are given in [3] or [5].) In some cases, AG can be shown to be a polynomial algebra. Typically this occurs when G is associated with a Fraïssé class (such as graphs) with a "good notion of connectedness", and polynomial generators correspond to connected structures.

Here is a summary of some positive results on the polynomial question.

The process can be reversed. If the inverse Euler transform EULERi(fn(G))=(an) is a "familiar" sequence (one listed in the Encyclopedia), we might suspect that AG is a polynomial algebra, and try to prove this by associating generators with objects counted by (an).

A linearly ordered set of size n with its elements coloured red and blue can be identified with a word of length n over a 2-letter alphabet. The fact that any such word can be uniquely written as a product of Lyndon words (those which are lexicographically smaller than all their cyclic shifts) in decreasing lexicographical order shows that the EULERi transform of the sequence of powers of 2 is the sequence counting Lyndon words. This sequence is A001037, which also counts necklaces with two colours of beads having no rotational symmetries, or irreducible polynomials over GF(2). It is known (see [5]) that, for at least one group G whose U-sequence is the sequence of powers of 2, the algebra AG is polynomial.

In a similar way, sequence A000045 (Fibonacci numbers) counts words in a and b with no two repeated as. If we shift the sequence right one place, we can assume that the words do not end with an a. The Lyndon factors of such a word themselves have no two repeated as, and thus correspond to necklaces with no two consecutive red beads (excluding the necklace with just one red bead), which are counted by sequence A006206.

Here are three related problems of this type, where AG is not known to be a polynomial algebra.

7. List of examples

The list of examples will be kept in a separate file and will be updated regularly.

8. Acknowledgments

I am very grateful to Christian G. Bower for many helpful comments (and a number of additional examples).

9. References

  1. F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Encyclopedia of Mathematics and Its Applications, 67, Cambridge University Press, Cambridge, 1998.
  2. M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra and Applications 226/228 (1995), 57-72 [postscript, pdf].
  3. P. J. Cameron, Oligomorphic Permutation Groups, London Mathematical Society Lecture Notes 152, Cambridge University Press, Cambridge, 1990.
  4. P. J. Cameron, Sequence operators from groups, Linear Algebra and Applications 226/228 (1995), 109-113.
  5. P. J. Cameron, Stories about groups and sequences, Designs, Codes, Cryptography 8 (1996), 109-134.
  6. P. J. Cameron, The random graph, pp. 331-351 in The Mathematics of Paul Erdös (ed. R. L. Graham and J. Nesetril), Springer, Berlin, 1997.
  7. A. Joyal, Une theorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.
  8. H. D. Macpherson, The action of an infinite permutation group on the unordered subsets of a set, Proc. London Math. Soc. (3) 46 (1983), 471-486.
  9. C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes, and Euler graphs are equal in number, SIAM J. Appl. Math. 28 (1975), 876-880.
  10. F. Merola, Thesis, University of Palermo, 1999.


Received Sep. 2, 1999; revised version received Jan. 4, 2000. Published in Journal of Integer Sequences Jan. 25, 2000.


Return to Journal of Integer Sequences home page