%I #21 Dec 11 2019 06:50:42
%S 0,0,0,1,8,43,196,820,3265,12615,47840,179355,667875,2478022,9180616,
%T 34011401,126120212,468411235,1743105373,6500874434,24300686879,
%U 91049069203,341924710480,1286932932251,4854167659403,18346988061078
%N Catalan numbers minus odd-indexed Fibonacci numbers.
%C From _Emeric Deutsch_, Aug 21 2008: (Start)
%C 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.
%C Number of ordered trees of height at least 4 and having n edges. (End)
%C From _Gus Wiseman_, Jun 22 2019: (Start)
%C 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:
%C {{1,4},{2,3}} {{1,2,5},{3,4}}
%C {{1,4,5},{2,3}}
%C {{1,5},{2,3,4}}
%C {{1},{2,5},{3,4}}
%C {{1,4},{2,3},{5}}
%C {{1,5},{2},{3,4}}
%C {{1,5},{2,3},{4}}
%C {{1,5},{2,4},{3}}
%C (End)
%H E. Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325. [_Emeric Deutsch_, Aug 21 2008]
%F A000108(n) - A001519(n), n > 0; A000108 = Catalan numbers, A001519 = odd-indexed Fibonacci numbers.
%e a(5) = 8 = A000108(5) - A001519(5) = 42 - 34.
%p with(combinat): seq(binomial(2*n,n)/(n+1)-fibonacci(2*n-1), n=1..27); # _Emeric Deutsch_, Aug 21 2008
%t With[{nn=30},#[[1]]-#[[2]]&/@Thread[{CatalanNumber[Range[nn]], Fibonacci[ Range[ 1,2nn,2]]}]] (* _Harvey P. Dale_, Nov 07 2016 *)
%Y Cf. A000108, A001519, A122881.
%Y Non-crossing set partitions are A000108.
%Y Capturing set partitions are A326243.
%Y Crossing, not capturing set partitions are A326245.
%Y Crossing, capturing set partitions are A326246.
%Y Cf. A000110, A054391, A099947, A326255, A326259.
%K nonn
%O 1,5
%A _Gary W. Adamson_, Sep 16 2006
%E More terms from _Emeric Deutsch_, Aug 21 2008
|