|
|
A086615
|
|
Antidiagonal sums of triangle A086614.
|
|
18
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
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
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
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
|
|
EXAMPLE
|
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
|
|
MAPLE
|
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:
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|