اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSet partition patterns and statistics
185
0
0.0
(
0
)
تأليف
Samantha Dahlberg
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A set partition $sigma$ of $[n]={1,dots,n}$ contains another set partition $pi$ if restricting $sigma$ to some $Ssubseteq[n]$ and then standardizing the result gives $pi$. Otherwise we say $sigma$ avoids $pi$. For all sets of patterns consisting of partitions of $[3]$, the sizes of the avoidance classes were determined by Sagan and by Goyt. Set partitions are in bijection with restricted growth functions (RGFs) for which Wachs and White defined four fundamental statistics. We consider the distributions of these statistics over various avoidance classes, thus obtaining multivariate analogues of the previously cited cardinality results. This is the first in-depth study of such distributions. We end with a list of open problems.
قيم البحث
اقرأ أيضاً
The $k$-arrangements are permutations whose fixed points are $k$-colored. We prove enumerative results related to statistics and patterns on $k$-arrangements, confirming several conjectures by Blitvic and Steingrimsson. In particular, one of their co
njectures regarding the equdistribution of the number of descents over the derangement form and the permutation form of $k$-arrangements is strengthened in two interesting ways. Moreover, as one application of the so-called Decrease Value Theorem, we calculate the generating function for a symmetric pair of Eulerian statistics over permutations arising in our study.
A restricted growth function (RGF) of length n is a sequence w = w_1 w_2 ... w_n of positive integers such that w_1 = 1 and w_i is at most 1 + max{w_1,..., w_{i-1}} for i at least 2. RGFs are of interest because they are in natural bijection with set
partitions of {1, 2, ..., n}. RGF w avoids RGF v if there is no subword of w which standardizes to v. We study the generating functions sum_{w in R_n(v)} q^{st(w)} where R_n(v) is the set of RGFs of length n which avoid v and st(w) is any of the four fundamental statistics on RGFs defined by Wachs and White. These generating functions exhibit interesting connections with integer partitions and two-colored Motzkin paths, as well as noncrossing and nonnesting set partitions.
We study statistics on ordered set partitions whose generating functions are related to $p,q$-Stirling numbers of the second kind. The main purpose of this paper is to provide bijective proofs of all the conjectures of stein (Arxiv:math.CO/0605670).
Our basic idea is to encode ordered partitions by a kind of path diagrams and explore the rich combinatorial properties of the latter structure. We also give a partition version of MacMahons theorem on the equidistribution of the statistics inversion number and major index on words.
We construct bijections to show that two pairs of sextuple set-valued statistics of permutations are equidistributed on symmetric groups. This extends a recent result of Sokal and the second author valid for integer-valued statistics as well as a pre
vious result of Foata and Han for bivariable set-valued statistics.
Several algorithms with an approximation guarantee of $O(log n)$ are known for the Set Cover problem, where $n$ is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements
are partitioned into $r$ emph{color classes}, and we are required to cover at least $k_t$ elements from each color class $mathcal{C}_t$, using the minimum number of sets. We give a randomized LP-rounding algorithm that is an $O(beta + log r)$ approximation for the Partition Set Cover problem. Here $beta$ denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which $beta$ is known to be sublogarithmic in $n$. We also extend the LP rounding algorithm to obtain $O(log r)$ approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an $o(log r)$-approximation for any of these problems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
