๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On abab-free and abba-free Set Partitions

โœ Scribed by Martin Klazar

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
341 KB
Volume
17
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 dif ferent 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 .

๐Ÿ“œ SIMILAR VOLUMES

Partitioning a power set into union-free
Partitioning a power set into union-free classes
โœ Martin Aigner; Dwight Duffus; Daniel J. Kleitman ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 353 KB

Aigner, M., D. Duffus and D.J. Kleitman, Partitioning a power set into union-free classes, Discrete Mathematics 88 (1991) 113-119. Two problems involving union-free colorings of the set of all subsets of an n-set are considered, with bounds obtained for minimum colorings. ## any integer n let g(n)

The free local semilattice on a set
The free local semilattice on a set
โœ John Meakin ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 773 KB
Counting Pattern-free Set Partitions I:
Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind
โœ Martin Klazar ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 160 KB

A partition u of [k] = {1, 2, . . . , k} is contained in another partition v of [l] if [l] has a k-subset on which v induces u. We are interested in counting partitions v not containing a given partition u or a given set of partitions R. This concept is related to that of forbidden permutations. A s