اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn pattern-avoiding partitions
65
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A emph{set partition} of the set $[n]={1,...c,n}$ is a collection of disjoint blocks $B_1,B_2,...c, B_d$ whose union is $[n]$. We choose the ordering of the blocks so that they satisfy $min B_1<min B_2<...b<min B_d$. We represent such a set partition by a emph{canonical sequence} $pi_1,pi_2,...c,pi_n$, with $pi_i=j$ if $iin B_j$. We say that a partition $pi$ emph{contains} a partition $sigma$ if the canonical sequence of $pi$ contains a subsequence that is order-isomorphic to the canonical sequence of $sigma$. Two partitions $sigma$ and $sigma$ are emph{equivalent}, if there is a size-preserving bijection between $sigma$-avoiding and $sigma$-avoiding partitions. We determine several infinite families of sets of equivalent patterns; for instance, we prove that there is a bijection between $k$-noncrossing and $k$-nonnesting partitions, with a notion of crossing and nesting based on the canonical sequence. We also provide new combinatorial interpretations of the Catalan numbers and the Stirling numbers. Using a systematic computer search, we verify that our results characterize all the pairs of equivalent partitions of size at most seven. We also present a correspondence between set partitions and fillings of Ferrers shapes and stack polyominoes. This correspondence allows us to apply recent results on polyomino fillings in the study of partitions, and conversely, some of our results on partitions imply new results on polyomino fillings and ordered graphs.
قيم البحث
اقرأ أيضاً
An alternating permutation of length $n$ is a permutation $pi=pi_1 pi_2 ... pi_n$ such that $pi_1 < pi_2 > pi_3 < pi_4 > ...$. Let $A_n$ denote set of alternating permutations of ${1,2,..., n}$, and let $A_n(sigma)$ be set of alternating permutations
in $A_n$ that avoid a pattern $sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bona, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.
We introduce consecutive-pattern-avoiding stack-sorting maps $text{SC}_sigma$, which are natural generalizations of Wests stack-sorting map $s$ and natural analogues of the classical-pattern-avoiding stack-sorting maps $s_sigma$ recently introduced b
y Cerbai, Claesson, and Ferrari. We characterize the patterns $sigma$ such that $text{Sort}(text{SC}_sigma)$, the set of permutations that are sortable via the map $scirctext{SC}_sigma$, is a permutation class, and we enumerate the sets $text{Sort}(text{SC}_{sigma})$ for $sigmain{123,132,321}$. We also study the maps $text{SC}_sigma$ from a dynamical point of view, characterizing the periodic points of $text{SC}_sigma$ for all $sigmain S_3$ and computing $max_{piin S_n}|text{SC}_sigma^{-1}(pi)|$ for all $sigmain{132,213,231,312}$. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map $s_{132}$, and we show that the maximum number of iterations of $s_{132}$ needed to send a permutation in $S_n$ to a periodic point is $n-1$. The paper ends with numerous open problems and conjectures.
A permutation $sigmainmathfrak{S}_n$ is simsun if for all $k$, the subword of $sigma$ restricted to ${1,...,k}$ does not have three consecutive decreasing elements. The permutation $sigma$ is double simsun if both $sigma$ and $sigma^{-1}$ are simsun.
In this paper we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian s
tatistic in terms of generalized pattern functions, which is denoted $stat$. Recently, Amini investigated the equidistributions of these Mahonian statistics over sets of pattern avoiding permutations. Moreover, he posed several conjectures. In this paper, we construct a bijection from $S_n(213)$ to $S_n(231)$, which maps the statistic $(maj,stat)$ to the statistic $(stat,maj)$. This allows us to give solutions to some of Aminis conjectures.
In this note, we study the mean length of the longest increasing subsequence of a uniformly sampled involution that avoids the pattern $3412$ and another pattern.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
