A029847 Gessel-Stanley triangle read by rows: triangle of coefficients of polynomials arising in connection with enumeration of intransitive trees by number of nodes and number of right nodes.

1, 1, 1, 1, 1, 5, 1, 1, 17, 17, 1, 1, 49, 146, 49, 1, 1, 129, 922, 922, 129, 1, 1, 321, 4887, 11234, 4887, 321, 1, 1, 769, 23151, 106439, 106439, 23151, 769, 1, 1, 1793, 101488, 856031, 1679494, 856031, 101488, 1793, 1, 1, 4097, 420512, 6137832, 21442606, 21442606, 6137832, 420512, 4097, 1

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• tabf
• easy

Comments

For precise definition see Knuth (1997).

Named after the American mathematicians Ira Martin Gessel (b. 1951) and Richard Peter Stanley (b. 1944). - Amiram Eldar, Jun 11 2021

Examples

			Triangle begins:
  1;
  .   1;
  .   1,   1;
  .   1,   5,   1;
  .   1,  17,  17,   1;
  .   1,  49, 146,  49,   1;
  .   1, 129, 922, 922, 129, 1;
  .   ...
		

Links

• Alois P. Heinz, Rows n = 0..141, flattened
• Donald E. Knuth, Letter to Daniel Ullman and others, Apr 29 1997. [Annotated scanned copy, with permission]
• Alexander Postnikov, Intransitive Trees, J. Combin. Theory Ser. A, Vol. 79, No. 2 (1997), pp. 360-366.

Crossrefs

Row sums give A007889.

Programs

Maple

f:= proc(n,k) option remember; `if`(k<0, 0, `if`(n=0
      and k=0, 1, f(n-1,k-1)+add(add(binomial(n-1, l)
      *s*f(l,s)*f(n-l-1,k-s), s=1..l), l=1..n-1)))
    end:
seq(seq(f(n, k), k=min(n, 1)..n), n=0..10); # Alois P. Heinz, Sep 24 2019

Mathematica

f[n_, k_] := f[n, k] = If[k<0, 0, If[n==0 && k==0, 1, f[n-1, k-1]+Sum[Sum[ Binomial[n-1, l]*s*f[l, s]*f[n-l-1, k-s], {s, 1, l}], {l, 1, n-1}]]];
Table[Table[f[n, k], {k, Min[n, 1], n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

Extensions

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 23 2003