|
|
A122880
|
|
Catalan numbers minus odd-indexed 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 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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
|
|
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
|
Non-crossing 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
|
|
|
|