Sylvie Corteel ; Pawel Hitczenko - Expected values of statistics on permutation tableaux

dmtcs:3518 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3518
Expected values of statistics on permutation tableauxArticle

Authors: Sylvie Corteel 1; Pawel Hitczenko 1,2

  • 1 Laboratoire de Recherche en Informatique
  • 2 Department of mathematics [Philadelphie]

Permutation tableaux are new objects that were introduced by Postnikov in the context of enumeration of the totally positive Grassmannian cells. They are known to be in bijection with permutations and recently, they have been connected to PASEP model used in statistical physics. Properties of permutation tableaux became a focus of a considerable research activity. In this paper we study properties of basic statistics defined on permutation tableaux. We present a simple and unified approach based on probabilistic techniques and use it to compute the expected values of basic statistics defined on permutation tableaux. We also provide a non―bijective and very simple proof that there are n! permutation tableaux of length n.


Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: permutation tableau,expected value,binomial distribution,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • US-France Cooperative Research: Analysis and Evaluation of Combinatorial Structures and Algorithms; Funder: National Science Foundation; Code: 0230800

5 Documents citing this article

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 223 times.