Davenport-Schinzel Sequence

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, ... (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 Davenport-Schinzel 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.

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 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, and A002004/M3328 in "The On-Line Encyclopedia of Integer Sequences."