Journal of Integer Sequences, Vol. 12 (2009), Article 09.5.1

Equidistribution of Descents, Adjacent Pairs, and Place-Value Pairs on Permutations

Emeric Deutsch Department of Mathematics Polytechnic Institute of NYU Brooklyn, NY 11201 USA Sergey Kitaev The Mathematics Institute School of Computer Science Reykjavík University IS-103 Reykjavík Iceland Jeffrey Remmel Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112 USA

Abstract:

An -descent in a permutation is a pair of adjacent elements such that the first element is from , the second element is from , and the first element is greater than the second one. An -adjacency in a permutation is a pair of adjacent elements such that the first one is from and the second one is from . An -place-value pair in a permutation is an element in position , such that is in and is in . It turns out, that for certain choices of and some of the three statistics above become equidistributed. Moreover, it is easy to derive the distribution formula for -place-value pairs thus providing distribution for other statistics under consideration too. This generalizes some results in the literature. As a result of our considerations, we get combinatorial proofs of several remarkable identities. We also conjecture existence of a bijection between two objects in question preserving a certain statistic.

Full version:  pdf,    dvi,    ps,    latex

Received March 14 2009; revised version received June 21 2009. Published in Journal of Integer Sequences, June 21 2009.