𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On numbers of Davenport-Schinzel sequences

✍ Scribed by Martin Klazar

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
522 KB
Volume
185
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

One 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 k-n+l 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. (~

πŸ“œ SIMILAR VOLUMES

Combinatorial aspects of Davenport-Schin
Combinatorial aspects of Davenport-Schinzel sequences
✍ Martin Klazar πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 994 KB

A finite sequence u = ala2 . up of some symbols is contained in another sequence c = h1b2.. b, if there is a subsequence b,,bi, b,, of u which can be identified, after an injective renaming of symbols, with u. We say that u = u1a2.. .up is k-regular if i -j > k whenever a, = a,, i > j. We denote fur