On abab-free and abba-free Set Partitions

AbstractThese 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