login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

Table of n, a(n) for n=1..26.

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

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

EXAMPLE

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

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

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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 30 22:26 EDT 2020. Contains 337440 sequences. (Running on oeis4.)