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,3

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

Links

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

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

Example

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

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

Prog

(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 */

Crossrefs

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

Sequence in context: A149237 A054577 A206687 * A109268 A256960 A174993

Adjacent sequences: A106637 A106638 A106639 * A106641 A106642 A106643

Keyword

nonn

Author

Philippe Deléham, May 26 2005

Extensions

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

Status

approved