A106640 Row sums of A059346.

1, 1, 4, 11, 36, 117, 393, 1339, 4630, 16193, 57201, 203799, 731602, 2643903, 9611748, 35130195, 129018798, 475907913, 1762457595, 6550726731, 24428808690, 91377474411, 342763939656, 1289070060903, 4859587760076, 18360668311027, 69514565858653, 263693929034909

Offset: 0

Author

Philippe Deléham, May 26 2005

Keywords

• nonn

Comments

a(n) = p(n + 1) where p(x) is the unique degree-n polynomial such that p(k) = Catalan(k) for k = 0, 1, ..., n. - Michael Somos, Jan 05 2012

Number of Dyck (n+1)-paths whose minimum ascent length is 1. - David Scambler, Aug 22 2012

From Alois P. Heinz, Jun 29 2014: (Start)

a(n) is the number of ordered rooted trees with n+2 nodes such that the minimal outdegree equals 1. a(2) = 4:

o o o o

| | / \ / \

o o o o o o

| / \ | |

o o o o o

|

o

(End)

Number of non-crossing partitions of {1,2,..,n+1} that contain cyclical adjacencies. a(2) = 4, [12|3, 13|2, 1|23, 123]. - Yuchun Ji, Nov 13 2020

Examples

			1 + x + 4*x^2 + 11*x^3 + 36*x^4 + 117*x^5 + 393*x^6 + 1339*x^7 + 4630*x^8 + ...
a(2) = 4 since p(x) = (x^2 - x + 2) / 2 interpolates p(0) = 1, p(1) = 1, p(2) = 2, and p(3) = 4. - _Michael Somos_, Jan 05 2012
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000108, A005043, A244455, A000296, A247494.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, [1, 1, 4][n+1],
      ((30*n^3-44*n^2-22*n+24)*a(n-1)-(25*n^3-105*n^2+140*n-48)*a(n-2)
       -6*(n-1)*(5*n-4)*(2*n-3)*a(n-3))/(n*(n+2)*(5*n-9)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 29 2014

Mathematica

max = 30; t = Table[Differences[Table[CatalanNumber[k], {k, 0, max}], n], {n, 0, max}]; a[n_] := Sum[t[[n-k+1, k]], {k, 1, n}]; Array[a, max] (* Jean-François Alcover, Jan 21 2017 *)

PARI

{a(n) = if( n<0, 0, n++; subst( polinterpolate( vector(n, k, binomial( 2*k - 2, k - 1) / k)), x, n + 1))} /* Michael Somos, Jan 05 2012 */

PARI

{a(n) = local(A); if( n<0, 0, A = x * O(x^n); polcoeff( 2 / (sqrt( 1 - 2*x - 3*x^2 + A) + (1 + x) * sqrt( 1 - 4*x + A)) ,n))} /* Michael Somos, Jan 05 2012 */

Formula

G.f.: (sqrt( 1 - 2*x - 3*x^2 ) / (1 + x) - sqrt( 1 - 4*x )) / (2*x^2) = 2 / (sqrt( 1 - 2*x - 3*x^2 ) + (1 + x) * sqrt( 1 - 4*x )). - Michael Somos, Jan 05 2012

a(n) = A000108(n+1) - A005043(n+1).

a(n) ~ 2^(2*n+2) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jan 21 2017

a(n) = A000296(n+2) - A247494(n+1); i.e., remove the crossing partitions from the partitions with cyclical adjacencies. - Yuchun Ji, Nov 17 2020

Extensions

Typo in a(20) corrected and more terms from Alois P. Heinz, Jun 29 2014