

A006013


a(n) = binomial(3*n+1,n)/(n+1).
(Formerly M1782)


120



1, 2, 7, 30, 143, 728, 3876, 21318, 120175, 690690, 4032015, 23841480, 142498692, 859515920, 5225264024, 31983672534, 196947587823, 1219199353190, 7583142491925, 47365474641870, 296983176369495, 1868545312633440, 11793499763070480
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Enumerates pairs of ternary trees [Knuth, 2014].  N. J. A. Sloane, Dec 09 2014
G.f. (offset 1) is series reversion of x  2x^2 + x^3.
a(n) = number of ways to connect 2*n  2 points labeled 1, 2, ..., 2*n2 in a line with 0 or more noncrossing arcs above the line such that each maximal contiguous sequence of isolated points has even length. For example, with arcs separated by dashes, a(3) = 7 counts {} (no arcs), 12, 14, 23, 34, 1234, 1423. It does not count 13 because 2 is an isolated point.  David Callan, Sep 18 2007
In my 2003 paper I introduced Lalgebras. These are Kvector spaces equipped with two binary operations > and < satisfying (x > y) < z = x > (y < z). In my arXiv paper mathph/0709.3453 I show that the free Lalgebra on one generator is related to symmetric ternary trees with odd degrees, so the dimensions of the homogeneous components are 1, 2, 7, 30, 143, .... These Lalgebras are closely related to the socalled triplicialalgebras, 3 associative operations and 3 relations whose free object is related to even trees.  Philippe Leroux (ph_ler_math(AT)yahoo.com), Oct 05 2007
a(n1) is also the number of projective dependency trees with n nodes.  Marco Kuhlmann (marco.kuhlmann(AT)lingfil.uu.se), Apr 06 2010
Also the number of Dyck npaths with up steps colored in two ways (N or A) and avoiding NA. The 7 Dyck 2paths are NDND, ADND, NDAD, ADAD, NNDD, ANDD, and AADD.  David Scambler, Jun 24 2013
a(n) is also the number of permutations avoiding 213 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n1 nodes. See A245904 for more information on increasing strict binary trees.  Manda Riehl Aug 07 2014
With offset 1, a(n) is the number of ordered trees (A000108) with n nonleaf vertices and n leaf vertices such that every nonleaf vertex has a leaf child (and hence exactly one leaf child).  David Callan, Aug 20 2014
a(n) is the number of paths in the plane with unit east and north steps, never going above the line x=2y, from (0,0) to (2n+1,n).  Ira M. Gessel, Jan 04 2018
a(n) is the number of words on the alphabet [n+1] that avoid the patterns 231 and 221 and contain exactly one 1 and exactly two occurrences of every other letter.  Colin Defant, Sep 26 2018
a(n) is the number of Motzkin paths of length 3n with n of each type of step, such that (1, 1) and (1, 0) alternate (ignoring (1, 1) steps). All paths start with a (1, 1) step.  Helmut Prodinger, Apr 08 2019
If f(x) is the generating function for (1)^n*a(n), a real solution of the equation y^3  y^2  x = 0 is given by y = 1 + x*f(x). In particular 1 + f(1) is Narayana's cow constant, A092526, aka the "supergolden" ratio.  R. James Evans, Aug 09 2023


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS



FORMULA

Convolution of A001764 with itself: 2*C(3*n + 2, n)/(3*n + 2), or C(3*n + 2, n+1)/(3*n + 2).
G.f.: (4/(3*x)) * sin((1/3)*arcsin(sqrt(27*x/4)))^2.
a(n) is the top left term in M^n, where M is the infinite square production matrix:
2, 1, 0, 0, 0, ...
3, 2, 1, 0, 0, ...
4, 3, 2, 1, 0, ...
5, 4, 3, 2, 1, ...
... (End)
a(n) is the sum of top row terms in Q^n, where Q is the infinite square production matrix as follows:
1, 1, 0, 0, 0, ...
2, 2, 1, 0, 0, ...
3, 3, 2, 1, 0, ...
4, 4, 3, 2, 1, ...
... (End)
Dfinite with recurrence: 2*(n+1)*(2n+1)*a(n) = 3*(3n1)*(3n+1)*a(n1).  R. J. Mathar, Dec 17 2011
E.g.f.: 2F2([2/3, 4/3]; [3/2,2]; 27*x/4).
a(n) ~ 3^(3*n+3/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). (End)
0 = v0*(+98415*v2 122472*v3 +32340*v4) +v1*(+444*v3 2968*v4) +v2*(60*v2 +56*v3 +64*v4) where v0=a(n)^2, v1=a(n)*a(n+1), v2=a(n+1)^2, v3=a(n+1)*a(n+2), v4=a(n+2)^2 for all n in Z if a(1)=2/3 and a(n)=0 for n<1.  Michael Somos, May 15 2022
a(n) = (1/4^n) * Product_{1 <= i <= j <= 2*n} (2*i + j + 2)/(2*i + j  1). Cf. A000260.  Peter Bala, Feb 21 2023
a(n) = Integral_{x=0..27/4} x^n*W(x) dx, where
W(x) = (((9 + sqrt(81  12*x))^(2/3)  (9  sqrt(81  12*x))^(2/3)) * 2^(1/3) * 3^(1/6)) / (12 * Pi * x^(1/3)), for x in (0, 27/4).
This integral representation is unique as W(x) is the solution of the Hausdorff power moment problem. Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0, with the singularity x^(1/3), and for x > 0 is monotonically decreasing to zero at x = 27/4. At x = 27/4 the first derivative of W(x) is infinite. (End)
G.f.: hypergeometric([2/3,1,4/3], [3/2,2], (3^3/2^2)*x). See the e.g.f. above.  Wolfdieter Lang, Feb 04 2024


EXAMPLE

a(3) = 30 since the top row of Q^3 = (12, 12, 5, 1).
G.f. = 1 + 2*x + 7*x^2 + 30*x^3 + 143*x^4 + 728*x^5 + 3876*x^6 + 21318*x^7 + ...  Michael Somos, May 15 2022


MATHEMATICA

Binomial[3#+1, #]/(#+1)&/@Range[0, 30] (* Harvey P. Dale, Mar 16 2011 *)


PROG

(Sage)
D = [0]*(n+1); D[1] = 1
R = []; b = false; h = 1
for i in range(2*n) :
for k in (1..h) : D[k] += D[k1]
if b : R.append(D[h]); h += 1
b = not b
return R
(Haskell)
a006013 n = a007318 (3 * n + 1) n `div` (n + 1)
a006013' n = a258708 (2 * n + 1) n
(Python)
from math import comb


CROSSREFS

These are the odd indices of A047749.
Cf. A305574 (the same with offset 1 and the initial 1 replaced with 5).
Cf. A130564 (comment on c(k, n+1)).


KEYWORD

nonn,nice,easy


AUTHOR



EXTENSIONS



STATUS

approved



