

A025266


a(n) = a(1)*a(n1) + a(2)*a(n2) + ...+ a(n1)*a(1) for n >= 4.


12



1, 1, 0, 1, 2, 6, 16, 45, 126, 358, 1024, 2954, 8580, 25084, 73760, 218045, 647670, 1932230, 5787520, 17398270, 52476700, 158765300, 481690080, 1465239250, 4467799212, 13653601116, 41812009216, 128290240180, 394338641416, 1214165174712
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

a(n+2)=number of Motzkin (2n)paths whose longest plateau is of length n. A plateau is a sequence of contiguous flatsteps that is either the entire path or is of length >=1 and preceded by an up step and followed by a down step. Example: for n=3; a(5) counts UFFFDF and FUFFFD.  David Callan, Jul 15 2004
a(n) is the number of Motzkin paths of length n2 having no (1,0)steps at levels 0,2,4,... and having (1,0)steps of two colors at levels 1,3,5,... . Example: a(7)=16 because, denoting U=(1,1), D=(1,1), and H=(1,0), we have 2 paths of shape UDUHD, 2 paths of shape UHDUD, 2^3 = 8 paths of shape UHHHD, 2 paths of shape UHUDD, and 2 paths of shape UUDHD.  Emeric Deutsch, May 02 2011


LINKS

Table of n, a(n) for n=1..30.
Filippo Disanto, The size of the biggest Caterpillar subtree in binary rooted planar trees, arXiv preprint arXiv:1202.5668 [math.CO], 20122013.
Filippo Disanto and Thomas Wiehe, Some instances of a subpermutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 20122014.
Filippo Disanto, Unbalanced subtrees in binary rooted ordered and unordered trees, SÃ©minaire Lotharingien de Combinatoire, 68 (2013), Article B68b.
F. Disanto and T. Wiehe, On the subpermutations of pattern avoiding permutations, Discrete Math., 337 (2014), 127141.


FORMULA

G.f.: (1sqrt(14*x+8*x^3))/2.  Michael Somos, Jun 08 2000
Recurrence: n*a(n) = 2*(2*n3)*a(n1)  4*(2*n9)*a(n3).  Vaclav Kotesovec, Jan 25 2015


MATHEMATICA

nmax = 30; aa = ConstantArray[0, nmax]; aa[[1]] = 1; aa[[2]] = 1; aa[[3]] = 0; Do[aa[[n]] = Sum[aa[[k]] * aa[[nk]], {k, 1, n1}], {n, 4, nmax}]; aa (* Vaclav Kotesovec, Jan 25 2015 *)


PROG

(PARI) a(n)=polcoeff((1sqrt(14*x+8*x^3+x*O(x^n)))/2, n)


CROSSREFS

Cf. A025264.
Sequence in context: A026163 A005717 A333106 * A074403 A337318 A333070
Adjacent sequences: A025263 A025264 A025265 * A025267 A025268 A025269


KEYWORD

nonn


AUTHOR

Clark Kimberling


STATUS

approved



