|
| |
|
|
A001764
|
|
Binomial(3n,n)/(2n+1) (enumerates ternary trees and also non-crossing trees).
(Formerly M2926 N1174)
|
|
241
|
|
|
|
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. 2sqrt(3)sin(arcsin(3sqrt(3)x/2)/3)/(3x) 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) = 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 Down-steps=(1,k); where k<= -1 and stays above the x-axis. For example, a(2)= 3 ;[(1,1)(1,1)(1,-1)(1,-1)],[(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)] Also 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
Central terms of pendular triangle A167763. [From Philippe DELEHAM, Nov 12 2009]
|
|
|
REFERENCES
|
Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.
I. Bajunaid et al., Function series, Catalan numbers and random walks on trees, Amer. Math. Monthly 112 (2005), 765-785.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
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.
L. W. Beineke and R. E. Pippert, Enumerating dissectable polyhedra by their automorphism groups, Canad. J. Math., 26 (1974), 50-67.
Bousquet, Michel; and Lamathe, Cedric; On symmetric structures of order two. Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.
L. Carlitz, Enumeration of two-line arrays, Fib. Quart., 11 (1973), 113-130.
S. J. Cyvin et al., Enumeration of staggered conformers of alkanes: complete solution ..., J. Molec. Struct., 413 (1997), 237-239.
S. J. Cyvin et al., Enumeration of staggered conformers of alkanes and monocyclic ..., J. Molec. Struct., 445 (1998), 127-137.
E. Deutsch, S. Feretic and M. Noy, Diagonally convex directed polyominoes and even trees: a bijection and related issues, Discrete Math., 256 (2002), 645-654.
E. Deutsch and M. Noy, Statistics on non-crossing trees, Discr. Math., 254 (2002), 75-87.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
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.
N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on beta(1, 0)-trees, arXiv preprint arXiv:1210.2618, 2012. - From N. J. A. Sloane, Dec 31 2012
Kuba, Markus; Panholzer, Alois. Enumeration formulae for pattern restricted Stirling permutations. Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From N. J. A. Sloane, Sep 25 2012
W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.
Lun Lv and Sabrina X.M. Pang, Reduced Decompositions of Matchings, Electronic Journal of Combinatorics 18 (2011), #P107.
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).
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.
M. Noy, Enumeration of noncrossing trees on a circle, Discr. Math. 180 (1998), 301-313.
A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195.
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.
Jocelyn Quaintance, Combinatoric Enumeration of Two-Dimensional Proper Arrays, Discrete Math., 307 (2007), 1844-1864.
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).
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).
Anssi Yli-Jyra, On Dependency Analysis via Contractions and Weighted FSTs, in Shall We Play the Festschrift Game?, Springer, 2012, pp. 133-158; http://rd.springer.com/chapter/10.1007%2F978-3-642-30773-7_10?LI=true. - From N. J. A. Sloane, Dec 25 2012
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..100
O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13-th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
Joerg Arndt, Fxtbook, pp.337-338
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
M. Bousquet-Mélou and M. Petkov\v{s}ek, Walks confined in a quadrant are not always D-finite
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns
T. C. Copeland, Discriminating Deltas, Depressed Equations, and Generalized Catalan Numbers
J. A. Eidswick, Short factorizations of permutations into transpositions, Disc. Math. 73 (1989) 239-243
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486
I. Gessel and G. Xin, The generating function of ternary trees and continued fractions
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 53
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 285
W. Lang, Ternary trees with n=1,2,3 and 4 vertices.
H. Niederhausen, Catalan Traffic at the Beach.
A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195.
K. A. Penson and A. I. Solomon, Coherent states from combinatorial sequences.
B. Rittaud, On the Average Growth of Random Fibonacci Sequences, Journal of Integer Sequences, 10 (2007), Article 07.2.4.
M. Somos, Number Walls in Combinatorics.
Index entries for "core" sequences
Index entries for sequences related to trees
|
|
|
FORMULA
|
From Karol A. Penson, Nov 08 2001: (Start)
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)=int(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)), x=0..6.75), n=0, 1... This representation is unique. (End)
G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2) - 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]
From Gary W. Adamson, Jul 07 2011: (Start)
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[a(i)a(j)a(n-1-i-j), i=0..n-1, j=0..n-1-i] 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
2*n*(2n+1)*a(n)-3*(3n-1)*(3n-2)*a(n-1)=0. - R. J. Mathar, Dec 14 2011
REVERT transform of A115140. BINOMIAL transform is A188687. SUMADJ transform of A188678. HANKEL transform is A051255. INVERT transform of A023053. INVERT transform is A098746. - Michael Somos, Apr 07 2012
(n + 1) * a(n) = A174687(n).
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]
|
|
|
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.
1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...
|
|
|
MAPLE
|
A001764 := n->binomial(3*n, n)/(2*n+1);
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 (zerinvarylajos(AT)yahoo.com), 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 (zerinvarylajos(AT)yahoo.com), Apr 25 2008
|
|
|
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}] (* From 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) = local(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 */
(Sage)
def A001764_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[k-1]
if not b : R.append(D[h])
else : h += 1
b = not b
return R
A001764_list(22) # Peter Luschny, May 03 2012
|
|
|
CROSSREFS
|
Cf. A001762, A001763, A064017, A063548, A072247, A072248.
Cf. A143603, A006013
A column of triangle A102537.
Bisection of A047749 and A047761.
Row sums of triangle A108410.
Second column of triangle A062993.
Sequence in context: A024038 A007199 A179848 * A171780 A216493 A216494
Adjacent sequences: A001761 A001762 A001763 * A001765 A001766 A001767
|
|
|
KEYWORD
|
easy,nonn,nice,core
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
