A111169 Number of top simplices in a minimal triangulation of the permutohedron.

1, 1, 4, 34, 488, 10512, 316224, 12649104, 649094752, 41568338240, 3249938294656, 304670810708736, 33736950933298688, 4356802177994094080, 649031480783423250432, 110477935456564190447616, 21310050396755400705088512, 4623833701942527407032074240

Offset

0,3

Comments

The analogous sequence with associahedron in place of permutohedron is (n+1)^{n-1}.

This also counts maximal chains in the shard intersection orders of type A, see Theorem 1.3 in Reading reference. - F. Chapoton, Apr 29 2015

The ordinary generating series may be Gevrey of order 2, i.e., the coefficients may be bounded by A*B^n*(n!)^2 for some constants A and B. - F. Chapoton, Jul 07 2023

Links

M. F. Hasler, Table of n, a(n) for n = 0..100

Jean-Louis Loday, More information

Jean-Louis Loday, Parking functions and triangulation of the associahedron, arXiv:math/0510380 [math.AT], 2005.

N. Reading, Noncrossing partitions and the shard intersection order, arXiv:0909.3288 [math.CO], 2009.

N. Reading, Noncrossing partitions and the shard intersection order, J. Algebraic Combin. 33 (2011), no. 4.

Formula

a(n) = Sum_{m=0..n-1} (binomial(n+1, m+1) - 1)*binomial(n-1, m)*a(m)*a(n-m-1). - Robert G. Wilson v, Oct 31 2005

Maple

function y=binom(n, p); y=1; for j = 0 : p-1; y=y*(n-j); end; for j = 1 : p; y=y/j; end; format long; nmax = 14; mm=nmax+1; zp=zeros(mm, 1); zp(1:1) = 1; for n = 1 : nmax; z=0; for p = 0 : n-1; z=z+ (binom(n+1, p+1)-1) * binom(n-1, p) * zp(p+1:p+1) * zp(n-p:n-p); end; zp(n+1:n+1)=z; z; end; n, z

Mathematica

f[0] = 1; f[n_] := Sum[(Binomial[n + 1, m + 1] - 1)Binomial[n - 1, m]f[m]f[n - m - 1], {m, 0, n - 1}]; Table[f[n], {n, 0, 16}] (* Robert G. Wilson v, Oct 31 2005 *)

Prog

(PARI) a111169=[1]; A111169(n)={n<3&&return(n^n); global(a111169); while(n>m=#a111169, a111169=concat(a111169, sum(k=1, m-1, (binomial(m+2, k+1)-1)*binomial(m, k)*a111169[k]*a111169[m-k], 2*(m+1)*a111169[m]))); a111169[n]} \\ M. F. Hasler, May 02 2015
(Sage)
@cached_function
def a(n):
    if n == 0:
        return 1
    return sum((binomial(n + 1, m + 1) - 1) * binomial(n - 1, m)
               * a(m) * a(n - m - 1) for m in range(n))
# F. Chapoton, Jul 07 2023

Crossrefs

Sequence in context: A156325 A248654 A336495 * A274244 A002105 A198717

Adjacent sequences: A111166 A111167 A111168 * A111170 A111171 A111172

Keyword

easy,nonn

Author

Jean-Louis Loday (loday(AT)math.u-strasbg.fr), Oct 21 2005

Extensions

More terms from Robert G. Wilson v, Oct 31 2005

Status

approved