A solution to one of Knuth's permutation problems

Young, Benjamin

doi:10.1016/j.crma.2010.05.005

Combinatorics

A solution to one of Knuth's permutation problems
[Une solution d'un problème de permutation de Knuth]

Présenté par : Christophe Soulé

Young, Benjamin ¹

¹ Department of Mathematics, McGill University, Burnside Hall room 1005, 805 Sherbrooke Street W, H3A 2K6 Montreal, Quebec, Canada

Comptes Rendus. Mathématique, Tome 348 (2010) no. 13-14, pp. 713-716.

Résumé
Abstract

Nous répondons à un problème posé récemment par Knuth dans le contexte suivant : une boîte de dimension n, dont les arêtes s'alignent en partant de l'origine sur les axes de coordonnées positives et sont de longueur générique $W_{1} < W_{2} < \dots < W_{n}$ , est découpée en n! morceaux par les hyperplans $x_{i} = x_{j}$ . Nous décrivons alors les morceaux qui ont même volume et nous montrons qu'il y a $C_{n}$ volumes distincts où $C_{n}$ désigne le n-ième nombre de Catalan.

We answer a problem posed recently by Knuth: an n-dimensional box, with edges lying on the positive coordinate axes and generic edge lengths $W_{1} < W_{2} < \dots < W_{n}$ , is dissected into n! pieces along the planes $x_{i} = x_{j}$ . We describe which pieces have the same volume, and show that there are $C_{n}$ distinct volumes, where $C_{n}$ denotes the nth Catalan number.

Reçu le : 2010-05-18
Accepté le : 2010-05-28
Publié le : 2010-06-17

DOI : 10.1016/j.crma.2010.05.005

Affiliations des auteurs :

Young, Benjamin ¹

¹ Department of Mathematics, McGill University, Burnside Hall room 1005, 805 Sherbrooke Street W, H3A 2K6 Montreal, Quebec, Canada

@article{CRMATH_2010__348_13-14_713_0,
     author = {Young, Benjamin},
     title = {A solution to one of {Knuth's} permutation problems},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {713--716},
     publisher = {Elsevier},
     volume = {348},
     number = {13-14},
     year = {2010},
     doi = {10.1016/j.crma.2010.05.005},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2010.05.005/}
}

TY  - JOUR
AU  - Young, Benjamin
TI  - A solution to one of Knuth's permutation problems
JO  - Comptes Rendus. Mathématique
PY  - 2010
SP  - 713
EP  - 716
VL  - 348
IS  - 13-14
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2010.05.005/
DO  - 10.1016/j.crma.2010.05.005
LA  - en
ID  - CRMATH_2010__348_13-14_713_0
ER  -

%0 Journal Article
%A Young, Benjamin
%T A solution to one of Knuth's permutation problems
%J Comptes Rendus. Mathématique
%D 2010
%P 713-716
%V 348
%N 13-14
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2010.05.005/
%R 10.1016/j.crma.2010.05.005
%G en
%F CRMATH_2010__348_13-14_713_0

Young, Benjamin. A solution to one of Knuth's permutation problems. Comptes Rendus. Mathématique, Tome 348 (2010) no. 13-14, pp. 713-716. doi : 10.1016/j.crma.2010.05.005. http://www.numdam.org/articles/10.1016/j.crma.2010.05.005/

Bibliographie
Cité par

[1] Eriksson, Kimmo; Linusson, Svante Combinatorics of Fulton's essential set, Duke Mathematical Journal, Volume 85 (1996) no. 1, pp. 61-76

[2] Fulmek, Markus Enumeration of permutations containing a prescribed number of occurrences of a pattern of length 3, Advances in Applied Mathematics, Volume 30 (2003) no. 4, pp. 607-632 | arXiv

[3] Fulton, W. Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, Duke Math. J, Volume 65 (1992) no. 3, pp. 381-420

[4] Donald E. Knuth, Permutation problems, Talk (1056-05-168) at the Joint Meetings of the AMS-CMS, San Francisco, 2010

[5] Reifegerste, Astrid On the diagram of 132-avoiding permutations, European Journal of Combinatorics, Volume 24 (2003) no. 6, pp. 759-776 | arXiv

[6] Stanley, R.P. Enumerative Combinatorics, Univ. Press, Cambridge, 2001

Cité par Sources :