On multiple pattern avoiding set partitions

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say that two sets S and T of patterns are equivalent if for each n the number of partitions of size n avoiding all the members of S is the same as the number of those that avoid all the members of T.     

A major index for matchings and set partitions

We introduce a statistic pmaj(P) for partitions of [n], and show that it is equidistributed with cr₂, the number of 2-crossings, over all partitions of [n] with given sets of minimal block elements and maximal block elements. This generalizes the classical result of equidistribution for the permutation statistics inv and maj.     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

Pattern avoidance in “flattened” partitions

To flatten a set partition (with apologies to Mathematica^®) means to form a permutation by erasing the dividers between its blocks. Of course, the result depends on how the blocks are listed. For the usual listing—increasing entries in each block and blocks arranged in increasing order of their first entries—we count the partitions of [n] whose flattening avoids a single 3-letter pattern. Five counting sequences arise: a null sequence, the powers of 2, the Fibonacci numbers, the Catalan numbers, and the binomial transform of the Catalan numbers.     

On cyclic strings avoiding a pattern

We count the number of cyclic strings over an alphabet that avoid a single pattern under two different assumptions. In the first case, we assume that the symbols of the alphabet are on numbered positions on a circle, while in the second case we assume that the symbols can be freely rotated on the circle (i.e., we deal with necklaces). In each case, we provide a generating function, and we explain how these two cases are related. For the situation of avoiding more than one pattern, we formulate a general conjecture for the first case, and a conditional result for the second case. We also explain the differences between our theory and the theory of Edlin and Zeilberger (2000) by emphasizing how we modified the definition of the enumeration of cyclic strings that avoid one or more patterns when their lengths are less than the length of the longest pattern.     

Bargraph statistics on words and set partitions

In this paper, we consider statistics on partitions of an n-element set represented as a subset of the bargraphs that have n horizontal steps. More precisely, we find the joint distribution of the area and up step statistics on the latter subset of bargraphs, thereby obtaining new refined counts on partitions having a fixed number of blocks. Furthermore, we give explicit formulas in terms of the Stirling numbers for the total area and number of up steps in bargraphs corresponding to partitions, providing both algebraic and combinatorial proofs. Finally, we find asymptotic estimates for the average and total values of these statistics and as a consequence obtain some new identities for the Stirling and Bell numbers.     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

On partitions of a partially ordered set

Using linear programming we prove a generalization of Greene and Kleitman's generalization of Dilworth's theorem on the decomposition of a partially ordered set into chains.     

Reconfiguration of subspace partitions

Let $q$ be a fixed prime power and let $V\left(n,q\right)$ denote a vector space of dimension $n$ over the Galois field with $q$ elements. A subspace partition (also called “vector space partition”) of $V\left(n,q\right)$ is a collection of subspaces of $V\left(n,q\right)$ with the property that every nonzero element of $V\left(n,q\right)$ appears in exactly one of these subspaces. Given positive integers $a,b,n$ such that $1\le a<b<n$, we say a subspace partition of $V\left(n,q\right)$ has type $a^x{b}^y$ if it is composed of $x$ subspaces of dimension $a$ and $y$ subspaces of dimension $b$. Let $c=\text{gcd}\left(a,b\right)$. In this paper, we prove that if $b$ divides $n$, then one can (algebraically) construct every possible subspace partition of $V\left(n,q\right)$ of type $a^x{b}^y$ whenever $y\ge \left(q^e?1\right)∕\left(q^b?1\right)$, where $0\le e<ab∕c$ and $n\equiv e\left(\mathrm{mod}ab∕c\right)$. Our construction allows us to sequentially reconfigure batches of $\left(q^a?1\right)∕\left(q^c?1\right)$ subspaces of dimension $b$ into batches of $\left(q^b?1\right)∕\left(q^c?1\right)$ subspaces of dimension $a$. In particular, this accounts for all numerically allowed subspace partition types $a^x{b}^y$ of $V\left(n,q\right)$ under some additional conditions, for example, when $e=b$.     

On colored set partitions of type B n

Generalizing Reiner’s notion of set partitions of type B _n , we define colored B _n -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B _n -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B _n -partition. We find an asymptotic expression of the total number of colored B _n -partitions up to an error of O(n ^?1/2log^7/2 n], and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored B _n -partitions.     

On partitions of K2,3-free graphs under degree constraints

Suppose that $s$, $t$ are two positive integers, and $?$ is a set of graphs. Let $g(s,t;?)$ be the least integer $g$ such that any $?$-free graph with minimum degree at least $g$ can be partitioned into two sets which induced subgraphs have minimum degree at least $s$ and $t$, respectively. For a given graph $H$, we simply write $g(s,t;H)$ for $g(s,t;?)$ when $?=\left\{H\right\}$. In this paper, we show that if $s,t\ge 2$, then $g(s,t;K_{2,3})\le s+t$ and $g(s,t;\{K_3,C_8,K_{2,3}\})\le s+t?1$. Moreover, if $?$ is the set of graphs obtained by connecting a single vertex to exactly two vertices of $K_4?e$, then $g(s,t;?)\le s+t$ on $?$-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).     

Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

Random partitions with restricted part sizes

For a subset of positive integers let Ω(n, ) be the set of partitions of n into summands that are elements of . For every λ ∈ Ω(n, ), let M _n(λ) be the number of parts, with multiplicity, that λ has. Put a uniform probability distribution on Ω(n, ), and regard M _n as a random variable. In this paper the limiting density of the (suitably normalized) random variable M _n is determined for sets that are sufficiently regular. In particular, our results cover the case = {Q(k) : k ≥ 1}, where Q(x) is a fixed polynomial of degree d ≥ 2. For specific choices of Q, the limiting density has appeared before in rather different contexts such as Kingman's coalescent, and processes associated with the maxima of Brownian bridge and Brownian meander processes. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008