login
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.
2
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,6
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
LINKS
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.
EXAMPLE
Triangle begins:
1;
. 1;
. 1, 1;
. 1, 5, 1;
. 1, 17, 17, 1;
. 1, 49, 146, 49, 1;
. 1, 129, 922, 922, 129, 1;
. ...
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 *)
CROSSREFS
Row sums give A007889.
Sequence in context: A157637 A157181 A347974 * A154334 A178346 A168551
KEYWORD
nonn,tabf,easy
AUTHOR
EXTENSIONS
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 23 2003
STATUS
approved