login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005118 Number of simple allowable sequences on 1..n containing the permutation 12...n.
(Formerly M2097)
18
1, 1, 1, 2, 16, 768, 292864, 1100742656, 48608795688960, 29258366996258488320, 273035280663535522487992320, 44261486084874072183645699204710400, 138018895500079485095943559213817088756940800 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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, when n=5 a(5)=768 and the shape of the tableau is xxxx / xxx / xx / x. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 04 2001

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

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

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

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

REFERENCES

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.

J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, CRC Press, 1997, p. 102.

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n = 0..40

Omer Angel, Alexander E. Holroyd, Dan Romik, and Balint Virag, Random Sorting Networks, arXiv preprint arXiv:0609538 [math.PR], 2006.

Sara C. Billey and Peter R. W. McNamara, The contributions of Stanley to the fabric of symmetric and quasisymmetric functions, arXiv preprint, 2015.

R. Davis and B. Sagan, Pattern-Avoiding Polytopes, 2016

FindStat - Combinatorial Statistic Finder, The number of ways to write a permutation as a minimal length product of simple transpositions

M. J. Hay, J. Schiff, N. J. Fisch, Maximal energy extraction under discrete diffusive exchange, arXiv preprint arXiv:1508.03499, 2015

H. Hiller, Combinatorics and intersection of Schubert varieties, Comment. Math. Helv. 57 (1982), 41-59.

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. [Annotated scanned copy]

R. P. Stanley, A combinatorial miscellany

R. P. Stanley, Ordering events in Minkowski space

R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

FORMULA

a(n) = C(n, 2)!/(1^{n-1} * 3^{n-2} *...* (2n-3)^1 ).

a(n) = (n*(n-1)/2)!/A057863(n-1) (n>=1). - Emeric Deutsch, May 21 2004

a(n) = A153452(A002110(n-1)). - Naohiro Nomoto, Jan 01 2009

From Alois P. Heinz, Nov 18 2012: (Start)

a(n+1) = A219272(A000217(n),n) = A219274(A000217(n),n) = A219311(A000217(n),n).

a(n) = A193536(n,A000217(n-1)) = A193629(n,A000217(n-1)). (End)

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

MAPLE

A005118 := proc(n) local i; binomial(n, 2)!/product( (2*i+1)^(n-i-1), i=0..n-2 ); end;

MATHEMATICA

Table[Binomial[n, 2]!/Product[(2*i + 1)^(n - i - 1), {i, 0, n - 2}], {n, 0, 10}] (* T. D. Noe, May 29 2012 *)

CROSSREFS

Cf. A003121, A018241, A057863, A246865, A289778.

Sequence in context: A128294 A278087 A015188 * A108400 A186002 A013029

Adjacent sequences:  A005115 A005116 A005117 * A005119 A005120 A005121

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Citation corrected by Matthew J. Samuel, Feb 01 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 17:56 EST 2017. Contains 294894 sequences.