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

Sequences Realized by Oligomorphic Permutation Groups: Tables

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

These tables, which will be updated regularly, include all examples currently known to the author of sequences which occur in the Encyclopedia of Integer Sequences and are U-sequences or L-sequences of oligomorphic permutation groups (in the sense of the accompanying paper Sequences realized by oligomorphic permutation groups).

If an entry is blank, the sequence is not (yet) in the table. As noted in the main paper, all blank entries in the U and L columns should be regarded as potentially interesting sequences.

The column labeled "Inverse Euler" is obtained by applying the transformation EULERi to the U-sequence. Its significance is explained in Section 6 of the main paper. (See also the section on transformations in the On-Line Encyclopedia.) An entry P denotes that the algebra AG for the group in question is known to be polynomial (and the sequence counts its generators).

If the entry under "L-sequence" is annotated with U, then this is the U-sequence of a different group, because the associated Fraïssé class has the Strong Amalgamation Property: see Section 5.4 of the main paper. Such groups are usually not listed separately; the nth term of the L-sequence is obtained by multiplying the nth term of the U-sequence by n! (that is, applying LISTTOLISTMULT).

The letters R and L mean "shifted right" and "shifted left" respectively.

The Atlas of Graphs [5] has been very useful in preparing these tables.

This version is dated 10 September 1999.

Contents

  1. Basic examples
  2. Direct and wreath products
  3. Fraïssé classes
  4. Miscellaneous examples
  5. Some oddities
  6. References (see also the references for the main paper)
  7. The main paper (in a separate file)

1. Basic examples

Here S denotes the infinite symmetric group, A the group of order-preserving permutations of the rational numbers, B the group of order-preserving and reversing permutations of the rationals, C the group of permutations preserving the cyclic order of the complex roots of unity, and D the group preserving or reversing this cyclic order. Note that A is the point stabilizer in C, and B the stabilizer in D, while the point stabilizer in S is isomorphic to S. These are the five "highly homogeneous" groups of Cameron [2].

In the notation used in [3], A, B, C, D are dC, dC*, C, C* respectively: the "d" denotes point stabilizer and the asterisk denotes an extension by a group of order 2 reversing the order. In the language of species [1], the cases A, B, C, D, S are denoted respectively by L (linear orders), Cha (chains), C (cycles), P (polygons) and E (sets).

Highly homogeneous groups
Group U-sequence L-sequence Inverse Euler
S A000012 A000012 U A000007 RP
A A000012 A000142U A000007RP
B A000012 A001710U A000007RP
C A000012 A000142RU A000007RP
D A000012 A001710RU A000007RP

2. Direct and wreath products

Direct products
Group U-sequence L-sequence Inverse Euler
S Times S A000027L A000079U (1)P
S Times A A000027L A000522U (1)P
A Times A A000027L A000142LU (1)P
S3 A000217 A000244U(2) (1)P
S4 A000292 A000302U (1)P
S5 A000332 A000351U (1)P
S6 A000389 A000400U (1)P
S7 A000579 A000420U (1)P
S8 A000580 A001018U (1)P
S9 A000581 A001019U (1)P
S10 A000582 A011557U (1)P
S11 A001287 A001020U (1)P
S12 A001288 A001021U (1)P
S13 A001022U (1)P
S14 A001023U (1)P
S15 A001024U (1)P
S16 A001025U (1)P
S17 A001026U (1)P
S18 A001027U (1)P
S19 A001029U (1)P

Notes:

  1. The inverse Euler transform of the U-sequence for Sn is the sequence whose only non-zero entry is n in the first position.
  2. The L-sequence for Sn is simply the powers of n.

Wreath products
Group U-sequence L-sequence Inverse Euler
S Wr S A000041 A000110U A000012P
A Wr S A000041 A000262U A000012P
C Wr S A000041 A000142U A000012P
S Wr A A000079R A000670U
S Wr S2 A008619 A000079U (1)P
S2 Wr S A008619 A000085 (1)P
S Wr S3 A001399 A007051U (1)P
S3 Wr S A001399 A001680 (1)P
S Wr S4 A001400 A007581U (1)P
S4 Wr S A001400 A001681 (1)P
S Wr S Wr S A001970 A000258U A000041P
A Wr A A000079R A002866U A001037
A Wr A Wr A(2) A000244R U
S2 Wr A A000045 A006206
S3 Wr A A000073
S4 Wr A A000078
S5 Wr A A001591
S6 Wr A A001592
E Wr S(3) A002620LL A000898 (4)P
E Wr A(3) A000129 (5)
S<4>(6) A007713 A000307U A001970P
S<5> A007714 A000357U A007713P
S<6> A000405U A007714P
S<7> A001669U P
C<2> A008965 A003713U
C<3> A000268U
C<4> A000310U
C<5> A000359U
C<6> A000406U
C<7> A001765U

Notes:

  1. The inverse Euler transform of the U-sequence for S Wr Sk or Sk Wr S has the first k entries 1 and the rest 0.
  2. The U-sequence of the kth iterated wreath product of A has nth term kn-1. (This is the L-sequence for Sk in the preceding table, shifted right.) The L-sequence is obtained by multiplying by n!.
  3. E denotes the trivial group acting on a set of two points. So E Wr G is obtained from G by taking two copies of each orbit.
  4. This is the finite sequence 2, 1.
  5. This is obtained by multiplying the terms of the U-sequence by factorials.
  6. Here G<n> means the iterated wreath product of G with itself with n factors.

Mixed groups
Group U-sequence L-sequence Inverse Euler
S Times (S Wr S2) A002620 A007051 (1)P
S Times (S Wr S3) A000601 (1)P
S Times (S Wr S4) A002621 (1)P
S Times (S Wr S5) A002622 (1)P
S Times (S Wr S) A000070 (1)P
S Times (S2 Wr A) A000071
S Wr (S Times S2) A000097 A008619P
S Times S Times (S Wr S2) A002623 (1)P
(S2 Wr A)2 A001629
(S2 Wr A)3 A001628
(S2 Wr A)4 A001872
(S2 Wr A)5 A001873
(S2 Wr A)6 A001874
(S2 Wr A)7 A001875

Notes:

  1. For S Times (S Wr Sk), this entry is 2 followed by k-1 ones. For S Times (S Wr S), it is the all-1 sequence with the first term changed to 2. For S Times S Times (S Wr S2) it is 3, 1, 1.

3. Fraïssé classes

In these cases the group G is the automorphism group of the unique countable homogeneous structure whose age is the named Fraïssé class.

The notation R(things) means that the group is the point stabilizer in the group corresponding to "things" (so that the Fraïssé class is "rooted things"). The L-sequence shifts one place left under this operation.

The treelike objects in this table are discussed in [3]. The final column of the table gives the names used in that paper.

Automorphism groups of homogeneous structures
Fraïssé class U-sequence L-sequence Inverse Euler In [3]
Graphs A000088 A006125U A001349P
Graphs up to complement A007869 A036442U
K3-free graphs A006785 U A024607P
Graphs with bipartite block A049312 A047863 P
Graphs with loops A000666 A006125LU P
Digraphs A000273 (1)U A003085P
Digraphs with loops A000595 A002416U P
Oriented graphs A001174 A047656U P
Topologies A001930 A006057U A001928P
Posets A000112 A001035U A000608P
Tournaments A000568 A006125U
Local orders A000016 A000165RU C2
Two-graphs A002854 A006125RU A003049
Oriented two-graphs A049313 A006125RU
Total orders with subset A000079 A000165U A001037P dC2
Total orders with 2-partition A000079R A002866U A001037(2)P dC2*
C-structures with subset A000031 U
D-structures with subset A000029 U
2 total orders (distinguished) A000142 A001044U
2 total orders (not distinguished) A007868 U
2 betweennesses (not distinguished) A000903 U
Boron trees (leaves) A000672RR A001147RRU T3
HI trees (leaves)(3) A007827 A000311RU T
R(Boron trees (leaves)) A001190 A001147RU dT3
R(HI trees (leaves))(3) A000669 A000311U dT
Trees (edges) A000055L A007830RRU
Covington structures[4] A007866 A001813RU dT3(2)
Binary trees A000108 A001813RU dPT3
Binary trees up to reflection A007595R A000407RRU dP*T3
Plane boron trees A001683 A001813U PT3
Plane boron trees up to reflection A000207R A000407RU P*T3
3-hypergraphs A000665R U A003190P
Ternary relations A000662 U P
Quaternary relations A001377 U P

Notes:

  1. Labeled digraphs: 1, 4, 64, 4096, ... (general term 2n(n-1))
  2. First term changed from 2 to 1.
  3. HI = "homeomorphically irreducible", i.e. no divalent vertices.
Products of the above
Group U-sequence L-sequence Inverse Euler
(Total orders with subset) Times S A000225 U P
(Total orders with subset) Times S Times S A000295 U P
(Total orders with subset) Times (Total orders with subset) A001787 U P
(Total orders with subset) Times (Total orders with 2-partition) A001792 U P
(Total orders with subset) Times (Total orders with 2-partition) Times S A001787 U P
(2 total orders (distinguished)) Times S A003422L U
R(HI trees (leaves)) Wr S A000084 U A000669P
(Binary trees) Wr A A000108R U
(Binary trees) Wr A Wr A A001700 U

4. Miscellaneous examples

Miscellaneous groups
Group U-sequence L-sequence Inverse Euler
S on 2-sets A000664 A014500 A002905P
S2 (product action) A049311 (1)P

Notes:

  1. Connected graphs with a bipartite block, by edges: 1, 2, 3, 7, 12, 32, 67, ...

5. Some oddities

The U-sequence of the group S2 Wr A is the sequence of Fibonacci numbers (A000045). The inverse Euler transform of this is A006206.

The groups C Wr S and A have the same L-sequence, namely A000142 (factorials). This reflects the fact that a permutation can be expressed uniquely as an unordered union of cycles. Of course, C Wr S has the same U-sequence as S Wr S, namely A000041 (partitions).

6. 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. P. J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 48 (1976), 127-139.
  3. P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford (2) 38 (1987), 155-183.
  4. J. Covington, A universal structure for N-free graphs, Proc. London Math. Soc. (3) 58 (1989), 1-16.
  5. R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press, Oxford, 1999.

Received September 2 1999; revised version received January 4 2000. Published in Journal of Integer Sequences January 25 2000.

Return to Journal of Integer Sequences home page