A082680 Triangle read by rows: T(n,k) is the number of 2-stack sortable n-permutations with k runs.

1, 1, 1, 1, 4, 1, 1, 10, 10, 1, 1, 20, 49, 20, 1, 1, 35, 168, 168, 35, 1, 1, 56, 462, 900, 462, 56, 1, 1, 84, 1092, 3630, 3630, 1092, 84, 1, 1, 120, 2310, 12012, 20449, 12012, 2310, 120, 1, 1, 165, 4488, 34320, 91091, 91091, 34320, 4488, 165, 1, 1, 220, 8151, 87516, 340340, 529984, 340340, 87516, 8151, 220, 1

Offset: 1

Author

Ralf Stephan, May 19 2003

Keywords

• nonn
• tabl
• easy

Comments

Number of beta(1,0)-trees on n+1 nodes with k leaves.

Row sums are given by A000139. - F. Chapoton, Nov 17 2015

T(n,k) is the number of rooted non-separable planar maps with n+1 edges, k+1 faces and n+2-k vertices. - Andrew Howroyd, Mar 29 2021

Examples

			Triangle starts:
  1;
  1,  1;
  1,  4,    1;
  1, 10,   10,    1;
  1, 20,   49,   20,    1;
  1, 35,  168,  168,   35,    1;
  1, 56,  462,  900,  462,   56,  1;
  1, 84, 1092, 3630, 3630, 1092, 84, 1;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
• M. Bona, 2-stack sortable permutations with a given number of runs, arXiv:math/9705220 [math.CO], 1997.
• Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, Refined product formulas for Tamari intervals, arXiv:2303.10986 [math.CO], 2023.
• Enrica Duchi, Veronica Guerrini, Simone Rinaldi, and Gilles Schaeffer, Fighting Fish: enumerative properties, arXiv:1611.04625 [math.CO], 2016.

Crossrefs

Cf. A000292 (2nd column), A051947 (3rd column).

Cf. A000139 (row sums).

Similar to A008292 and A001263.

Programs

Mathematica

Table[(n+k-1)!(2n-k)!/k!/(n+1-k)!/(2k-1)!/(2n-2k+1)!,{n,10},{k,n}]//Flatten (* Harvey P. Dale, Jun 10 2020 *)

PARI

T(n, k) = (n+k-1)!*(2*n-k)!/k!/(n+1-k)!/(2*k-1)!/(2*n-2*k+1)! \\ Andrew Howroyd, Mar 29 2021

Formula

T(n, k) = (n+k-1)!*(2*n-k)!/(k!*(n+1-k)!*(2*k-1)!*(2*n-2*k+1)!).

Extensions

Terms a(52) and beyond from Andrew Howroyd, Mar 29 2021