Séminaire Lotharingien de Combinatoire, B23e (1990).
[Formerly: Publ. I.R.M.A. Strasbourg, 1992, 460/S-23, p. 77-83.]

Daniéle Gardy and Dominique Gouyou-Beauchamps

Enumeration of Some Davenport-Schinzel Sequences

Abstract. Davenport-Schinzel sequences of order s are words with no subsequence ababa... of length s+2. We give enumeration results for the case s=2. in particular, we related some of these sequences to Catalan and Schröder numbers.

The paper has been finally published under the title "Enumerating Davenport-Schinzel sequences" in RAIRO Inform. Théor. Appl. 26 (1992), 387-402.