|
| |
|
|
A025266
|
|
a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-1)*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 n-2 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], 2012-2013.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012-2014.
Filippo Disanto, Unbalanced subtrees in binary rooted ordered and un-ordered trees, Séminaire Lotharingien de Combinatoire, 68 (2013), Article B68b.
F. Disanto and T. Wiehe, On the sub-permutations of pattern avoiding permutations, Discrete Math., 337 (2014), 127-141.
|
|
|
FORMULA
|
G.f.: (1-sqrt(1-4*x+8*x^3))/2. - Michael Somos, Jun 08 2000
Recurrence: n*a(n) = 2*(2*n-3)*a(n-1) - 4*(2*n-9)*a(n-3). - 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[[n-k]], {k, 1, n-1}], {n, 4, nmax}]; aa (* Vaclav Kotesovec, Jan 25 2015 *)
|
|
|
PROG
|
(PARI) a(n)=polcoeff((1-sqrt(1-4*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
|
| |
|
|
