cp's OEIS Frontend

A005118 Number of simple allowable sequences on 1..n containing the permutation 12...n.

%I A005118 M2097 #100 Nov 11 2024 22:29:47
%S A005118 1,1,1,2,16,768,292864,1100742656,48608795688960,29258366996258488320,
%T A005118 273035280663535522487992320,44261486084874072183645699204710400,
%U A005118 138018895500079485095943559213817088756940800
%N A005118 Number of simple allowable sequences on 1..n containing the permutation 12...n.
%C A005118 For n >= 2 by the hook length formula a(n) is also the number of Young tableaux of size 1+2+...+(n-1) = n*(n-1)/2 that correspond to the partition (1,2,...n-1), i.e., triangular Young tableaux. For example, for n=5 the shape of the tableau is xxxx / xxx / xx / x. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 04 2001
%C A005118 Also, a(n) is the degree of the symplectic Grassmannian, the projective variety of all maximal isotropic subspaces in a complex vector space of dimension 2n-2 with a symplectic form. See Hiller's paper. - Burt Totaro (b.totaro(AT)dpmms.cam.ac.uk), Oct 29 2002
%C A005118 Also, for n >= 2, a(n) is the number of maximal chains in the poset of Dyck paths ordered by inclusion. - Jennifer Woodcock (Jennifer.Woodcock(AT)ugdsb.on.ca), May 21 2008
%C A005118 a(n) is the number of minimal decompositions of the "flip" permutation n(n-1)..21 in terms of the n-1 standard Coxeter generators (i i+1) ("reduced decompositions", cf. Stanley). As such, it is also the number of positive n-strand braid words representing the Garside braid Delta(n) (the half-turn) (cf. Epstein's book, lemma 9.1.14). - _Maxime Bourrigan_, Apr 04 2011
%C A005118 For n >= 1, the normalized volume of the subpolytope of the Birkhoff polytope obtained by taking the convex hull of all (2n)x(2n) permutation matrices corresponding to alternating permutations that also avoid the pattern 123. - _Robert Davis_, Dec 04 2016
%D A005118 D. B. A. Epstein with J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston, MA, 1992. xii+330 pp.
%D A005118 J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 102.
%D A005118 G. Kreweras, Sur un problème de scrutin à plus de deux candidats, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87.
%D A005118 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005118 T. D. Noe, <a href="/A005118/b005118.txt">Table of n, a(n) for n = 0..40</a>
%H A005118 Omer Angel, Alexander E. Holroyd, Dan Romik, and Balint Virag, <a href="https://arxiv.org/abs/math/0609538">Random Sorting Networks</a>, arXiv preprint arXiv:0609538 [math.PR], 2006.
%H A005118 Joerg Arndt, <a href="/A005118/a005118.txt">The a(4)=16 Young tableaux of shape [3, 2, 1]</a>.
%H A005118 Sara C. Billey and Peter R. W. McNamara, <a href="http://arxiv.org/abs/1505.01115">The contributions of Stanley to the fabric of symmetric and quasisymmetric functions</a>, arXiv preprint, 2015.
%H A005118 Tobias Boege, Alessio D'Alì, Thomas Kahle, Bernd Sturmfels, <a href="https://arxiv.org/abs/1710.07175">The Geometry of Gaussoids</a>, arXiv:1710.07175 [math.CO], 2017.
%H A005118 R. Davis and B. Sagan, <a href="https://arxiv.org/abs/1609.01782">Pattern-Avoiding Polytopes</a>, 2016
%H A005118 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000001/">The number of ways to write a permutation as a minimal length product of simple transpositions</a>
%H A005118 M. J. Hay, J. Schiff, and N. J. Fisch, <a href="http://arxiv.org/abs/1508.03499">Maximal energy extraction under discrete diffusive exchange</a>, arXiv preprint arXiv:1508.03499 [physics.plasm-ph], 2015.
%H A005118 H. Hiller, <a href="http://dx.doi.org/10.5169/seals-43873">Combinatorics and intersection of Schubert varieties</a>, Comment. Math. Helv. 57 (1982), 41-59.
%H A005118 D. Kim, <a href="https://doi.org/10.1007/s00373-024-02852-y">Finding k Shortest Paths in Cayley Graphs of Finite Groups</a>, Graphs and Combinatorics 40, 120 (2024). See Formula at p. 13.
%H A005118 G. Kreweras, <a href="/A005118/a005118.pdf">Sur un problème de scrutin à plus de deux candidats</a>, Publications de l'Institut de Statistique de l'Université de Paris, 26 (1981), 69-87. [Annotated scanned copy]
%H A005118 Joshua Maglione and Christopher Voll, <a href="https://arxiv.org/abs/2410.08075">Hall-Littlewood polynomials, affine Schubert series, and lattice enumeration</a>, arXiv:2410.08075 [math.CO], 2024. See pp. 34, 39.
%H A005118 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>
%H A005118 R. P. Stanley, <a href="https://arxiv.org/abs/math/0501256">Ordering events in Minkowski space</a>, arXiv:math/0501256 [math.CO], 2005.
%H A005118 R. P. Stanley, <a href="http://dx.doi.org/10.1016/S0195-6698(84)80039-6">On the number of reduced decompositions of elements of Coxeter groups</a>, European J. Combin., 5 (1984), 359-372.
%F A005118 a(n) = C(n, 2)!/(1^{n-1} * 3^{n-2} *...* (2n-3)^1 ).
%F A005118 a(n) = (n*(n-1)/2)!/A057863(n-1) (n>=1). - _Emeric Deutsch_, May 21 2004
%F A005118 a(n) = A153452(A002110(n-1)). - _Naohiro Nomoto_, Jan 01 2009
%F A005118 From _Alois P. Heinz_, Nov 18 2012: (Start)
%F A005118 a(n+1) = A219272(A000217(n),n) = A219274(A000217(n),n) = A219311(A000217(n),n).
%F A005118 a(n) = A193536(n,A000217(n-1)) = A193629(n,A000217(n-1)). (End)
%F A005118 a(n) ~ sqrt(Pi) * n^(n^2/2-n/2+23/24) * exp(n^2/4-n/2+7/24) / (A^(1/2) * 2^(n^2-n/2-7/24)), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - _Vaclav Kotesovec_, Nov 13 2014
%p A005118 A005118 := proc(n) local i; binomial(n,2)!/product( (2*i+1)^(n-i-1), i=0..n-2 ); end;
%t A005118 Table[Binomial[n, 2]!/Product[(2*i + 1)^(n - i - 1), {i, 0, n - 2}], {n, 0, 10}] (* _T. D. Noe_, May 29 2012 *)
%Y A005118 Cf. A003121, A018241, A057863, A246865, A289778.
%K A005118 nonn,easy,nice
%O A005118 0,4
%A A005118 _N. J. A. Sloane_
%E A005118 Citation corrected by _Matthew J. Samuel_, Feb 01 2011