|
| |
|
|
A001764
|
|
a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).
(Formerly M2926 N1174)
|
|
414
|
|
|
|
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, 8414640, 50067108, 300830572, 1822766520, 11124755664, 68328754959, 422030545335, 2619631042665, 16332922290300, 102240109897695, 642312451217745, 4048514844039120, 25594403741131680, 162250238001816900
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Smallest number of straight line crossing-free spanning trees on n points in the plane.
Number of dissections of some convex polygon by nonintersecting diagonals into polygons with an odd number of sides and having a total number of 2n+1 edges (sides and diagonals). - Emeric Deutsch, Mar 06 2002
Number of lattice paths of n East steps and 2n North steps from (0,0) to (n,2n) and lying weakly below the line y=2x. - David Callan, Mar 14 2004
With interpolated zeros, this has g.f. 2*sqrt(3)*sin(arcsin(3*sqrt(3)*x/2)/3)/(3*x) and a(n) = C(n+floor(n/2),floor(n/2))*C(floor(n/2),n-floor(n/2))/(n+1). This is the first column of the inverse of the Riordan array (1-x^2,x(1-x^2)) (essentially reversion of y-y^3). - Paul Barry, Feb 02 2005
Number of 12312-avoiding matchings on [2n].
Number of complete ternary trees with n internal nodes, or 3n edges.
Number of rooted plane trees with 2n edges, where every vertex has even outdegree ("even trees").
a(n) is the number of noncrossing partitions of [2n] with all blocks of even size. E.g.: a(2)=3 counts 12-34, 14-23, 1234. - David Callan, Mar 30 2007
Pfaff-Fuss-Catalan sequence C^{m}_n for m=3, see the Graham et al. reference, p. 347. eq. 7.66.
Also 3-Raney sequence, see the Graham et al. reference, p. 346-7.
The number of lattice paths from (0,0) to (2n,0) using an Up-step=(1,1) and a Down-step=(0,-2) and staying above the x-axis. E.g., a(2) = 3; UUUUDD, UUUDUD, UUDUUD. - Charles Moore (chamoore(AT)howard.edu), Jan 09 2008
a(n) is (conjecturally) the number of permutations of [n+1] that avoid the patterns 4-2-3-1 and 4-2-5-1-3 and end with an ascent. For example, a(4)=55 counts all 60 permutations of [5] that end with an ascent except 42315, 52314, 52413, 53412, all of which contain a 4-2-3-1 pattern and 42513. - David Callan, Jul 22 2008
With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} a(j) (-t)^j x^(2j+1). Let U(x,t)=(x-A(x,t))/t. Then DU(x,t)/Dt=dU/dt+U*dU/dx=0 and U(x,0)=x^3, i.e., U is a solution of the inviscid Burgers's, or Hopf, equation. Also U(x,t)=U(x-t*U(x,t),0) and dB(x,t)/dt = U(B(x,t),t) = x^3 = U(x,0). The characteristics for the Hopf equation are x(t) = x(0) + t*U(x(t),t) = x(0) + t*U(x(0),0) = x(0) + t*x(0)^3 = B(x(0),t). These results apply to all the Fuss-Catalan sequences with 3 replaced by n>0 and 2 by n-1 (e.g., A000108 with n=2 and A002293 with n=4), see also A086810, which can be generalized to A133437, for associahedra. - Tom Copeland, Feb 15 2014
Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Kreweras lattice (noncrossing partitions ordered by refinement) of size n, see the Bernardi & Bonichon (2009) and Kreweras (1972) references. - Noam Zeilberger, Jun 01 2016
Number of sum-indecomposable (4231,42513)-avoiding permutations. Conjecturally, number of sum-indecomposable (2431,45231)-avoiding permutations. - Alexander Burstein, Oct 19 2017
a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link. - Caleb Ji, May 14 2018
Number of complete quadrillages of 2n+2-gons. See Baryshnikov p. 12. See also Nov. 10 2014 comments in A134264. - Tom Copeland, Jun 04 2018
a(n) is the number of 2-regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2-regular tortoise-sortable words on the alphabet [n] (see the Defant and Kravitz link). - Colin Defant, Sep 26 2018
a(n) is the number of Motzkin paths of length 3n with n steps of each type, with the condition that (1, 0) and (1, 1) steps alternate (starting with (1, 0)). - Helmut Prodinger, Apr 08 2019
a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 312 and 1342. - Colin Defant, Jun 08 2019
The compositional inverse o.g.f. pair in Copeland's comment above are related to a pair of quantum fields in Balduf's thesis by Theorem 4.2 on p. 92. - Tom Copeland, Dec 13 2019
The sequences of Fuss-Catalan numbers, of which this is the first after the Catalan numbers A000108 (the next is A002293), appear in articles on random matrices and quantum physics. See Banica et al., Collins et al., and Mlotkowski et al. Interpretations of these sequences in terms of the cardinality of specific sets of noncrossing partitions are provided by A134264. - Tom Copeland, Dec 21 2019
a(n) is the total number of down steps before the first up step in all 2_1-Dyck paths of length 3*n for n > 0. A 2_1-Dyck path is a lattice path with steps (1,2), (1,-1) that starts and ends at y = 0 and does not go below the line y = -1. - Sarah Selkirk, May 10 2020
a(n) is the number of pairs (A<=B) of noncrossing partitions of [n]. - Francesca Aicardi, May 28 2022
a(n) is the number of parking functions of size n avoiding the patterns 231 and 321. - Lara Pudwell, Apr 10 2023
|
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347. See also the Pólya-Szegő reference.
W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
N. V. Alexeev, Number of trees in a random graph, Probabilistic methods in discrete mathematics, Extended abstracts of the 10th International Petrozavodsk Conference (Russia, 2019), 12-13. (in Russian)
T. Banica, S. Belinschi, M. Capitaine, and B. Collins, Free Bessel laws, arXiv:0710.5931 [math.PR], 2008.
Y. Baryshnikov, On Stokes sets, New developments in singularity theory (Cambridge, 2000): 65-86. Kluwer Acad. Publ., Dordrecht, 2001.
L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 87-98.
Peter J. Cameron and Liam Stott, Trees and cycles, arXiv:2010.14902 [math.CO], 2020. See p. 33.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and it is on pages vii-xiv of the same issue.
Tian-Xiao He, The Vertical Recursive Relation of Riordan Arrays and Its Matrix Representation, J. Int. Seq., Vol. 25 (2022), Article 22.9.5. [https://cs.uwaterloo.ca/journals/JIS/VOL25/He/he49.html HTML] (A001764)
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344, (T_n for s=3).
|
|
|
FORMULA
|
G.f.: (2/sqrt(3*x))*sin((1/3)*arcsin(sqrt(27*x/4))).
E.g.f.: hypergeom([1/3, 2/3], [1, 3/2], 27/4*x).
Integral representation as n-th moment of a positive function on [0, 27/4]: a(n) = Integral_{x=0..27/4} (x^n*((1/12) * 3^(1/2) * 2^(1/3) * (2^(1/3)*(27 + 3 * sqrt(81 - 12*x))^(2/3) - 6 * x^(1/3))/(Pi * x^(2/3)*(27 + 3 * sqrt(81 - 12*x))^(1/3)))), n >= 0. This representation is unique. (End)
G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2) [Cyvin (1998)]. - Ralf Stephan, Jun 30 2003
a(n) = n-th coefficient in expansion of power series P(n), where P(0) = 1, P(k+1) = 1/(1 - x*P(k)^2).
G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of). - Paul Barry, Mar 26 2010
Let M = the production matrix:
1, 1
2, 2, 1
3, 3, 2, 1
4, 4, 3, 2, 1
5, 5, 4, 3, 2, 1
...
a(n) = upper left term in M^n. Top row terms of M^n = (n+1)-th row of triangle A143603, with top row sums generating A006013: (1, 2, 7, 30, 143, 728, ...). (End)
Recurrence: a(0)=1; a(n) = Sum_{i=0..n-1, j=0..n-1-i} a(i)a(j)a(n-1-i-j) for n >= 1 (counts ternary trees by subtrees of the root). - David Callan, Nov 21 2011
G.f.: 1 + 6*x/(Q(0) - 6*x); Q(k) = 3*x*(3*k + 1)*(3*k + 2) + 2*(2*(k^2) + 5*k +3) - 6*x*(2*(k^2) + 5*k + 3)*(3*k + 4)*(3*k + 5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2011
D-finite with recurrence: 2*n*(2n+1)*a(n) - 3*(3n-1)*(3n-2)*a(n-1) = 0. - R. J. Mathar, Dec 14 2011
G.f.: F([2/3,4/3], [3/2], 27/4*x) / F([2/3,1/3], [1/2], 27/4*x) where F() is the hypergeometric function. - Joerg Arndt, Sep 01 2012
0 = a(n)*(-3188646*a(n+2) + 20312856*a(n+3) - 11379609*a(n+4) + 1437501*a(n+5)) + a(n+1)*(177147*a(n+2) - 2247831*a(n+3) + 1638648*a(n+4) - 238604*a(n+5)) + a(n+2)*(243*a(n+2) + 31497*a(n+3) - 43732*a(n+4) + 8288*a(n+5)) for all integer n. - Michael Somos, Jun 03 2016
a(n) ~ 3^(3*n + 1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). - Ilya Gutkovskiy, Nov 21 2016
Given g.f. A(x), then A(1/8) = -1 + sqrt(5), A(2/27) = (-1 + sqrt(3))*3/2, A(4/27) = 3/2, A(3/64) = -2 + 2*sqrt(7/3), A(5/64) = (-1 + sqrt(5))*2/sqrt(5), etc. A(n^2/(n+1)^3) = (n+1)/n if n > 1. - Michael Somos, Jul 17 2018
A(x) = exp( Sum_{n >= 1} (1/3)*binomial(3*n,n)*x^n/n ).
The sequence defined by b(n) := [x^n] A(x)^n = A224274(n) for n >= 1 and satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 3. Cf. A060941. (End)
G.f.: 1/sqrt(B(x)+(1-6*x)/(9*B(x))+1/3), with B(x):=((27*x^2-18*x+2)/54-(x*sqrt((-(4-27*x))*x))/(2*3^(3/2)))^(1/3). - Vladimir Kruchinin, Sep 28 2021
|
|
|
EXAMPLE
|
a(2) = 3 because the only dissections with 5 edges are given by a square dissected by any of the two diagonals and the pentagon with no dissecting diagonal.
G.f. = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...
|
|
|
MAPLE
|
with(combstruct): BB:=[T, {T=Prod(Z, F), F=Sequence(B), B=Prod(F, Z, F)}, unlabeled]:seq(count(BB, size=i), i=0..22); # Zerinvary Lajos, Apr 22 2007
with(combstruct):BB:=[S, {B = Prod(S, S, Z), S = Sequence(B)}, labelled]: seq(count(BB, size=n)/n!, n=0..21); # Zerinvary Lajos, Apr 25 2008
n:=30:G:=series(RootOf(g = 1+x*g^3, g), x=0, n+1):seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 03 2015
alias(PS=ListTools:-PartialSums): A001764List := proc(m) local A, P, n;
A := [1, 1]; P := [1]; for n from 1 to m - 2 do P := PS(PS([op(P), P[-1]]));
A := [op(A), P[-1]] od; A end: A001764List(25); # Peter Luschny, Mar 26 2022
|
|
|
MATHEMATICA
|
InverseSeries[Series[y-y^3, {y, 0, 24}], x] (* then a(n)=y(2n+1)=ways to place non-crossing diagonals in convex (2n+4)-gon so as to create only quadrilateral tiles *) (* Len Smiley, Apr 08 2000 *)
Table[Binomial[3n, n]/(2n+1), {n, 0, 25}] (* Harvey P. Dale, Jul 24 2011 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, (3*n)! / n! / (2*n + 1)!)};
(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x - x^3 + O(x^(2*n + 2))), 2*n + 1))};
(PARI) {a(n) = my(A); if( n<0, 0, A = 1 + O(x); for( m=1, n, A = 1 + x * A^3); polcoeff(A, n))};
(PARI) b=vector(22); b[1]=1; for(n=2, 22, for(i=1, n-1, for(j=1, n-1, for(k=1, n-1, if((i-1)+(j-1)+(k-1)-(n-2), NULL, b[n]=b[n]+b[i]*b[j]*b[k]))))); a(n)=b[n+1]; print1(a(0)); for(n=1, 21, print1(", ", a(n))) \\ Gerald McGarvey, Oct 08 2008
(PARI) Vec(1 + serreverse(x / (1+x)^3 + O(x^30))) \\ Gheorghe Coserea, Aug 05 2015
(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 not b : R.append(D[h])
else : h += 1
b = not b
return R
(Haskell)
a001764 n = a001764_list !! n
a001764_list = 1 : [a258708 (2 * n) n | n <- [1..]]
(GAP) List([0..25], n->Binomial(3*n, n)/(2*n+1)); # Muniru A Asiru, Oct 31 2018
(Python)
from math import comb
|
|
|
CROSSREFS
|
Cf. A000108, A001762, A001763, A002293 - A002296, A006013, A025174, A063548, A064017, A072247, A072248, A134264, A143603, A258708, A256311.
|
|
|
KEYWORD
|
easy,nonn,nice,core
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
