FRONT REPRESENTATION OF SET PARTITIONS

Let π be a set partition of [n] = {1, 2, . . . , n}. The standard representation of π 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 π is the graph on the...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2011, Vol.25 (1-2), p.447-461
Main Author: Kim, Jang Soo
Format: Article
Language:English
Subjects:
Algebra
Applied mathematics
Blocking
Combinatorics
Combinatorics. Ordered structures
Difference and functional equations, recurrence relations
Exact sciences and technology
Graph representations
Graphs
Integers
Mathematical analysis
Mathematics
Nesting
Numerical analysis
Numerical analysis. Scientific computation
Partitions
Representations
Sciences and techniques of general use
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let π be a set partition of [n] = {1, 2, . . . , n}. The standard representation of π 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 π 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 12 ... k12-avoiding partitions for k ≥ 2. 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. [PUBLICATION ABSTRACT]
ISSN:0895-4801
1095-7146
DOI:10.1137/090768266