A Davenport-Schinzel sequence of degree 
over an alphabet of 
letters is a sequence
with no equal consecutive letters and no alternating subsequence of length 
using two distinct letters. Here
and 
are positive integers. The maximum length is
denoted 
.
This degree convention corresponds to order 
in the standard order convention (Sharir and Agarwal 1995).
The values of 
form the trivial sequence
of 1s: 1, 1, 1, ... (OEIS A000012). The values
of 
are the positive integers 1, 2, 3, 4, ... (OEIS
A000027). The values of 
are the odd integers
1, 3, 5, 7, ... (OEIS A005408). The first nontrivial
extremal-length sequence 
is given by 1, 4, 8, 12, 17, 22, 27, 32, ... (OEIS A002004). Additional sequences
are given by Guy (1994, p. 221) and Sloane.
Davenport-Schinzel Sequence
Explore with Wolfram|Alpha
References
Agarwal, P. K. and Sharir, M. "Davenport-Schinzel Sequences and Their Geometric Applications." Ch. 1 in Handbook of Computational Geometry (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, pp. 1-47, 2000.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 on 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, 1970.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 A005408 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Davenport-Schinzel SequenceCite this as:
Weisstein, Eric W. "Davenport-Schinzel Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Davenport-SchinzelSequence.html