Explicit expressions for the extremal excedance set statistics

Eric Clark; Richard Ehrenborg

doi:10.1016/j.ejc.2008.11.014

Explicit expressions for the extremal excedance set statistics

Eric Clark, Richard Ehrenborg

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The excedance set of a permutation π = π₁ π₂ ⋯ π_k is the set of indices i for which π_i > i. We give explicit formulas for the number of permutations whose excedance set is the initial segment {1, 2, ..., m} and also of the form {1, 2, ..., m, m + 2}. We provide two proofs. The first is an explicit combinatorial argument using rook placements. The second uses the chromatic polynomial and two variable exponential generating functions. We then recast these explicit formulas as L D U-decompositions of associated matrices and show that these matrices are totally non-negative.

Original language	English
Pages (from-to)	270-279
Number of pages	10
Journal	European Journal of Combinatorics
Volume	31
Issue number	1
DOIs	https://doi.org/10.1016/j.ejc.2008.11.014
State	Published - Jan 2010

Bibliographical note

Funding Information:
The authors thank the two referees for their comments on an earlier version of this paper. The authors were partially supported by National Security Agency grant H98230-06-1-0072.

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2008.11.014

Cite this

@article{176a734f680444d89b6b1e0cd68cb26e,

title = "Explicit expressions for the extremal excedance set statistics",

abstract = "The excedance set of a permutation π = π1 π2 ⋯ πk is the set of indices i for which πi > i. We give explicit formulas for the number of permutations whose excedance set is the initial segment {1, 2, ..., m} and also of the form {1, 2, ..., m, m + 2}. We provide two proofs. The first is an explicit combinatorial argument using rook placements. The second uses the chromatic polynomial and two variable exponential generating functions. We then recast these explicit formulas as L D U-decompositions of associated matrices and show that these matrices are totally non-negative.",

author = "Eric Clark and Richard Ehrenborg",

note = "Funding Information: The authors thank the two referees for their comments on an earlier version of this paper. The authors were partially supported by National Security Agency grant H98230-06-1-0072.",

year = "2010",

month = jan,

doi = "10.1016/j.ejc.2008.11.014",

language = "English",

volume = "31",

pages = "270--279",

number = "1",

}

TY - JOUR

T1 - Explicit expressions for the extremal excedance set statistics

AU - Clark, Eric

AU - Ehrenborg, Richard

N1 - Funding Information: The authors thank the two referees for their comments on an earlier version of this paper. The authors were partially supported by National Security Agency grant H98230-06-1-0072.

PY - 2010/1

Y1 - 2010/1

N2 - The excedance set of a permutation π = π1 π2 ⋯ πk is the set of indices i for which πi > i. We give explicit formulas for the number of permutations whose excedance set is the initial segment {1, 2, ..., m} and also of the form {1, 2, ..., m, m + 2}. We provide two proofs. The first is an explicit combinatorial argument using rook placements. The second uses the chromatic polynomial and two variable exponential generating functions. We then recast these explicit formulas as L D U-decompositions of associated matrices and show that these matrices are totally non-negative.

AB - The excedance set of a permutation π = π1 π2 ⋯ πk is the set of indices i for which πi > i. We give explicit formulas for the number of permutations whose excedance set is the initial segment {1, 2, ..., m} and also of the form {1, 2, ..., m, m + 2}. We provide two proofs. The first is an explicit combinatorial argument using rook placements. The second uses the chromatic polynomial and two variable exponential generating functions. We then recast these explicit formulas as L D U-decompositions of associated matrices and show that these matrices are totally non-negative.

UR - http://www.scopus.com/inward/record.url?scp=70350096539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350096539&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2008.11.014

DO - 10.1016/j.ejc.2008.11.014

M3 - Article

AN - SCOPUS:70350096539

SN - 0195-6698

VL - 31

SP - 270

EP - 279

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 1

ER -

Explicit expressions for the extremal excedance set statistics

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this