This page describes the sequences I contributed to the OEIS and gives some complementary information for some of them.
Please email me any comments and suggestions.
Here is the table of the sequences; they link to further explanations below on this page.
The understanding of the monoid of endomorphisms and the group of automorphisms of a given object is essential to its understanding. This is true for groups, but also fields (Galois theory), topological spaces (mapping class group), manifolds, Riemann surfaces (Teichmüller theory)…
The sequence A137316 is a table read by rows where T(n,k) is the number of automorphisms of the "kth" group of order n, where the ordering of groups of a given order is such that the lines T(n,.) are non-decreasing (note that this does not determine a unique ordering of the groups). The sequence A138565 is the subsequence of A137316 restricted to abelian groups. The tables begin as follows:
For example, the first line with two numbers corresponds to the two groups of order 4, the cyclic group C4 and the Klein group C2×C2, whose automorphism groups are respectively the group C4× ≅ C2 and the symmetric group S3.1 1 1 1 2 2 2 6 2 6 4 4 2 6 2 6 6 4 8 8 24 168 4 8 168 6 48 6 48 4 20 4 10 10 4 12 12 12 24 4 12 12 12 6 42 6 8 8 … …
The problem of determining the automorphism group of given classes of groups has many partial answers. A general formula is known for finite abelian groups (see Hillar and Rhea's exposition, which also describes endomorphisms of finite abelian p-groups). Conversely, one can ask which groups arise as automorphism groups, and which groups have a given automorphism group. Here, the study begins with the following three theorems:
Theorem (Baer 1955, Alperin 1961)
A group has a finite endomorphism monoid if and only if it is itself finite.
Theorem (Alperin 1961)
A finitely generated group has a finite automorphism group if and only if it is a finite central extension
of a cyclic group.
Theorem (Ledermann and Neumann 1956)
There exists a least sequence an of natural numbers such that any finite group of order at least
an has at least n automorphisms.
The sequence A137315 is the sequence of the third theorem. With offset 1, it begins as follows:
For all n, LNn is odd, and LNn ≤ nn(1 + log2 n) (a very rough bound). It is conjectured that LN2n-1 = LN2n when n>1. This sequence has been computed up to n = 48 by MacHale and Sheehy, who also provide a complete list of finite groups with at most 47 automorphisms as well as a complete list of groups with at most 49 endomorphisms.1, 3, 7, 7, 13, 13, 19, 19, 31, 31, 31, 31, 43, 43, 43, 43, 61, 61, 61, 61, 67, 67, 67, 67, 91, …
Theorem
If G is a finite abelian group, then |Aut(G)| ≥ φ(|G|), with equality if and only if G is cyclic.
The sequence A139795 is defined by an being the least m such that k ≥ m implies φ(k) ≥ n. The cyclic groups show that an ≤ LNn. Even though there is equality up to n = 48, the inequality can be strict. For example, Aut(12.M22) = M22.2, where M22 is the Mathieu group of order 27.32.5.7.11, so that LN28.32.5.7.11 + 1 > 29.33.5.7.11, but a28.32.5.7.11 + 1 = 2.3.5.72.11.13.23 + 1 < 29.33.5.7.11.
It follows from the above that there exists a least sequence bn of natural numbers such that any finite group of order at least bn has at least n endomorphisms. The endomorphism monoid of the cyclic group of order n being (Zn,.), and the trivial endomorphism not being a automorphism for non-trivial groups, one has n ≤ bn ≤ an-1. Actually, bn = n for n ≤ 50, and this is conjectured to hold for all n.
The number of partitions of an integer n into p positive integers is denoted by Partp(n) (sequence A008284). Part0(0) = 1 and the other non-zero values are exactly those with 0 < p ≤ n. If n > 0, Part1(n) = Partn(n) = 1 and if n ≥ 0, Part2(n) = [n/2]. The table, with offset (1,1), begins as follows:
The sum of the nth row is the number of partitions of n into positive parts, Part(n) (sequence A000041). Two recurrence formulas are easily derived:1 1 1 1 2 1 1 1 3 1 2 1 1 5 1 2 2 1 1 7 1 3 3 2 1 1 11 1 3 4 3 2 1 1 15 1 4 5 5 3 2 1 1 22 … …
Partp(n) = Σpi=0 Parti(n-p)by noting for the first formula that the p parts are either of size 1 or greater, so that it suffices to consider the partitions of n-p into 0 to p parts, and for the second formula that either all parts have size at least two (second summand) or at least a part has size one (first summand). From the first formula, it follows that Partp(n) = Part(n-p) if p ≥ ceil(n/2).
Partp(n) = Partp-1(n-1) + Partp(n-p)
One can also consider the number of partitions of a couple of integers (m,n) into couples of positive integers
(mi,ni) such that
Σpi=0 mi = m and
Σpi=0 miq.ni = m for
a non-negative integer q.
This definition is motivated by the case q = 2, which intervenes in the counting of groupoids (categories
all of whose morphisms are invertible, see below).
We denote by Partq(m,n) the number of such partitions.
Then Partq(0,0) = 1 and the other non-zero values are exactly those with
m, n > 0 if q = 0 and
0 < n ≤ m if q > 0.
For m ≥ 1, Partq(m,1) = 1.
For q = 0, Part0(m,n) = Part0(n,m) is given by the
sequence A090806.
For q = 1, Part1(m,n) is given by the sequence A136405, which, with offset (1,1), begins as follows:
For the second column and the diagonal, Part1(n,2) = [n/2] + (1+(-1)n)/2 (sequence A028242) and Part1(n,n) = Part(n). The sum of the nth row is A006171(n) (number of factorization patterns of polynomials of degree n over integers, or rationals).1 1 1 2 3 1 1 3 5 1 3 2 5 11 1 2 4 3 7 17 1 4 6 7 5 11 34 1 3 7 8 11 7 15 52 1 5 8 16 14 17 11 22 94 … …
For q = 2, Part2(m,n) is given by the sequence A136406, which, with offset (1,1), begins as follows:
The sum of the nth row is A004101(n). The sequence A137504 gives the limiting values of this table: A137504(k) = Part1(n,n-k) for any n ≥ 2k. With offset 0, it begins as follows:1 1 1 1 2 1 1 1 3 1 3 1 1 6 1 2 3 1 1 8 1 3 4 3 1 1 13 1 3 5 4 3 1 1 18 1 5 6 8 4 3 1 1 29 … …
1, 1, 3, 4, 8, 11, 21, 28, 47, 64, 100, 135, 205, 273, 398, 530, 749, 989, 1373, 1796, 2446, …
Directed multigraphs with loops are arguably the easiest graphs to define:
they consist of a set of arcs, a set of vertices, and two functions, "source" and "target",
from the set of arcs to the set of vertices.
The degree of a vertex is the couple formed by the numbers of its preimages
under the functions "source" and "target" respectively.
By a multigraph, we mean a directed multigraph with loops and no vertex of degree 0.
This is the notion of graph best suited to the study of categories.
Important properties of these graphs are
connectedness (the corresponding undirected graph is connected),
strong connectedness (there exists a path between any couple of vertices),
transitivity (the existence of a path between two points implies the existence of an arc between those two points) and
reflexivity (every vertex has a loop).
The sequences
A136564,
A139621,
A139622,
A139623,
A139624 and
A139625
represent the numbers of, respectively, all, connected, strongly connected, transitive, connected transitive and
strongly connected transitive multigraphs.
They are tables T(n,k) where n is the number of arcs and k the number of vertices.
These tables have offset (1,1) in the OEIS, but we note that for al of them,
T(0,0) = 1, corresponding to the empty graph,
and if n > 0, T(n,0) = T(0,n) = 0 and
T(n,1) = 1.
The row lengths are respectively 2n, n+1, n, 2n, n+1 and [√n]
(that is, the non-zero values are exactly those with n = k = 0 and
1 ≤ k ≤ 2n, n+1, …).
The row sums of these tables are respectively given by the sequences
A052171,
A137975,
A139627,
A139628,
A139629 and
A139630,
which then represent the numbers of multigraphs of a given kind with n arcs
(with offset 0, so that a(0) = 1).
Note that A052171 and A139628 are the Euler transforms of A137975 and A139629 respectively.
The partial row sums of these triangular tables are square tables with stationary rows.
Equationally, one has T'(n,k) = Σkp=0 T(n,p).
They are respectively given by the sequences
A138107,
A129620,
A143841,
A138352,
A136868 and
A143842,
which then represent the numbers of multigraphs of a given kind with n arcs and k vertices,
possibly of degree 0.
These tables have offset (0,0), so that for n ≥ 0, T(0,n) = T(n,1) = 1, and
for n > 0, and T(n,0) = 0.
The third, fourth and fifth columns of A138107 are respectively given by the sequences
A005993,
A050927 and
A050929.
The first terms of these eighteen sequences are gathered here. Help expanding them, and contribute more terms to the OEIS !
Some of the triangular tables might have limiting values, that is, T(n,n-k) might not depend on n ≥ f(k). For instance (with self-explanatory subscripts),
Groupoids are categories all of whose morphisms are invertible. A groupoid with one object being the same thing as a group, groupoids can be thought of as « groups on several objects ». It is easy to see that a connected groupoid is isomorphic to an elementary groupoid, that is, a groupoid of the form S×G×S where S is a set, G is a group, and composition is given by (z,h,y).(y,g,x) = (z,hg,x), and defined only in this case.
The sequence A140185 gives the number of connected groupoids with n elements. Since the number of connected groupoids with n elements and k identities is non-zero only when n = k = 0 or n = m.k2, in which case it is the number of groups of order n (sequence A000001), one has Grpdc(0) = 1 and if n>0, Grpdc(n) = Σk2|n Grp(n/k2). As a consequence, Grpdc(n) ≥ Grp(n) with equality if and only if n is square-free. The sequences of numbers of groups and groupoids begin as follow:
The sequences A140186 and A140187 give respectively the number of connected groupoids with n more morphisms than objects and with n times as many morphisms as objects. One has Grpdc'(0) = 2 and if n>0, Grpdc'(n) = Σk2|n+k Grp((n+k)/k2). Likewise, Grpdc"(0) = 1 and if n>0, Grpdc"(n) = 1 + Σk|n Grp(n/k) (the 1 accounts for the empty groupoid). In particular, Grpdc'(n) ≥ Grp(n+1) and if n>1, Grpdc"(n) ≥ 2 + Grp(n) with equality for the latter if and only if n is prime. The sequences begin as follows (the first line gives the number of groups):0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, … 1, 1, 1, 1, 3, 1, 2, 1, 6, 3, 2, 1, 6, 1, 2, 1, 17, 1, 6, 1, 6, 2, 2, 1, 17, 3, 2, 6, 5, …
0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, … 2, 1, 2, 2, 1, 2, 3, 5, 2, 2, 2, 5, 2, 2, 3, 15, 1, 5, 2, 5, 3, 2, 3, 15, 3, 2, 6, 4, … 1, 2, 3, 3, 5, 3, 6, 3,10, 5, 6, 3,13, 3, 6, 5, 24, 3,13, 3,13, 6, 6, 3, 33, 5, 6,10,12, …
The sequence A140188
is a table read by rows where T(n,k) is the number of groupoids with n morphisms and k objects.
T(n,k) is the sum over the quadratic bi-partitions (ni,ki) of (n,k)
(see above)
of the "product" of the Grpd(ni), where the "product" is the usual product except when
(ni1,ki1) = … = (nip,kip),
in which case the number ap is replaced by
the binomial coefficient ( a + pp- 1 ).
The first column is of course Grpd(n,1) = Grp(n).
Also, Grpd(n,k) ≥ Part2(n,k).
The row sums of this table are given by
the sequence A140189,
which then represents the number of groupoids with n morphisms. It is the Euler transform of Grpdc.
The table also has limiting values, that is, for 2k≤n, Grpd(n,n-k) does not depend on n.
These values are given by
the sequence A140190.
It is the Euler transform of Grpdc'(n).
These are two variants of a classic example of a rapidly growing function, that is a computable but not primitive recursive. More details can be found on Wikipedia, Ackermann function and Mathworld, Ackermann function.
The sequence A143796 begins as follows:
The sequence A143797 is a variant due to Buck and begins as follows:1 2 3 4 5 6 7 … 2 3 4 5 6 7 8 … 3 5 7 9 11 13 15 … 5 13 29 61 125 253 509 … 13 65533 . . . . . … 65533 . . . . . . …
1 2 3 4 5 6 7 … 2 3 4 5 6 7 8 … 0 2 4 6 8 10 12 … 1 2 4 8 16 32 64 … 1 2 4 16 65536 . . … 1 2 4 . . . . …