A035101 E.g.f. x*(c(x/2)-1)/(1-2*x), where c(x) = g.f. for Catalan numbers A000108.

0, 1, 9, 87, 975, 12645, 187425, 3133935, 58437855, 1203216525, 27125492625, 664761133575, 17600023616175, 500706514833525, 15234653491682625, 493699195087473375, 16977671416936605375, 617528830880480644125, 23687738668934964248625

Offset

1,3

Comments

2nd column of triangular array A035342 whose first column is given by A001147(n), n >= 1. Recursion: a(n) = 2*n*a(n-1)+ A001147(n-1), n >= 2, a(1)=0.

a(n) gives the number of organically labeled forests (sets) with two rooted ordered trees with n non-root vertices. See the example a(3)=9 given in A035342. Organic labeling means that the vertex labels along the (unique) path from the root to any of the leaves (degree 1, non-root vertices) is increasing. - Wolfdieter Lang, Aug 07 2007

a(n), n>=2, enumerates unordered n-vertex forests composed of two plane (ordered) ternary (3-ary) trees with increasing vertex labeling. See A001147 (number of increasing ternary trees) and a D. Callan comment there. For a picture of some ternary trees see a W. Lang link under A001764.

a(n) is the number of linear chord diagrams on 2n vertices with one marked chord such that exactly 1 of the remaining n-1 chords are contained within the marked chord, see [Young]. - Donovan Young, Aug 11 2020

Links

Robert Israel, Table of n, a(n) for n = 1..370

Selden Crary, Richard Diehl Martinez, Michael Saunders, The Nu Class of Low-Degree-Truncated Rational Multifunctions. Ib. Integrals of Matern-correlation functions for all odd-half-integer class parameters, arXiv:1707.00705 [stat.ME], 2017, Table 2.

Alexander Kreinin, Integer Sequences and Laplace Continued Fraction, Preprint 2016.

Alexander Kreinin, Integer Sequences Connected to the Laplace Continued Fraction and Ramanujan's Identity, Journal of Integer Sequences, 19 (2016), #16.6.2.

Donovan Young, A critical quartet for queuing couples, arXiv:2007.13868 [math.CO], 2020.

Formula

a(n) = n!*A008549(n-1)/2^(n-1) = n!(4^(n-1)-binomial(2*n, n)/2)/2^(n-1).

a(n) = (2n-2)*a(n-1) + A129890(n-2). - Philippe Deléham, Oct 28 2013

a(n) = n!*2^(n-1) - A001147(n) = A002866(n) - A001147(n). - Peter Bala, Sep 11 2015

a(n) = -2*(n-1)*(2*n-3)*a(n-2)+(4*n-3)*a(n-1). - Robert Israel, Sep 11 2015

Example

a(2)=1 for the forest: {r1-1, r2-2} (with root labels r1 and r2). The order between the components of the forest is irrelevant (like for sets).
a(3)=9 increasing ternary 2-forest with n=3 vertices: there are three 2-forests (the one vertex tree together with any of the three different 2-vertex trees) each with three increasing labelings. - Wolfdieter Lang, Sep 14 2007

Maple

F:= gfun:-rectoproc({(4*n^2+6*n+2)*a(n)+(-4*n-5)*a(n+1)+a(n+2), a(1)=0, a(2)=1, a(3)=9}, a(n), remember):
map(f, [$1..30]); # Robert Israel, Sep 11 2015

Mathematica

Table[Round [n! (4^(n - 1) - Binomial[2 n, n]/2)/2^(n - 1)], {n, 1, 20}] (* Vincenzo Librandi, Sep 12 2015 *)

Prog

(Magma) I:=[0, 1, 9]; [n le 3 select I[n] else - 2*(n-1)*(2*n-3)*Self(n-2)+(4*n-3)*Self(n-1): n in [1..30]]; // Vincenzo Librandi, Sep 12 2015
(PARI) a(n) = n!*(4^(n-1)-binomial(2*n, n)/2)/2^(n-1);
vector(40, n, a(n)) \\ Altug Alkan, Oct 01 2015

Crossrefs

Cf. A000108, A002866, A008549, A336599.

Cf. A001147 (m=1 column of A035342). See a D. Callan comment there on the number of increasing ordered rooted trees on n+1 vertices.

Sequence in context: A223277 A267265 A152264 * A351525 A245491 A160466

Adjacent sequences: A035098 A035099 A035100 * A035102 A035103 A035104

Keyword

easy,nonn

Author

Wolfdieter Lang

Status

approved