A193629 -id:A193629 - cp's OEIS frontend

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

1, 1, 1, 2, 16, 768, 292864, 1100742656, 48608795688960, 29258366996258488320, 273035280663535522487992320, 44261486084874072183645699204710400, 138018895500079485095943559213817088756940800

Offset: 0

N. J. A. Sloane

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
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

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).

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.
Joerg Arndt, The a(4)=16 Young tableaux of shape [3, 2, 1].
Sara C. Billey and Peter R. W. McNamara, The contributions of Stanley to the fabric of symmetric and quasisymmetric functions, arXiv preprint, 2015.
Tobias Boege, Alessio D'Alì, Thomas Kahle, Bernd Sturmfels, The Geometry of Gaussoids, arXiv:1710.07175 [math.CO], 2017.
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, and N. J. Fisch, Maximal energy extraction under discrete diffusive exchange, arXiv preprint arXiv:1508.03499 [physics.plasm-ph], 2015.
H. Hiller, Combinatorics and intersection of Schubert varieties, Comment. Math. Helv. 57 (1982), 41-59.
D. Kim, Finding k Shortest Paths in Cayley Graphs of Finite Groups, Graphs and Combinatorics 40, 120 (2024). See Formula at p. 13.
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]
Joshua Maglione and Christopher Voll, Hall-Littlewood polynomials, affine Schubert series, and lattice enumeration, arXiv:2410.08075 [math.CO], 2024. See pp. 34, 39.
R. P. Stanley, A combinatorial miscellany
R. P. Stanley, Ordering events in Minkowski space, arXiv:math/0501256 [math.CO], 2005.
R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

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

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

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

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

Citation corrected by Matthew J. Samuel, Feb 01 2011

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

Original entry on oeis.org

1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440

Offset: 0

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008

nonn

For each n, each vertex in the Hasse diagram of the poset corresponds to a Dyck path of size n. The chain polynomial, C(P,t)=(1 + sum_k(c_k*t^(k+1)), gives the breakdown of this sequence by number of vertices in the chain. The 1 in front of the sum in this equation denotes the empty chain. The coefficient, c_k, gives the number of chains of length k and the exponent, (k+1), indicates the number of vertices in the chain. Here are the chain polynomials corresponding to this sequence:
n=0 1
n=1 1 + t
n=2 1 + 2t + t^2
n=3 1 + 5t + 9t^2 + 7t^3 + 2t^4
n=4 1 + 14t + 70t^2 + 176 t^3+249t^4 + 202t^5 + 88 t^6 + 16 t^7
n=5 1 + 42t + 552t^2 + 3573t^3 + 13609t^4+ 33260 t^5 + 54430t^6 + 60517t^7 + 45248t^8 + 21824t^9 + 6144t^(10) + 768t^(11)
Note that for each n, the coefficient of t is equal to the Catalan number, C_n. It is well-known that the number of Dyck paths in D_n is given by C_n (A000108). The coefficient in front of the largest power of t gives the number of maximal (and also maximum) chains (A005118).

			a(3) = 24 since in D_3 there are 2 chains of length 3 (i.e., on 4 vertices in the Hasse diagram), 7 chains of length 2 (on 3 vertices), 9 chains of length 1 (on 2 vertices), 5 chains of length 0 (on 1 vertex) and the empty chain: 2 + 7 + 9 + 5 + 1 = 24 chains.

R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Cf. A143673, A143674, A193629. Chains on one vertex: A000108. Number of maximal chains: A005118.

d:= proc(x, y, l) option remember;
      `if`(x=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)])
    end:
le:= proc(l1, l2) local i;
       for i to nops(l1) do if l1[i]>l2[i] then return false fi od;
       true
     end:
a:= proc(n) option remember; local l, m, g;
      if n=0 then return 1 fi;
      l:= d(n, n, []); m:= nops(l);
      g:= proc(t) option remember;
            1 +add(`if`(le(l[d], l[t]), g(d), 0), d=1..t-1);
          end;
      1+ add(g(h), h=1..m)
    end:
seq(a(n), n=0..7);  # Alois P. Heinz, Jul 26 2011

a(n) = 1 + Sum_{i,j in {1..C(n)}} (2*delta - zeta)^(-1)[i,j] where delta is the identity matrix and the zeta matrix is defined: zeta[a,b] = 1 if a<=b in D_n and 0 otherwise.

a(6)-a(11), from Alois P. Heinz, Jul 26 2011, Aug 01 2011

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions