Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind

Author: Klazar M.^{1, 2}

Source: European Journal of Combinatorics, Volume 21, Number 3, March 2000 , pp. 367-378(12)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

A partition u of [ k ] = {1, 2, ctdot , k } is contained in another partition v of [ l ] if [ l ] has a k -subset on which v inducesu. 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 strengthening of the Stanley–Wilf conjecture is proposed. We prove that the generating function (GF) counting v is rational if (i)R is finite and the number of parts of v is fixed or if (ii)u has only singleton parts and at most one doubleton part. In fact, (ii) is an application of (i). As another application of (i) we prove that for each k the GF counting partitions with k pairs of crossing parts belongs toZ(1 - 4 x).Copyright 2000 Academic Press

Language: English

Document Type: Research article

Affiliations: 1: Katedra aplikované matematiky, Univerzita Karlova, Malostranské nám. 25,, Praha, 118 00, Czech Republic 2: Forschungsinstitut für Diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität Bonn, Lennéstr. 2, Bonn, 53113, Germany

Publication date: 2000-03-01