login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

REFERENCES

Filippo Disanto, Unbalanced subtrees in binary rooted ordered and un-ordered trees, Seminaire 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.

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, 2012.

Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908, 2012.

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: A126285 A026163 A005717 * A074403 A290953 A151391

Adjacent sequences:  A025263 A025264 A025265 * A025267 A025268 A025269

KEYWORD

nonn

AUTHOR

Clark Kimberling

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 21:26 EST 2018. Contains 299469 sequences. (Running on oeis4.)