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 , est découpée en n! morceaux par les hyperplans . Nous décrivons alors les morceaux qui ont même volume et nous montrons qu'il y a volumes distincts où 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 , is dissected into n! pieces along the planes . We describe which pieces have the same volume, and show that there are distinct volumes, where denotes the nth Catalan number.
Accepté le :
Publié le :
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1016/j.crma.2010.05.005/
[1] Combinatorics of Fulton's essential set, Duke Mathematical Journal, Volume 85 (1996) no. 1, pp. 61-76
[2] 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] 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] On the diagram of 132-avoiding permutations, European Journal of Combinatorics, Volume 24 (2003) no. 6, pp. 759-776 | arXiv
[6] Enumerative Combinatorics, Univ. Press, Cambridge, 2001
Cité par Sources :