A086615 Antidiagonal sums of triangle A086614.

1, 2, 4, 8, 17, 38, 89, 216, 539, 1374, 3562, 9360, 24871, 66706, 180340, 490912, 1344379, 3701158, 10237540, 28436824, 79288843, 221836402, 622599625, 1752360040, 4945087837, 13988490338, 39658308814, 112666081616

Offset: 0

Author

Paul D. Hanna, Jul 24 2003

Keywords

• nonn

Comments

Partial sums of the Motzkin sequence (A001006). - Emeric Deutsch, Jul 12 2004

a(n) is the number of distinct ordered trees obtained by branch-reducing the ordered trees on n+1 edges. - David Callan, Oct 24 2004

a(n) is the number of consecutive horizontal steps at height 0 of all Motzkin paths from (0,0) to (n,0) starting with a horizontal step. - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007

This sequence (with offset 1 instead of 0) occurs in Section 7 of K. Grygiel, P. Lescanne (2015), see g.f. N. - N. J. A. Sloane, Nov 09 2015

Also number of plain (untyped) normal forms of lambda-terms (terms that cannot be further beta-reduced.) [Bendkowski et al., 2016]. - N. J. A. Sloane, Nov 22 2017

If interpreted with offset 2, the INVERT transform is A002026 with offset 1. - R. J. Mathar, Nov 02 2021

Examples

			a(0)=1, a(1)=2, a(2)=3+1=4, a(3)=4+4=8, a(4)=5+10+2=17, a(5)=6+20+12=38, are upward antidiagonal sums of triangle A086614:
{1},
{2,1},
{3,4,2},
{4,10,12,5},
{5,20,42,40,14},
{6,35,112,180,140,42}, ...
For example, with n=2, the 5 ordered trees (A000108) on 3 edges are
|...|..../\.../\.../|\..
|../.\..|......|........
|.......................
Suppressing nonroot vertices of outdegree 1 (branch-reducing) yields
|...|..../\.../\../|\..
.../.\.................
of which 4 are distinct. So a(2)=4.
a(4)=8 because we have HHHH, HHUD, HUDH, HUHD
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
• Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6
• Maciej Bendkowski, K. Grygiel, and P. Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682, 2016
• K. Grygiel and P. Lescanne, A natural counting of lambda terms, SOFSEM 2016. Preprint 2015

Crossrefs

Cf. A086614 (triangle), A086616 (row sums), A348869 (Seq. Transf.).

Cf. A001006.

Cf. A136788.

Programs

Maple

A086615 := proc(n)
    option remember;
    if n <= 3 then
        2^n;
    else
        3*(-n-1)*procname(n-1) +(-n+4)*procname(n-2) +3*(n-1)*procname(n-3) ;
        -%/(n+2) ;
    end if;
end proc:
seq(A086615(n),n=0..20) ; # R. J. Mathar, Nov 02 2021

Mathematica

CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(2*x-2*x^2)/x, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 13 2014 *)

Formula

G.f.: A(x) = 1/(1-x)^2 + x^2*A(x)^2.

a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+1, 2k+1)*binomial(2k, k)/(k+1). - Paul Barry, Nov 29 2004

a(n) = n + 1 + Sum_k a(k-1)*a(n-k-1), starting from a(n)=0 for n negative. - Henry Bottomley, Feb 22 2005

a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(j)*C(n-k, 2j). - Paul Barry, Aug 19 2005

From Paul Barry, May 31 2006: (Start)

G.f.: c(x^2/(1-x)^2)/(1-x)^2, c(x) the g.f. of A000108;

a(n) = Sum_{k=0..floor(n/2)} C(n+1,n-2k)*C(k). (End)

Binomial transform of doubled Catalan sequence 1,1,1,1,2,2,5,5,14,14,... - Paul Barry, Nov 17 2005

Row sums of Pascal-Catalan triangle A086617. - Paul Barry, Nov 17 2005

g(z) = (1-z-sqrt(1-2z-3z^2))/(2z-2z^2)/z - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007, corrected by Vaclav Kotesovec, Feb 13 2014

D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n+4)*a(n-2) +3*(n-1)*a(n-3)=0. - R. J. Mathar, Nov 30 2012

a(n) ~ 3^(n+5/2) / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014

Extensions

Edited by N. J. A. Sloane, Oct 16 2006