|
|
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*n-2 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, 12-34, 14-23. It does not count 13 because 2 is an isolated point. - David Callan, Sep 18 2007
In my 2003 paper I introduced L-algebras. These are K-vector spaces equipped with two binary operations > and < satisfying (x > y) < z = x > (y < z). In my arXiv paper math-ph/0709.3453 I show that the free L-algebra 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 L-algebras are closely related to the so-called triplicial-algebras, 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(n-1) 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 n-paths with up steps colored in two ways (N or A) and avoiding NA. The 7 Dyck 2-paths 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 2n-1 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 non-leaf vertices and n leaf vertices such that every non-leaf 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)
D-finite with recurrence: 2*(n+1)*(2n+1)*a(n) = 3*(3n-1)*(3n+1)*a(n-1). - 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[k-1]
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
|
|
|
|