A316773 Triangle read by rows: T(n,m) = Sum_{k=m+1..n} (n-1)!/(k-1)!*binomial(2*n-k-1, n-1)*E(k,m) where E(n,m) is Euler's triangle A173018, T(0,0) = 1, n >= m >= 0.

1, 1, 0, 3, 1, 0, 19, 10, 1, 0, 193, 119, 23, 1, 0, 2721, 1806, 466, 46, 1, 0, 49171, 34017, 10262, 1502, 87, 1, 0, 1084483, 770274, 255795, 47020, 4425, 162, 1, 0, 28245729, 20429551, 7235853, 1539939, 193699, 12525, 303, 1, 0, 848456353, 621858526, 230629024, 54314242, 8273758, 755170, 34912, 574, 1, 0

Offset

0,4

Comments

T(n,m) is the number of labeled binary trees of size n with m ascents on the left branch.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened)

Yuriy Shablya, Dmitry Kruchinin, Vladimir Kruchinin, Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application, Mathematics (2020) Vol. 8, No. 6, 962.

Formula

E.g.f.: Sum_{n >= m >= 0} T(n, m)/n! * x^n * y^m = E(C(x),y) = (y-1)/(y-exp(C(x)*(y-1))), where E(x,y) is an e.g.f. for Euler's triangle A173018.

T(n,m) = Sum_{k = m+1..n} C(n,k)*E(k,m)*P(n,n-k), T(0,0)=1, where C(n,m) is the transposed Catalan's triangle A033184, E(n,m) is Euler's triangle A173018, and P(n,m) is the number of k-permutations of n A008279.

Example

Triangle begins:
--------------------------------------------------------------------------
n\k|       0         1         2        3       4      5     6   7   8   9
------+-------------------------------------------------------------------
0 |         1
1 |         1         0
2 |         3         1         0
3 |        19        10         1        0
4 |       193       119        23        1       0
5 |      2721      1806       466       46       1      0
6 |     49171     34017     10262     1502      87      1     0
7 |   1084483    770274    255795    47020    4425    162     1   0
8 |  28245729  20429551   7235853  1539939  193699  12525   303   1  0
9 | 848456353 621858526 230629024 54314242 8273758 755170 34912 574  1  0

Maple

T := (n, m) -> `if`(n=0, 1, add((n-1)!/(k-1)!*binomial(2*n-k-1, n-1)*
combinat:-eulerian1(k, m), k = m+1..n)):
for n from 0 to 6 do seq(T(n, k), k=0..n) od; # Peter Luschny, Sep 04 2020

Mathematica

Table[Boole[n == 0] + Sum[(n - 1)!/(k - 1)!*Binomial[2 n - k - 1, n - 1]*Sum[(-1)^j*(m + 1 - j)^k*Binomial[k + 1, j], {j, 0, m}], {k, m + 1, n}], {n, 0, 8}, {m, 0, n}] // Flatten (* Michael De Vlieger, Sep 04 2020 *)

Prog

(Maxima)
T(n, m):=if m>n then 0 else if n=0 then 1 else sum((n-1)!/(k-1)!*binomial(2*n-k-1, n-1)*sum((-1)^j*(m+1-j)^k*binomial(k+1, j), j, 0, m), k, m+1, n);

Crossrefs

Cf. A033184, A008279, A173018.

Sequence in context: A147723 A110518 A246049 * A006837 A158782 A187558

Adjacent sequences: A316770 A316771 A316772 * A316774 A316775 A316776

Keyword

nonn,tabl

Author

Yuriy Shablya, Sep 13 2018

Status

approved