A005118 -id:A005118 - cp's OEIS frontend

A193629 Triangle T(n,k), n>=0, 0<=k<=C(n,2), read by rows: T(n,k) = number of k-length chains in the poset of Dyck paths of semilength n ordered by inclusion.

1, 1, 2, 1, 5, 9, 7, 2, 14, 70, 176, 249, 202, 88, 16, 42, 552, 3573, 13609, 33260, 54430, 60517, 45248, 21824, 6144, 768, 132, 4587, 72490, 653521, 3785264, 15104787, 43358146, 91942710, 146186256, 175196202, 157630704, 104922224, 50152960, 16290560, 3221504

Offset: 0

Alois P. Heinz, Aug 01 2011

			Poset of Dyck paths of semilength n=3:
.
.      A       A:/\      B:
.      |        /  \      /\/\
.      B       /    \    /    \
.     / \
.    C   D     C:        D:        E:
.     \ /         /\      /\
.      E       /\/  \    /  \/\    /\/\/\
.
Chains of length k=0: A, B, C, D, E (5); k=1: A-B, A-C, A-D, A-E, B-C, B-D, B-E, C-E, D-E (9); k=2: A-B-C, A-B-D, A-B-E, A-C-E, A-D-E, B-C-E, B-D-E (7), k=3: A-B-C-E, A-B-D-E (2) => [5, 9, 7, 2].
Triangle begins:
:   1;
:   1;
:   2,    1;
:   5,    9,     7,      2;
:  14,   70,   176,    249,     202,       88,       16;
:  42,  552,  3573,  13609,   33260,    54430,    60517,    45248, ...
: 132, 4587, 72490, 653521, 3785264, 15104787, 43358146, 91942710, ...

Alois P. Heinz, Rows n = 0..11, flattened
J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Row sums give: A143672-A057427. Column k=0 gives: A000108. Last elements of rows give: A005118. Row lengths give: A000124(n-1). Cf. A193536.

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:
T:= proc(n) option remember; local h, l, m, g, r;
      l:= d(n, n, []); m:= nops(l);
      g:= proc(t) option remember; local r, d;
            r:= [1];
            for d to t-1 do if le(l[d], l[t]) then
              r:= zip((x, y)->x+y, r, [0, g(d)[]], 0)
            fi od; r
          end;
      r:= [];
      for h to m do
        r:= zip((x, y)->x+y, r, g(h), 0)
      od; r[]
    end:
seq(T(n), n=0..7);

A289778 Number T(n,k) of reduced decompositions for all permutations of [n] with exactly k inversions; triangle T(n,k), n>=0, 0<=k<=n*(n-1)/2, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 2, 1, 3, 6, 10, 14, 16, 16, 1, 4, 12, 30, 68, 132, 252, 412, 614, 768, 768, 1, 5, 20, 68, 210, 588, 1540, 3778, 8768, 19402, 40284, 78276, 137236, 219362, 292864, 292864, 1, 6, 30, 130, 512, 1864, 6340, 20472, 62770, 184748, 521272, 1428932

Offset: 0

Alois P. Heinz, Jul 12 2017

			Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  2,  2;
  1, 3,  6, 10, 14,  16,  16;
  1, 4, 12, 30, 68, 132, 252, 412, 614, 768, 768;
  ...

Alois P. Heinz, Rows n = 0..10, flattened
R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

Row sums give A246865.

Cf. A000217, A005118, A008302.

T(n,n*(n-1)/2) = A005118(n).

A246865 Total number of reduced decompositions for all permutations in S_n.

Original entry on oeis.org

1, 1, 2, 7, 66, 3061, 1095266, 3906746485, 165835140118904, 96867653699340061187, 883158060528372369857672080, 140546577721904223563711600192372503

Offset: 0

Sara Billey, Sep 05 2014

A decomposition of a permutation is a product of adjacent transpositions. A reduced decomposition is one of minimal length which is also the number of inversions of the permutation and there may be more than one reduced decomposition. The largest number (multiplicity) of reduced decompositions of a permutation in S_n is A005118(n) for the permutation which reverses the order of all elements and all of its reduced decompositions have length n(n-1)/2 which is the maximum number of inversions. - Michael Somos, Sep 07 2014

			a(4) = 66 is summarized in a table of multiplicity versus length:
length     =   0  1  2  3  4  5  6
multiplicity +---------------------+
       1     | 1  3  4  2  .  .  . | = 10   1*10 = 10
       2     | .  .  1  4  1  .  . | =  6   2*6  = 12
       3     | .  .  .  .  4  .  . | =  4   3*4  = 12
       5     | .  .  .  .  .  2  . | =  2   5*2  = 10
       6     | .  .  .  .  .  1  . | =  1   6*1  =  6
      16     | .  .  .  .  .  .  1 | =  1  16*1  = 16
             +---------------------+   --          --
               1  3  5  6  5  3  1   = 24   a(4) = 66.
- _Michael Somos_, Sep 07 2014

Bridget Eileen Tenner, Enumerating in Coxeter Groups (Survey), Advances in Mathematical Sciences, pp 75-82, Springer 2020.

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
M. J. Hay, J. Schiff, N. J. Fisch, Available free energy under local phase space diffusion, arXiv preprint arXiv:1604.08573, 2016
M. J. Hay, J. Schiff, N. J. Fisch, On extreme points of the diffusion polytope, Physica A 473 (2017) 225-236. doi:10.1016/j.physa.2017.01.038
R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., 5 (1984), 359-372.

Cf. A005118, A008302.

Row sums of A289778.

a(0)=1 prepended and a(7)-a(11) from Alois P. Heinz, Jul 10 2017

A166860 Number of saturated chains in the poset of Dyck paths ordered by inclusion.

Original entry on oeis.org

1, 1, 3, 16, 191, 9586, 3621062, 13539455808, 596242050871827, 358279069210950329112, 3339667708892016201497713938, 540966002417189385158099747634890008, 1685909333511453301447626182908204645875878754, 110859993072493750180447848516163015805399916591746521402

Offset: 0

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Oct 21 2009

nonn

Breakdown by length of chain:
n: chains
0:  1;
1:  1;
2:  2,  1;
3:  5,  5,   4,   2;
4: 14, 21,  30,  38,  40,  32,   16;
5: 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768;
Note that for each n, there are C_n chains of length 0 (A000108) and the number of maximal chains is A005118.

			For n=3, the Hasse diagram consists of 5 vertices corresponding to the 5 Dyck paths. With area as the rank function, we have one vertex of rank 0, two of rank 1, one of rank 2 and one of rank 3.
There are 16 saturated chains with 5 chains on one vertex, 5 chains on two vertices, 4 chains on three vertices and the 2 maximal chains on four vertices.

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. A143672, A000108, A005118.

# E.g., for n=3, using John Stembridge's Symmetric Functions package:
withSF();
AA:=add(s[op(la)],la=subPar([2,1]));tos(skew(AA,AA));
scalar(%, add(h1^r,r=0..4));
# second Maple program:
d:= proc(x, y, l) option remember;
      `if`(x<=1, [[y, l[]]], [seq(d(x-1, i, [y, l[]])[], i=x-1..y)])
    end:
a:= proc(n) option remember; local g;
      g:= proc(l) option remember;
            1 +add(`if`(l[i]>i and (i=1 or l[i-1]Alois P. Heinz, Jul 27 2011

d[x_, y_, l_List] := d[x, y, l] = If[x <= 1, {Join[{y}, l]}, Flatten[Table[d[x-1, i, Join[{y}, l]], {i, x-1, y}], 1]]; a[n_] := a[n] = Module[{g}, g[l_List] := g[l] = 1 + Sum[If[l[[i]] > i && (i == 1 || l[[i-1]] < l[[i]]), g[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, n-1}]; Sum[g[j], {j, d[n, n, {}]}]]; Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Jul 06 2015, after Alois P. Heinz *)

1) For D_i, D_j in D_n, the number of saturated chains = Sum_{D_i<=D_j} (number of standard Young tableaux for D_j\D_i partition).

2) Define zeta(x,y)=1 if x=y or if y immediately covers x in the poset and delta is the identity function. Then the number of saturated chains = sum of entries in the (2*delta - zeta)^(-1) matrix.

a(9)-a(13) from Alois P. Heinz, Jul 27 2011

A248330 The product of the first n Catalan numbers and the number of standard Young tableaux of shape(1,2,...,n).

Original entry on oeis.org

1, 1, 4, 160, 107520, 1722040320, 854352419880960, 16185399027773630054400, 13931397052191274338996977664000, 632089112919018408339999461491467091968000, 1721041721929360607907210006858724622834371563356160000

Offset: 0

Alejandro H. Morales, Oct 04 2014

The volume of a certain polytope (the Tesler polytope) whose lattice points are Tesler matrices (A008608), and with (n+1)! integral vertices (permutation Tesler matrices).

This is also the iterated constant term of the rational function (x1+x2+...+xn+x(n+1))^binomial(n+1,2)*product_{1<=i

K. Mészáros, A.H. Morales, B. Rhoades, The polytope of Tesler matrices, ArXiv:1409.8566, 2014.

Cf. A000108, A003046, A005118, A008608.

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

a(n) = A005118(n+1) * A003046(n).

a(n) = A005118(n+1) * Product_{k=0..n} A000108(k).

A278289 Number of standard Young tableaux of skew shape (2n-1,2n-2,...,2,1)/(n-1,n-2,..,2,1).

Original entry on oeis.org

1, 1, 16, 101376, 1190156828672, 68978321274090930831360, 40824193474825703180733027309531955200, 440873872874088459550341319780612789503586208384381091840, 140992383930585613207663170866505518985873138480180692888967131590224605582721024

Offset: 0

Alejandro H. Morales, Nov 16 2016

nonn

			For n = 3 there are a(2) = 16 standard tableaux of shape (3,2,1)/(1).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Corollary 7.16.3.

Alejandro H. Morales, Table of n, a(n) for n = 0..22
A. H. Morales, I. Pak and G. Panova, Asymptotics of the number of standard Young tableaux of skew shape, arXiv:1610.07561 [math.CO], 2016; European Journal of Combinatorics, Vol 70 (2018).
A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications, arXiv:1610.04744 [math.CO], 2016; SIAM Journal of Discrete Mathematics, Vol 31 (2017).
A. H. Morales, I. Pak and M. Tassy, Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings, arXiv:1805.00992 [math.CO], 2018.
A. H. Morales and D. G. Zhu, On the Okounkov--Olshanski formula for standard tableaux of skew shapes, arXiv:2007.05006 [math.CO], 2020.
H. Naruse, Schubert calculus and hook formula, talk slides at 73rd Sém. Lothar. Combin., Strobl, Austria, 2014.
I. Pak, Skew shape asymptotics, a case-based introduction, 2020.
Jay Pantone, File with list of n, a(n) for n = 0..438 (warning: file size is 100MB)

Cf. A005118; for even n the number of terms in Naruse hook length formula is given by A181119 (Corollary 8.1 in arXiv:1610.04744).

a:=proc(k) local lam,mu;
lam:=[seq(2*k-i,i=1..2*k-1)];
mu:=[seq(k-i,i=1..k-1),seq(0,i=1..k)];
factorial(binomial(2*k,2)-binomial(k,2))*LinearAlgebra:-Determinant(Matrix(2*k-1, 2*k-1,(i,j)->`if`(lam[i]-mu[j]-i+j<0,0,1/factorial(lam[i]-mu[j]-i+j))));
end proc:
seq(a(n),n=0..5);

a(n) = ((3*n^2-n)/2)!*det(1/(lambda[i]-mu[j]-i+j)!), where lambda = (2*n-1,2*n-2,...,1) and mu = (n-1,n-2,...,1,0...,0).

There is a constant c such that log(a(k)) = n*log(n)/2 + c*n + o(n) where n = k*(3*k-1)/2 goes to infinity and -0.2368 <= c <= -0.1648. [updated by Alejandro H. Morales, Aug 29 2020]

A291908 Number of standard Young tableaux of skew shape lambda/mu where lambda is the staircase (4n-1,4n-2,...,2,1) and mu is the square n^n.

Original entry on oeis.org

1, 16, 4362327818240, 19265181532031090042534736325278852710400, 830325323503973129435791248069702287019820905338483131168940909920954227594481411031040

Offset: 0

Alejandro H. Morales, Sep 05 2017

nonn

The number of standard Young tableaux of a fixed skew shape has a determinantal formula, the Jacobi-Trudi formula. It is rare when a family of skew shapes has a product formula for the number of standard Young tableaux. This product formula has independently been proved using P-Schur functions (by DeWitt) and using the Naruse hook-length formula for skew shapes (by Morales, Pak and Panova).

			a(1)=16 since there are 16 standard Young tableaux of skew shape 321/1 since this is the same as the number of standard Young tableaux of straight shape 321 given by the hook-length formula: 16 = 6!/(3^2*5).

E. A. DeWitt, Identities Relating Schur s-Functions and Q-Functions, Ph.D. thesis, University of Michigan, 2012, 73 pp.
A. H. Morales, I. Pak, G. Panova, Hook formulas for skew shapes III. Multivariate and product formulas, arXiv:1707.00931 [math.CO], 2017.

Cf. A000178, A057863, A008793, A291871, A000085, A061343, A005118.

b:=n->mul(factorial(i),i=1..n-1):
c:=n->mul(doublefactorial(2*i-1),i=1..n-1):
a:=n->factorial(binomial(4*n,2)-n^2)*b(n)^3*b(3*n)*c(n)*c(3*n)/(b(2*n)^3*c(2*n)^2*c(4*n)):
seq(a(n),n=0..9);

def b(n): return mul([factorial(i) for i in range(1,n)])
def d(n): return factorial(n+1)/(2^((n+1)/2)*factorial((n+1)/2))
def c(n): return mul([d(2*i-1) for i in range(1,n)])
def a(n):
    return factorial(binomial(4*n,2)-n^2)*b(n)^3*b(3*n)*c(n)*c(3*n)/(b(2*n)^3*c(2*n)^2*c(4*n))
[a(n) for n in range(10)]

a(n) = (binomial(4*n,2)-n^2)!*b(n)^3*b(3*n)*c(n)*c(3*n)/(b(2*n)^3*c(2*n)^2*c(4*n)) where b(n) = 1!*2!*...*(n-1)! is the superfactorial A000178(n-1), and c(n) = 1!!*3!!*...*(2*n-3)!! is super doublefactorial A057863(n-1).

a(n) ~ sqrt(Pi) * 3^(9*n^2 - 3*n/2 - 1/24) * 7^(7*n^2 - 2*n + 1/2) * exp(7*n^2/2 - 2*n + 23/56) * n^(7*n^2 - 2*n + 7/8) / (A^(3/2) * 2^(33*n^2 - 6*n - 7/8)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, Apr 08 2021

A092238 Number of ways to write the permutation n,n-1,...,1 of 1,2,...,n as a product of n(n-1)/2 transpositions, where each transposition of 1,2,...,n occurs exactly once.

Original entry on oeis.org

1, 1, 1, 2, 64, 59712, 3580519776

Offset: 0

Richard Stanley, Feb 19 2004

If we impose the additional condition on the product t_1 t_2 ... of transpositions that the number of inversions increases by one each time we multiply by a t_i, then the number of ways is given by A005118.

			a(3)=2 because 321 = (1,2)(1,3)(2,3) = (2,3)(1,3)(1,2).

Cf. A005118.

a(0)=1 prepended and a(6) added by Alois P. Heinz, Jul 12 2017

Previous Showing 11-18 of 18 results.

cp's OEIS Frontend

A193629 Triangle T(n,k), n>=0, 0<=k<=C(n,2), read by rows: T(n,k) = number of k-length chains in the poset of Dyck paths of semilength n ordered by inclusion.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A289778 Number T(n,k) of reduced decompositions for all permutations of [n] with exactly k inversions; triangle T(n,k), n>=0, 0<=k<=n*(n-1)/2, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A246865 Total number of reduced decompositions for all permutations in S_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A166860 Number of saturated chains in the poset of Dyck paths ordered by inclusion.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A248330 The product of the first n Catalan numbers and the number of standard Young tableaux of shape(1,2,...,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A278289 Number of standard Young tableaux of skew shape (2n-1,2n-2,...,2,1)/(n-1,n-2,..,2,1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A291908 Number of standard Young tableaux of skew shape lambda/mu where lambda is the staircase (4*n-1,4*n-2,...,2,1) and mu is the square n^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Sage

Formula

A092238 Number of ways to write the permutation n,n-1,...,1 of 1,2,...,n as a product of n(n-1)/2 transpositions, where each transposition of 1,2,...,n occurs exactly once.

Views

Author

Keywords

Comments

A291908 Number of standard Young tableaux of skew shape lambda/mu where lambda is the staircase (4n-1,4n-2,...,2,1) and mu is the square n^n.