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

Author

Wolfdieter Lang

Keywords

• easy
• nonn

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

Examples

			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
		

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.

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.

Programs

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

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

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

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