OFFSET
1,5
COMMENTS
From Emeric Deutsch, Aug 21 2008: (Start)
Number of Dyck paths of height at least 4 and of semilength n. Example: a(5)=8 because we have UUUUUDDDDD, UUUUDUDDDD, UUUDUUDDDD, UUDUUUDDDD, UDUUUUDDDD and the reflection of the last three in a vertical axis.
Number of ordered trees of height at least 4 and having n edges. (End)
From Gus Wiseman, Jun 22 2019: (Start)
Also the number of non-crossing, capturing set partitions of {1..n}. A set partition is crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y, and capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z and y > t or x > z and y < t. Capturing is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(4) = 1 and a(5) = 8 non-crossing, capturing set partitions are:
{{1,4},{2,3}} {{1,2,5},{3,4}}
{{1,4,5},{2,3}}
{{1,5},{2,3,4}}
{{1},{2,5},{3,4}}
{{1,4},{2,3},{5}}
{{1,5},{2},{3,4}}
{{1,5},{2,3},{4}}
{{1,5},{2,4},{3}}
(End)
LINKS
E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325. [Emeric Deutsch, Aug 21 2008]
FORMULA
MAPLE
with(combinat): seq(binomial(2*n, n)/(n+1)-fibonacci(2*n-1), n=1..27); # Emeric Deutsch, Aug 21 2008
MATHEMATICA
With[{nn=30}, #[[1]]-#[[2]]&/@Thread[{CatalanNumber[Range[nn]], Fibonacci[ Range[ 1, 2nn, 2]]}]] (* Harvey P. Dale, Nov 07 2016 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gary W. Adamson, Sep 16 2006
EXTENSIONS
More terms from Emeric Deutsch, Aug 21 2008
STATUS
approved