|
| |
|
|
A025276
|
|
a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-1)*a(1) for n >= 5, with a(1) = 1, a(2) = a(3) = 0, a(4) = 1.
|
|
2
|
|
|
|
1, 0, 0, 1, 2, 4, 8, 17, 38, 88, 208, 498, 1204, 2936, 7216, 17861, 44486, 111408, 280352, 708526, 1797564, 4576472, 11688496, 29939786, 76894684, 197974480, 510864480, 1321031716, 3422685992, 8884010928, 23098674400, 60152509613, 156879556678
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Number of lattice paths from (0,0) to (n-4,0) that stay weakly in the first quadrant and such that each step is either U=(2,1), D=(2,-1), blue H=(1,0), or red h=(1,0) (n>=4). E.g., a(8)=17 because we have 16 horizontal paths of length 4 with all combinations of blue and red (1,0) steps and, in addition, UD. - Emeric Deutsch, Dec 23 2003
a(n+3) is the number of rooted plane 2-trees with nonempty integer compositions labeling all the nodes, including 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 integer compositions labeling all the nodes.
Examples: a(3)=0 because there are no elements of size zero; a(4)=1, a(5)=2, a(6)=4 and a(7)=8 because in each case, the elements are trees that consist of the root alone labeled with the compositions of 1, 2, 3 and 4, respectively; a(8)=17 because now we have 17 elements of size 5, the first 16 coming from the root alone labeled with the compositions of 5, plus the 2-tree that consists of the root with two descendants, with each of the three nodes labeled with the composition 1=1. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
Recurrence: n*a(n) = 2*(2*n-3)*a(n-1) - 4*(n-3)*a(n-2) + 4*(n-6)*a(n-4). - Vaclav Kotesovec, Jan 25 2015
a(n) ~ sqrt((9-5*sqrt(3))/(8*Pi*n^3))*(2/(sqrt(3)-1))^n. - Ricardo Gómez Aíza, Mar 01 2024
|
|
|
MATHEMATICA
|
nmax = 30; aa = ConstantArray[0, nmax]; aa[[1]] = 1; aa[[2]] = 0; aa[[3]] = 0; aa[[4]] = 1; Do[aa[[n]] = Sum[aa[[k]]*aa[[n-k]], {k, 1, n-1}], {n, 5, nmax}]; aa (* Vaclav Kotesovec, Jan 25 2015 *)
|
|
|
PROG
|
(Haskell)
a025276 n = a025276_list !! (n-1)
a025276_list = 1 : 0 : 0 : 1 : f [1, 0, 0, 1] where
f xs = x' : f (x':xs) where
x' = sum $ zipWith (*) xs a025276_list
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
