A025266 - OEIS

%I #60 Mar 01 2024 10:30:31

%S 1,1,0,1,2,6,16,45,126,358,1024,2954,8580,25084,73760,218045,647670,

%T 1932230,5787520,17398270,52476700,158765300,481690080,1465239250,

%U 4467799212,13653601116,41812009216,128290240180,394338641416,1214165174712

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

%C 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

%C 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

%C 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

%H Filippo Disanto, <a href="http://arxiv.org/abs/1202.5668">The size of the biggest Caterpillar subtree in binary rooted planar trees</a>, arXiv preprint arXiv:1202.5668 [math.CO], 2012-2013.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1210.6908">Some instances of a sub-permutation problem on pattern avoiding permutations</a>, arXiv preprint arXiv:1210.6908 [math.CO], 2012-2014.

%H Filippo Disanto, <a href="http://www.kurims.kyoto-u.ac.jp/EMIS/journals/SLC/wpapers/s68disanto.html">Unbalanced subtrees in binary rooted ordered and un-ordered trees</a>, Séminaire Lotharingien de Combinatoire, 68 (2013), Article B68b.

%H Filippo Disanto and Thomas Wiehe, <a href="http://dx.doi.org/10.1016/j.disc.2014.06.028">On the sub-permutations of pattern avoiding permutations</a>, Discrete Math., 337 (2014), 127-141.

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See pp. 19-20.

%H Tom Roberts and Thomas Prellberg, <a href="https://arxiv.org/abs/2401.12201">Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling</a>, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 21.

%F G.f.: (1-sqrt(1-4*x+8*x^3))/2. - _Michael Somos_, Jun 08 2000

%F Recurrence: n*a(n) = 2*(2*n-3)*a(n-1) - 4*(2*n-9)*a(n-3). - _Vaclav Kotesovec_, Jan 25 2015

%F 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

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

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

%Y Cf. A025264.

%K nonn

%O 1,5

%A _Clark Kimberling_