TOPICS

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

## Explore with Wolfram|Alpha

More things to try:

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

## Referenced on Wolfram|Alpha

Davenport-Schinzel Sequence

## Cite this as:

Weisstein, Eric W. "Davenport-Schinzel Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Davenport-SchinzelSequence.html