On abab-free and abba-free set partitions

These are partitions of [l] = {1, 2,..., l} into n blocks such that no four-term subsequence of [l] induces the mentioned pattern and each k consecutive numbers of [l] fall into different blocks. These structures are motivated by Davenport-Schinzel sequences. We summarize and extend known enumeriative results for the pattern p = abab and give an explicit formula for the number p(abab,n,l,k) of such partitions. Our main tools are generating functions. We determine the corresponding generating function for p = abba and k = 1, 2, 3. For k = 2 there is a connection with the number of directed animals. We solve exactly two related extremal problems. (C) 1995 Academic Press Limited.