|
|
Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.5 |
|
|
Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.5 |
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.
(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.
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]).
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.In view of this theorem, we apply the term "countably categorical" also to a countable structure whose automorphism group is oligomorphic.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.
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.
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.
fn*(S) = Sumk S(n,k) = B(n),the Bell number (the total number of partitions of an n-set), sequence A000110. As noted, this will show that the Bell numbers form an L-sequence.
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.
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.
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).
If g is a permutation on n points, the cycle index of g is defined to be the monomial
z(g) = s1c1 ... sncnin 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:
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.)
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.
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).
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.
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".
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:The class K has the Amalgamation Property if the following holds:If these conditions hold, then the countable homogeneous structure whose age is K is unique up to isomorphism.
- K is closed under isomorphism;
- K is closed under taking induced substructures;
- K has only countably many members up to isomorphism;
- K has the Amalgamation Property (see below).
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).
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.
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.
Received Sep. 2, 1999; revised version received Jan. 4, 2000. Published in Journal of Integer Sequences Jan. 25, 2000.