Vol. 40, No. 1, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 294: 1
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
A map-theoretic approach to Davenport-Schinzel sequences

Ronald C. Mullin and Ralph Gordon Stanton

Vol. 40 (1972), No. 1, 167–172

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.

Mathematical Subject Classification
Primary: 10L99
Received: 20 August 1970
Published: 1 January 1972
Ronald C. Mullin
University of Waterloo
Ralph Gordon Stanton