On numbers of Davenport-Schinzel sequences

AbstractOne class of Davenport-Schinzel sequences consists of finite sequences over n symbols without immediate repetitions and without any subsequence of the type abab. We present a bijective encoding of such sequences by rooted plane trees with distinguished nonleaves and we give a combinatorial proof of the formula 1k−n+12k−2n−k−1k−1 for the number of such normalized sequences of length k. The formula was found by Gardy and Gouyou-Beauchamps by means of generating functions. We survey previous results concerning counting of DS sequences and mention several equivalent enumerative problems