An (n,d) Davenport-Schinzel
Sequence (more briefly, a DS sequence) is a sequence of symbols selected from 1, 2,
⋯,n, with the properties that (1) no two adjacent symbols are identical, (2) no
subsequence of the form abab… has length greater than d, (3) no symbol
can be added to the end of the sequence, without violating (1) or (2). It is
shown that the set of (n,3)DS sequences is in one-to-one correspondence
with the set of rooted planar maps on n vertices in which every edge of
the map is incident with the root face. The number of such sequences and
the number of such sequences of longest possible length 2n − 1 is explicitly
determined.
