login
The OEIS is supported by the many generous donors 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
a(n+2) is the total number of rooted plane trees with integer compositions of size at least 1 labeling all the nodes but the root, with total size n >= 0. The total size is the number of edges in the tree plus the sum of the sizes of the compositions in the nodes. Examples: a(2)=1 because there is only one element of size 0 and consists of the root with no edges; a(3)=0 because to have size one the tree would consist of the root and one single descendant, but then any composition labeling it would increase the total size to at least two; a(4)=1 because there is only one element of total size 2 and it consists of the root and one descendant labeled by the integer composition 1=1; a(5)=2 because now there are two elements, again they both consist of a root with one descendant, but now the label is either 2=2 or 2=1+1. - Ricardo Gómez Aíza, Feb 25 2024
LINKS
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.
Filippo Disanto and Thomas Wiehe, On the sub-permutations of pattern avoiding permutations, Discrete Math., 337 (2014), 127-141.
Tom Roberts and Thomas Prellberg, Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 21.
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
a(n) ~ sqrt(3*sqrt(5)-5)/(4*sqrt((1+sqrt(5))*Pi*n^3))*(4/(sqrt(5)-1))^n. - Ricardo Gómez Aíza, Feb 25 2024
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
KEYWORD
nonn
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)