%I #185 Jul 19 2024 08:46:43
%S 1,1,1,2,3,7,12,30,55,143,273,728,1428,3876,7752,21318,43263,120175,
%T 246675,690690,1430715,4032015,8414640,23841480,50067108,142498692,
%U 300830572,859515920,1822766520,5225264024,11124755664,31983672534
%N If n = 2*m then a(n) = binomial(3*m, m)/(2*m+1), if n=2*m+1 then a(n) = binomial(3*m+1, m+1)/(2*m+1).
%C Hankel transform appears to be a signed aerated version of A059492. - _Paul Barry_, Apr 16 2008
%C Row sums of inverse Riordan array (1, x*(1-x^2))^(-1). - _Paul Barry_, Apr 16 2008
%C a(n) is the number of permutations of length n avoiding 213 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - _Manda Riehl_, Aug 05 2014
%C From _David Callan_, Aug 22 2014: (Start)
%C a(n) is the number of ordered trees (A000108) with n vertices in which every non-root non-leaf vertex has exactly one leaf child (no restriction on its non-leaf children). For example, a(4) counts the 3 trees
%C | |
%C \/ \|/ \/
%C (End)
%C From _Emeric Deutsch_, Oct 28 2014: (Start)
%C a(n) is the number of symmetric ternary trees having n internal nodes.
%C a(n) is the number of symmetric non-crossing rooted trees having n edges.
%C a(n) is the number of symmetric even trees having 2n edges.
%C a(n) is the number of symmetric diagonally convex directed polyominoes having n diagonals.
%C (End)
%C For the above 4 items see the Deutsch-Feretic-Noy reference.
%C a(n) is also the number of self-dual labeled non-crossing trees with n edges. See my paper in the links section. - _Nikos Apostolakis_, Jun 11 2019
%C Number of achiral polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. An achiral polyomino is identical to its reflection. - _Robert A. Russell_, Jan 20 2024
%H G. C. Greubel, <a href="/A047749/b047749.txt">Table of n, a(n) for n = 0..1000</a>
%H Per Alexandersson, Frether Getachew Kebede, Samuel Asefa Fufa, and Dun Qiu, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Getachew/get3.html">Pattern-Avoidance and Fuss-Catalan Numbers</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.2.
%H Nikos Apostolakis, <a href="https://arxiv.org/abs/1807.11602">Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections</a> arXiv:1804.01214 [math.CO], 2018.
%H Jean-Luc Baril, Alexander Burstein, and Sergey Kirgizov, <a href="https://arxiv.org/abs/2010.06270">Pattern statistics in faro words and permutations</a>, arXiv:2010.06270 [math.CO], 2020. See Theorem 4.4.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.
%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.
%H L. W. Beineke and R. E. Pippert, <a href="http://dx.doi.org/10.4153/CJM-1974-006-x">Enumerating dissectable polyhedra by their automorphism groups</a>, Can. J. Math., 26 (1974), 50-67.
%H M. Bousquet and C. Lamathe, <a href="http://dx.doi.org/10.1016/j.disc.2004.11.015">Enumeration of solid trees according to edge number and edge degree distribution</a>, Discr. Math., 298 (2005), 115-141.
%H Michel Bousquet and Cédric Lamathe, <a href="https://doi.org/10.46298/dmtcs.420">On symmetric structures of order two</a>, Discrete Math. Theor. Comput. Sci. 10 (2008), 153-176.
%H Hassen Cheriha, Yousra Gati, and Vladimir Petrov Kostov, <a href="https://arxiv.org/abs/1805.04261">Descartes' rule of signs, Rolle's theorem and sequences of admissible pairs</a>, arXiv:1805.04261 [math.CA], 2018.
%H Malin Christensson, <a href="http://malinc.se/m/ImageTiling.php">Make hyperbolic tilings of images</a>, web page, 2019.
%H S. J. Cyvin, Jianji Wang, J. Brunvoll, Shiming Cao, Ying Li, B. N. Cyvin, and Yugang Wang, <a href="https://doi.org/10.1016/S0022-2860(97)00025-2">Staggered conformers of alkanes: complete solution of the enumeration problem</a>, J. Molec. Struct. 413-414 (1997), 227-239.
%H S. J. Cyvin et al., <a href="http://dx.doi.org/10.1016/S0022-2860(97)00419-5">Enumeration of staggered conformers of alkanes and monocyclic cycloalkanes</a>, J. Molec. Struct., 445 (1998), 127-137.
%H Alexander Burstein, Sergi Elizalde, and Toufik Mansour, <a href="https://arxiv.org/abs/math/0610234">Restricted Dumont permutations, Dyck paths and noncrossing partitions</a>, arXiv:math/0610234 [math.CO], 2006. [Theorem 3.5]
%H Emeric Deutsch, <a href="http://www.jstor.org/stable/2695568">Another Path to Generalized Catalan Numbers:Problem 10751</a>, Amer. Math. Monthly, 108 (Nov., 2001), 872-873.
%H Emeric Deutsch, S. Feretic and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00340-0">Diagonally convex directed polyominoes and even trees: a bijection and related issues</a>, Discrete Math., 256 (2002), 645-654.
%H F. Hering et al., <a href="http://dx.doi.org/10.1016/0012-365X(82)90121-2">The enumeration of stack polytopes and simplicial clusters</a>, Discrete Math., 40 (1982), 203-217.
%H Clark Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Kimberling/kimberling24.html">Matrix Transformations of Integer Sequences</a>, J. Integer Seqs., Vol. 6, 2003.
%H Anthony Zaleski and Doron Zeilberger, <a href="https://arxiv.org/abs/1712.10072">On the Intriguing Problem of Counting (n+1,n+2)-Core Partitions into Odd Parts</a>, arXiv:1712.10072 [math.CO], 2017.
%F G.f. is 1+Z, where Z satisfies x*Z^3 + (3*x-2)*Z^2 + (3*x-1)*Z + x = 0. Equivalently, the g.f. Y satisfies x*Y^3 - 2*Y^2 + 3*Y - 1 = 0. - _Vladeta Jovovic_, Dec 06 2002
%F Reversion of g.f. (x-2*x^2)/(1-x)^3 (ignoring signs). - _Ralf Stephan_, Mar 22 2004
%F G.f.: (4/(3*x))*(sin((1/3)*asin(sqrt(27*x^2/4))))^2 +(2/sqrt(3*x^2))*sin((1/3)*asin(sqrt(27*x^2/4))). - _Paul Barry_, Nov 08 2006
%F G.f.: 1/(1-2*sin(asin(3*sqrt(3)*x/2)/3)/sqrt(3)). - _Paul Barry_, Apr 16 2008
%F From _Paul D. Hanna_, Sep 20 2009: (Start)
%F G.f. satisfies: A(x) = 1 + x*A(x)^2*A(-x);
%F also, A(x)*A(-x) = B(x^2) where B(x) = 1 + x*B(x)^3 = g.f. of A001764.
%F (End)
%F G.f.: 1/(1-C(x)) where C(x) = Reverse(x-x^3) = x + x^3 + 3*x^5 + 12*x^7 + 55*x^9 + ... (cf. A001764). - _Joerg Arndt_, Apr 16 2011
%F G.f.: G(z^2)+z*G(z^2)^2, where G(z) = 1 + z*G(z)^3, the generating function for A001764. - _Robert A. Russell_, Jan 26 2024
%F From _Gary W. Adamson_, Jul 14 2011: (Start)
%F a(n) is the upper left term in M^n, M = the infinite square production matrix:
%F 1, 1, 0, 0, 0, 0, ...
%F 0, 0, 1, 0, 0, 0, ...
%F 1, 1, 0, 1, 0, 0, ...
%F 0, 0, 1, 0, 1, 0, ...
%F 1, 1, 0, 1, 0, 1, ...
%F ... (End)
%F Conjecture D-finite with recurrence: 8*n*(n+1)*a(n) + 36*n*(n-2)*a(n-1) - 6*(9*n^2-18*n+14)*a(n-2) - 27*(3*n-7)*(3*n-8)*a(n-3) = 0. - _R. J. Mathar_, Dec 19 2011
%F 0 = a(n)*(+7308954*a(n+2) - 16659999*a(n+3) - 4854519*a(n+4) + 6201838*a(n+5)) + a(n+1)*(-406053*a(n+2) - 1627560*a(n+3) + 1683538*a(n+4) - 245747*a(n+5)) + a(n+2)*(+45117*a(n+2) + 235870*a(n+3) + 173953*a(n+4) - 484295*a(n+5)) + a(n+3)*(-41820*a(n+3) - 50184*a(n+4) + 22304*a(n+5)) for all n in Z if a(-1) = -2/3. - _Michael Somos_, Oct 29 2014
%F a(0) = 1; a(n) = Sum_{i=0..n-1} Sum_{j=0..n-i-1} (-1)^i * a(i) * a(j) * a(n-i-j-1). - _Ilya Gutkovskiy_, Jul 28 2021
%F a(n) = binomial(A032766(n),floor((n+1)/2))/(2*floor(n/2)+1). - _Miko Labalan_, Nov 28 2023
%F a(n) = 2*A005036(n) - A005034(n) = A005034(n) - 2*A369315(n) = A005036(n) - A369315(n). - _Robert A. Russell_, Jan 20 2024
%F From _Robert A. Russell_, Mar 20 2024: (Start)
%F a(n) = U(n) in the Beineke and Pippert link.
%F G.f.: E(1)(t*E(3)(t^2)) (second entry in Table 1), where E(d)(t) is defined in formula 3 of Hering link. (End)
%F From _Robert A. Russell_, Jul 15 2024: (Start)
%F a(2m) = A001764(m) ~ (3^3/2^2)^m*sqrt(3/(2*Pi*(2*m)^3)).
%F a(n+2)/a(n) ~ 27/4; a(2m+1)/a(2m) ~ 3; a(2m)/a(2m-1) ~ 9/4. (End)
%e G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 7*x^5 + 12*x^6 + 30*x^7 + 55*x^8 + ...
%p A047749 := proc(m) if m mod 2 = 1 then x := (m-1)/2; RETURN((3*x+1)!/((x+1)!*(2*x+1)!)); fi; x := m/2; RETURN((3*x)!/(x!*(2*x+1)!)); end;
%p A047749 := proc(m) local x; if m mod 2 = 1 then x := (m-1)/2; RETURN((3*x+1)!/((x+1)!*(2*x+1)!)); fi; RETURN(A001764(m/2)); end;
%t a[ n_] := If[ n < 1, Boole[n == 0], SeriesCoefficient[ InverseSeries[ Series[ (x + 2 x^2) / (1 + x)^3, {x, 0, n}]], {x, 0, n}]]; (* _Michael Somos_, Oct 29 2014 *)
%t Table[If[OddQ[n],2Binomial[(3n-1)/2,(n-1)/2],Binomial[3n/2,n/2]]/(n+1),{n,0,40}] (* _Robert A. Russell_, Jan 19 2024 *)
%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1+x*A^2*subst(A,x,-x+x*O(x^n)));polcoeff(A,n)} \\ _Paul D. Hanna_, Sep 20 2009
%o (PARI) x='x+O('x^66);
%o C(x)=serreverse(x-x^3); /* =x+x^3+3*x^5+12*x^7+55*x^9 +..., cf. A001764 */
%o s=1/(1-C(x)); /* g.f. */
%o Vec(s) /* _Joerg Arndt_, Apr 16 2011 */
%o (Sage)
%o def A047749_list(n) :
%o D = [0]*n; D[1] = 1
%o R = []; b = False; h = 1
%o for i in range(n) :
%o for k in (1..h) :
%o D[k] = D[k] + D[k-1]
%o R.append(D[h])
%o if b : h += 1
%o b = not b
%o return R
%o A047749_list(35) # _Peter Luschny_, May 03 2012
%o (Sage) [1]+[((1+(-1)^n)*binomial(3*n/2,n/2)/(n+1) + (1-(-1)^n)* binomial((3*n-1)/2, (n+1)/2)/n)/2 for n in (1..35)] # _G. C. Greubel_, Jul 07 2019
%o (Magma) G:=Gamma; [Round((1+(-1)^n)*G(3*n/2+1)/(G(n/2+1)*Factorial(n+1)) + (1-(-1)^n)*G((3*n+1)/2)/(G((n+3)/2)*Factorial(n)))/2: n in [0..35]]; // _G. C. Greubel_, Jul 07 2019
%o (Python)
%o from math import comb
%o def A047749(n): return comb(n+(a:=n>>1),a+(b:=n&1))//(n+1-b) # _Chai Wah Wu_, Jul 30 2022
%Y Column k=3 of A369929 and k=4 of A370062.
%Y Cf. A000108, A032766, A059492.
%Y Cf. A006013 is the odd-indexed terms of this sequence.
%Y Polyominoes: A005034 (oriented), A005036 (unoriented), A369315 (chiral), A001764 (rooted), A208355(n-1) {3,oo}, A369472 {5,oo}.
%K nonn
%O 0,4
%A _N. J. A. Sloane_