cp's OEIS Frontend

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.

%I A029847 #30 Jul 08 2025 19:23:01
%S A029847 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,
%T A029847 11234,4887,321,1,1,769,23151,106439,106439,23151,769,1,1,1793,101488,
%U A029847 856031,1679494,856031,101488,1793,1,1,4097,420512,6137832,21442606,21442606,6137832,420512,4097,1
%N 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.
%C A029847 For precise definition see Knuth (1997).
%C A029847 Named after the American mathematicians Ira Martin Gessel (b. 1951) and Richard Peter Stanley (b. 1944). - _Amiram Eldar_, Jun 11 2021
%H A029847 Alois P. Heinz, <a href="/A029847/b029847.txt">Rows n = 0..141, flattened</a>
%H A029847 Donald E. Knuth, <a href="/A323841/a323841.pdf">Letter to Daniel Ullman and others</a>, Apr 29 1997. [Annotated scanned copy, with permission]
%H A029847 Alexander Postnikov, <a href="https://doi.org/10.1006/jcta.1996.2735">Intransitive Trees</a>, J. Combin. Theory Ser. A, Vol. 79, No. 2 (1997), pp. 360-366.
%e A029847 Triangle begins:
%e A029847   1;
%e A029847   .   1;
%e A029847   .   1,   1;
%e A029847   .   1,   5,   1;
%e A029847   .   1,  17,  17,   1;
%e A029847   .   1,  49, 146,  49,   1;
%e A029847   .   1, 129, 922, 922, 129, 1;
%e A029847   .   ...
%p A029847 f:= proc(n,k) option remember; `if`(k<0, 0, `if`(n=0
%p A029847       and k=0, 1, f(n-1,k-1)+add(add(binomial(n-1, l)
%p A029847       *s*f(l,s)*f(n-l-1,k-s), s=1..l), l=1..n-1)))
%p A029847     end:
%p A029847 seq(seq(f(n, k), k=min(n, 1)..n), n=0..10); # _Alois P. Heinz_, Sep 24 2019
%t A029847 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}]]];
%t A029847 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_ *)
%Y A029847 Row sums give A007889.
%K A029847 nonn,tabf,easy
%O A029847 0,6
%A A029847 _N. J. A. Sloane_
%E A029847 More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 23 2003