Form a sequence from an Alphabet of letters such that there are no consecutive letters and no alternating subsequences of length greater than . Then the sequence is a Davenport-Schinzel sequence if it has maximal length . The value of is the trivial sequence of 1s: 1, 1, 1, ... (Sloane's A000012). The values of are the Positive Integers 1, 2, 3, 4, ... (Sloane's A000027). The values of are the Odd Integers 1, 3, 5, 7, ... (Sloane's A005408). The first nontrivial Davenport-Schinzel sequence is given by 1, 4, 8, 12, 17, 22, 27, 32, ... (Sloane's A002004). Additional sequences are given by Guy (1994, p. 221) and Sloane.
References
Davenport, H. and Schinzel, A. ``A Combinatorial Problem Connected with Differential Equations.'' Amer. J. Math.
87, 684-690, 1965.
Guy, R. K. ``Davenport-Schinzel Sequences.'' §E20 in Unsolved Problems in Number Theory, 2nd ed.
New York: Springer-Verlag, pp. 220-222, 1994.
Roselle, D. P. and Stanton, R. G. ``Results of Davenport-Schinzel Sequences.''
In Proc. Louisiana Conference on Combinatorics, Graph Theory, and Computing. Louisiana State
University, Baton Rouge, March 1-5, 1970 (Ed. R. C. Mullin, K. B. Reid, and D. P. Roselle).
Winnipeg, Manitoba: Utilitas Mathematica, pp. 249-267, 1960.
Sharir, M. and Agarwal, P. Davenport-Schinzel Sequences and Their Geometric Applications.
New York: Cambridge University Press, 1995.
Sloane, N. J. A. Sequences
A000012/M0003,
A000027/M0472,
A002004/M3328, and
A002004/M2400
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.