Davenport-Schinzel Sequence

Form a sequence from an Alphabet of letters $[1, n]$ such that there are no consecutive letters and no alternating subsequences of length greater than $d$. Then the sequence is a Davenport-Schinzel sequence if it has maximal length $N_d(n)$. The value of $N_1(n)$ is the trivial sequence of 1s: 1, 1, 1, ... (Sloane's A000012). The values of $N_2(n)$ are the Positive Integers 1, 2, 3, 4, ... (Sloane's A000027). The values of $N_3(n)$ are the Odd Integers 1, 3, 5, 7, ... (Sloane's A005408). The first nontrivial Davenport-Schinzel sequence $N_4(n)$ 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.