Abstract :

 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 enumerative results for the pattern p=abab and give an explicit formula for the number p(abab,n,l,k) of such partitions. Our main tool 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.