On abab-free and abba-free Set Partitions

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