Front representation of set partitions

DOI10.1137/090768266MaRDI QIDQ3094921zbMATH OpenOpenAlexFDO

Authors Jang Soo Kim

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.1485

zbMATH Keywords

Catalan numberscrossings and nestingsnoncrossing partitionsset partitions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Let $pi$ be a set partition of $[n]=1,2,\mathrm{...},n$. The standard representation of $pi$ is the graph on the vertex set $[n]$ whose edges are the pairs $(i,j)$ of integers with $i<j$ in the same block which does not contain any integer between $i$ and $j$. The front representation of $pi$ is the graph on the vertex set $[n]$ whose edges are the pairs $(i,j)$ of integers with $i<j$ in the same block whose smallest integer is $i$. Using the front representation, we find a recurrence relation for the number of $\mathrm{12...}k12$-avoiding partitions for $kgeq2$. Similarly, we find a recurrence relation for the number of $k$-distant noncrossing partitions for $k=2,3$. We also prove that the front representation has several joint symmetric distributions for crossings and nestings as the standard representation does.

Recommendations

• On pattern-avoiding partitions
• Set partition patterns and statistics
• Enumeration of (k,2)-noncrossing partitions
• Crossings and nestings of two edges in set partitions
• k-distant crossings and nestings of matchings and partitions

Cited in

(6)

• Restricted growth function patterns and statistics
• A simple bijection for enhanced, classical, and 2-distant \(k\)-noncrossing partitions
• From Dyck paths to standard Young tableaux
• A note on 2-distant noncrossing partitions and weighted Motzkin paths
• Vacillating Hecke tableaux and linked partitions
• Enumeration of (k,2)-noncrossing partitions

This page was built for publication: Front representation of set partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094921)