

A006013


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


87



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.
Hankel transform is A005156(n+1).  Paul Barry, Jan 20 2007
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]
Number of subpartitions of [1^2, 2^2, ..., n^2].  Franklin T. AdamsWatters, Apr 13 2011
a(n) = sum of (n+1)th row terms of triangle A143603.  Gary W. Adamson, Jul 07 2011
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) = A258708(2*n+1, n).  Reinhard Zumkeller, Jun 22 2015
a(n) = A110616(n+1, 1).  Ira M. Gessel, Jan 04 2018
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


REFERENCES

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


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000[Terms 0 to 100 computed by T. D. Noe; terms 101 to 1000 by G. C. Greubel, Jan 14 2017]
A. Aggarwal, Armstrong's Conjecture for (k, mk+1)Core Partitions, arXiv:1407.5134 [math.CO], 2014.
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, (2016), #16.3.5.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
W. G. Brown, Enumeration of nonseparable planar maps, Canad. J. Math., 15 (1963), 526545.
W. G. Brown, Enumeration of nonseparable planar maps. [Annotated scanned copy]
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, 19 (2016), #16.6.1.
F. Cazals, Combinatorics of NonCrossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
F. Chapoton, F. Hivert, and J.C. Novelli, A setoperad of formal fractions and dendriformlike suboperads, arXiv:1307.0092 [math.CO], 2013.
F. Chapoton and S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv:1310.4521 [math.CO], 2013.
Jins de Jong, Alexander Hock, and Raimar Wulkenhaar, Catalan tables and a recursion relation in noncommutative quantum field theory, arXiv:1904.11231 [mathph], 2019.
C. Defant and N. Kravitz, Stacksorting for words, arXiv:1809.09158 [math.CO], 2018.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645654.
I. Gessel and G. Xin, The generating function of ternary trees and continued fractions, arXiv:math/0505217 [math.CO], 2005.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
HsienKuei Hwang, Mihyun Kang, and GuanHuei Duh, Asymptotic Expansions for SubCritical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss DagstuhlLeibnizZentrum für Informatik, 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 432.
S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on beta(1, 0)trees, arXiv:1210.2618 [math.CO], 2012.  From N. J. A. Sloane, Dec 31 2012
Sergey Kitaev, Anna de Mier, and Marc Noy, On the number of selfdual rooted maps, European J. Combin. 35 (2014), 377387. MR3090510. See Theorem 1.  N. J. A. Sloane, May 19 2014
Don Knuth, 20th Anniversary Christmas Tree Lecture.
Philippe Leroux, An algebraic framework of weighted directed graphs, Int. J. Math. Math. Sci. 58. (2003).
Philippe Leroux, Lalgebras, triplicialalgebras, within an equivalence of categories motivated by graphs, arXiv:0709.3453 [mathph], 2008.
HoHon Leung and Thotsaporn "Aek" Thanatipanonda, A Probabilistic TwoPile Game, arXiv:1903.03274 [math.CO], 2019.
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2plane trees, arXiv:1304.6544 [math.PR], 2013.
Henri Muehle and Philippe Nadeau, A Poset Structure on the Alternating Group Generated by 3Cycles, arXiv:1803.00540 [math.CO], 2018.
Liviu I. Nicolaescu, Counting Morse functions on the 2sphere, arXiv:math/0512496 [math.GT], 2005.
J.C. Novelli and J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv:1403.5962 [math.CO], 2014.
M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301313, 1998.
J.B. Priez and A. Virmaux, Noncommutative Frobenius characteristic of generalized parking functions: Application to enumeration, arXiv:1411.4161 [math.CO], 20142015.
Helmut Prodinger, On some questions by Cameron about ternary paths  a linear algebra approach, arXiv:1910.02320 [math.CO], 2019.
Helmut Prodinger, Sarah J. Selkirk, and Stephan Wagner, On two subclasses of Motzkin paths and their relation to ternary trees, arXiv:1902.01681 [math.CO], 2019.
Jocelyn Quaintance, Combinatoric Enumeration of TwoDimensional Proper Arrays, Discrete Math., 307 (2007), 18441864.
Thomas M. Richardson, The three 'R's and Dual Riordan Arrays, arXiv:1609.01193 [math.CO], 2016.
D. G. Rogers, Comments on A111160, A055113 and A006013.
Michael Somos, Number Walls in Combinatorics.
Zhujun Zhang, A Note on Counting Dependency Trees, arXiv:1708.08789 [math.GM], 2017. See p. 3.
S.n. Zheng and S.l. Yang, On theShifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages.


FORMULA

G.f. is square of g.f. for ternary trees, A001764 [Knuth, 2014].  N. J. A. Sloane, Dec 09 2014
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.
G.f.: A(x)/x with A(x)=x/(1A(x))^2.  Vladimir Kruchinin, Dec 26 2010
From Gary W. Adamson, Jul 14 2011: (Start)
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)
From Gary W. Adamson, Aug 11 2011: (Start)
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
a(n) = 2*A236194(n)/n for n > 0.  Bruno Berselli, Jan 20 2014
From Ilya Gutkovskiy, Dec 29 2016: (Start)
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)


EXAMPLE

a(3) = 30 since the top row of Q^3 = (12, 12, 5, 1).


MAPLE

BB:=[T, {T=Prod(Z, Z, F, F), F=Sequence(B), B=Prod(F, F, Z)}, unlabeled]: seq(count(BB, size=i), i=2..24); # Zerinvary Lajos, Apr 22 2007


MATHEMATICA

InverseSeries[Series[y2*y^2+y^3, {y, 0, 32}], x]
Binomial[3#+1, #]/(#+1)&/@Range[0, 30] (* Harvey P. Dale, Mar 16 2011 *)


PROG

(PARI) a(n)=if(n<0, 0, (3*n+1)!/(n+1)!/(2*n+1)!)
(PARI) a(n)=if(n<0, 0, polcoeff(serreverse(x2*x^2+x^3+x^2*O(x^n)), n+1))
(Sage)
def A006013_list(n) :
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
A006013_list(23) # Peter Luschny, May 03 2012
(MAGMA) [Binomial(3*n+1, n)/(n+1): n in [0..30]]; // Vincenzo Librandi, Mar 29 2015
(Haskell)
a006013 n = a007318 (3 * n + 1) n `div` (n + 1)
a006013' n = a258708 (2 * n + 1) n
 Reinhard Zumkeller, Jun 22 2015


CROSSREFS

These are the odd indices of A047749.
Cf. A121645, A115728, A143603, A236194.
Cf. A007318, A071948, A110616, A258708.
Sequence in context: A260773 A174796 A046648 * A187979 A243632 A196148
Adjacent sequences: A006010 A006011 A006012 * A006014 A006015 A006016


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Edited by N. J. A. Sloane, Feb 21 2008


STATUS

approved



