

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

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

Table of n, a(n) for n=1..26.
E. Deutsch and H. Prodinger, A bijection between directed columnconvex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319325. [Emeric Deutsch, Aug 21 2008]


FORMULA

A000108(n)  A001519(n), n > 0; A000108 = Catalan numbers, A001519 = oddindexed Fibonacci numbers.


EXAMPLE

a(5) = 8 = A000108(5)  A001519(5) = 42  34.


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

Cf. A000108, A001519, A122881.
Noncrossing set partitions are A000108.
Capturing set partitions are A326243.
Crossing, not capturing set partitions are A326245.
Crossing, capturing set partitions are A326246.
Cf. A000110, A054391, A099947, A326255, A326259.
Sequence in context: A137748 A005024 A094865 * A171479 A227209 A282523
Adjacent sequences: A122877 A122878 A122879 * A122881 A122882 A122883


KEYWORD

nonn


AUTHOR

Gary W. Adamson, Sep 16 2006


EXTENSIONS

More terms from Emeric Deutsch, Aug 21 2008


STATUS

approved



