A025266 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-1)*a(1) for n >= 4.

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

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

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.
• Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See pp. 19-20.
• 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.

Crossrefs

Cf. A025264.

Programs

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 *)

PARI

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

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