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, ... (OEIS A000012). The values of N_2(n) are the positive integers 1, 2, 3, 4, ... (OEIS A000027). The values of N_3(n) are the odd integers 1, 3, 5, 7, ... (OEIS A005408). The first nontrivial Davenport-Schinzel sequence N_4(n) is given by 1, 4, 8, 12, 17, 22, 27, 32, ... (OEIS A002004). Additional sequences are given by Guy (1994, p. 221) and Sloane.

Explore with Wolfram|Alpha


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."

Referenced on Wolfram|Alpha

Davenport-Schinzel Sequence

Cite this as:

Weisstein, Eric W. "Davenport-Schinzel Sequence." From MathWorld--A Wolfram Web Resource.

Subject classifications