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
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Contacts
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
Abstract

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
Milestones
Received: 20 August 1970
Published: 1 January 1972
Authors
Ronald C. Mullin
University of Waterloo
ON
Canada
Ralph Gordon Stanton