A122880 Catalan numbers minus odd-indexed Fibonacci numbers.

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

Offset: 1

Author

Gary W. Adamson, Sep 16 2006

Keywords

• nonn

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)

Examples

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

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]

Crossrefs

Cf. A000108, A001519, A122881.

Non-crossing 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.

Programs

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

Formula

A000108(n) - A001519(n), n > 0; A000108 = Catalan numbers, A001519 = odd-indexed Fibonacci numbers.

Extensions

More terms from Emeric Deutsch, Aug 21 2008