

A122880


Catalan numbers minus oddindexed Fibonacci numbers.


11



0, 0, 0, 1, 8, 43, 196, 820, 3265, 12615, 47840, 179355, 667875, 2478022, 9180616, 34011401, 126120212, 468411235, 1743105373, 6500874434, 24300686879, 91049069203, 341924710480, 1286932932251, 4854167659403, 18346988061078
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

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)
Also the number of noncrossing, 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 noncrossing, 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



FORMULA



EXAMPLE



MAPLE

with(combinat): seq(binomial(2*n, n)/(n+1)fibonacci(2*n1), 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

Noncrossing set partitions are A000108.
Capturing set partitions are A326243.
Crossing, not capturing set partitions are A326245.
Crossing, capturing set partitions are A326246.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



