

A006318


Large Schröder numbers.
(Formerly M1659)


185



1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890, 95149655201962, 518431875418926
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The number of perfect matchings in a triangular grid of n squares (n = 1, 4, 9, 16, 25, ...).  Roberto E. Martinez II, Nov 05 2001
a(n) is the number of subdiagonal paths from (0, 0) to (n, n) consisting of steps East (1, 0), North (0, 1) and Northeast (1, 1) (sometimes called royal paths).  David Callan, Mar 14 2004
Twice A001003 (except for the first term).
a(n) is the number of dissections of a regular (n+4)gon by diagonals that do not touch the base. (A diagonal is a straight line joining two nonconsecutive vertices and dissection means the diagonals are noncrossing though they may share an endpoint. One side of the (n+4)gon is designated the base.) Example: a(1)=2 because a pentagon has only 2 such dissections: the empty one and the one with a diagonal parallel to the base.  David Callan, Aug 02 2004
From Jonathan Vos Post, Dec 23 2004: (Start)
The only prime in this sequence is 2. The semiprimes (intersection with A001358) are a(2) = 6, a(3) = 22, a(4) = 394, a(9) = 206098 and a(215), and correspond 1to1 with prime superCatalan numbers, also called prime little Schröder numbers (intersection of A001003 and A000040), which are listed as A092840 and indexed as A092839.
The 3almost prime large Schröder numbers a(7) = 8558, a(11) = 5293446, a(17) = 111818026018, a(19) = 3236724317174, a(21) = 95149655201962 (intersection of A006318 and A014612) correspond 1to1 with semiprime superCatalan numbers, also called semiprime little Schröder numbers (intersection of A001003 and A001358), which are listed as A101619 and indexed as A101618. These relationships all derive from the fact that a(n) = 2*A001003(n).
Eric W. Weisstein comments that the Schröder numbers bear the same relationship to the Delannoy numbers (A001850) as the Catalan numbers (A000108) do to the binomial coefficients. (End)
a(n) is the number of lattice paths from (0, 0) to (n+1, n+1) consisting of unit steps north N = (0, 1) and variablelength steps east E = (k, 0), with k a positive integer, that stay strictly below the line y = x except at the endpoints. For example, a(2) = 6 counts 111NNN, 21NNN, 3NNN, 12NNN, 11N1NN, 2N1NN (east steps indicated by their length). If the word "strictly" is replaced by "weakly", the counting sequence becomes the little Schröder numbers, A001003 (offset).  David Callan, Jun 07 2006
a(n) is the number of dissections of a regular (n+3)gon with base AB that do not contain a triangle of the form ABP with BP a diagonal. Example: a(1) = 2 because the square DC   AB has only 2 such dissections: the empty one and the one with the single diagonal AC (although this dissection contains the triangle ABC, BC is not a diagonal).  David Callan, Jul 14 2006
a(n) is the number of (colored) Motzkin npaths with each upstep and each flatstep at ground level getting one of 2 colors and each flatstep not at ground level getting one of 3 colors. Example: With their colors immediately following upsteps/flatsteps, a(2) = 6 counts U1D, U2D, F1F1, F1F2, F2F1, F2F2.  David Callan, Aug 16 2006
a(n) is the number of separable permutations, i.e., permutations avoiding 2413 and 3142 (see Shapiro and Stephens).  Vincent Vatter, Aug 16 2006
The Hankel transform of this sequence is A006125(n+1) = [1, 2, 8, 64, 1024, 32768, ...]; example: Det([1, 2, 6, 22; 2, 6, 22, 90; 6, 22, 90, 394; 22, 90, 394, 1806 ]) = 64.  Philippe Deléham, Sep 03 2006
Triangle A144156 has row sums equal to A006318 with left border A001003.  Gary W. Adamson, Sep 12 2008
a(n) is also the number of orderpreserving and orderdecreasing partial transformations (of an nchain). Equivalently, it is the order of the Schröder monoid, PC sub n.  Abdullahi Umar, Oct 02 2008
Sum_{n >= 0} a(n)/10^n  1 = [9sqrt(41)]/2.  Mark Dols (markdols99(AT)yahoo.com), Jun 22 2010
1/sqrt(41) = sum_{n >= 0} Delannoy number(n)/10^n.  Mark Dols (markdols99(AT)yahoo.com), Jun 22 2010
a(n) is also the dimension of the space Hoch(n) related to Hochschild two cocyles.  Ph. Leroux (ph_ler_math(AT)yahoo.com), Aug 24 2010
Let W = (w(n, k)) denote the augmentation triangle (as at A193091) of A154325; then w(n, n) = A006318(n).  Clark Kimberling, Jul 30 2011
Conjecture: For each n > 2, the polynomial sum_{k = 0}^n a(k)*x^{nk} is irreducible modulo some prime p < n*(n+1).  ZhiWei Sun, Apr 07 2013
From Jon Perry, May 24 2013: (Start)
Consider a Pascal triangle variant where T(n, k) = T(n, k1) + T(n1, k1) + T(n1, k), i.e., the order of performing the calculation must go from left to right (A033877). This sequence is the rightmost diagonal.
Triangle begins:
1
1 2
1 4 6
1 6 16 22
1 8 30 68 90
(End)
a(n) is the number of permutations avoiding 2143, 3142 and one of the patterns among 246135, 254613, 263514, 524361, 546132.  Alexander Burstein, Oct 05 2014
a(n) is the number of semistandard Young tableaux of shape n x 2 with consecutive entries. That is, j \in P and 1<=i<=j imply i \in P.  Graham H. Hawkes, Feb 15 2015


REFERENCES

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 25442563.
D. Andrica and E. J. Ionascu, On the number of polynomials with coefficients in [n], An. St. Univ. Ovidius Constanta, 2013, to appear.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 1936.
Barcucci, E.; Del Lungo, A.; Pergola, E.; and Pinzani, R.; Some permutations with forbidden subsequences and their inversion number. Discrete Math. 234 (2001), no. 13, 115.
Paul Barry, On IntegerSequenceBased Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
P. Barry, RiordanBernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.
O. Bodini, A. Genitrini, F. Peschanski and N.Rolin, Associativity for binary parallel processes, CALDAM 2015.
S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142154.
William Y. C. Chen and Carol J. Wang, Noncrossing Linked Partitions and Large (3, 2)Motzkin Paths, Discrete Math., 312 (2012), 19181922.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81, #21, (4), q_n.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.
Deng, Eva Y. P.; Dukes, Mark; Mansour, Toufik; and Wu, Susan Y. J.; Symmetric Schröder paths and restricted involutions. Discrete Math. 309 (2009), no. 12, 41084115. See p. 4109.
E. Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235240.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341358.
Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 21822212. MR2404544 (2009j:05019)  From N. J. A. Sloane, May 01 2012
M. Dziemianczuk, Generalizing Delannoy numbers via counting weighted lattice paths, INTEGERS, 13 (2013), #A54.
Egge, Eric S., Restricted signed permutations counted by the Schröder numbers. Discrete Math. 306 (2006), 552563. [Many applications of these numbers.]
S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497499.
S. Gire, Arbres, permutations a motifs exclus et cartes planaire: quelques problemes algorithmiques et combinatoires, Ph.D. Thesis, Universite Bordeaux I, 1993.
N. S. S. Gu, N. Y. Li and T. Mansour, 2Binary trees: bijections and related issues, Discr. Math., 308 (2008), 12091221.
Guruswami, Venkatesan, Enumerative aspects of certain subclasses of perfect graphs. Discrete Math. 205 (1999), 97117.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
D. E. Knuth, The Art of Computer Programming, Vol. 1, Section 2.2.1, Problem 11.
D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000) 121130.
Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171183. MR1983276 (2004b:05006). See Table 1.
G. Kreweras, Sur les hiérarchies de segments, Cahiers Bureau Universitaire Recherche Opérationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.
Laradji, A. and Umar, A. Asymptotic results for semigroups of orderpreserving partial transformations. Comm. Algebra 34 (2006), 10711075.  Abdullahi Umar, Oct 11 2008
L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223229.
L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schröder numbers and the Nkings problem, SIAM J. Discrete Math., Vol. 4 (1991), pp. 275280.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178 and also Problems 6.39 and 6.40.
Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015; http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf
P. Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Treebased Arithmetic Computations, arXiv preprint arXiv:1507.06944, 2015


LINKS

Fung Lam, Table of n, a(n) for n = 0..2000 (terms 0..100 by T. D. Noe)
A. Asinowski, G. Barequet, M. BousquetMélou, T. Mansour, R. Pinter, Orders induced by segments in floorplans and (2143,3412)avoiding permutations, arXiv:1011.1889 [math.CO].
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of lengthincreasing forbidden subsequences
E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hillfree generalized Motzkin paths
Paul Barry, Laurent Biorthogonal Polynomials and Riordan Arrays, arXiv preprint arXiv:1311.2292, 2013
Arkady Berenstein, Vladimir Retakh, Christophe Reutenauer and Doron Zeilberger, The Reciprocal of Sum_{n >= 0} a^n b^n for noncommuting a and b, Catalan numbers and noncommutative quadratic equations, arXiv preprint arXiv:1206.4225, 2012.  From N. J. A. Sloane, Nov 28 2012
J. Bloom, A. Burstein, Egge triples and unbalanced Wilfequivalence, arXiv preprint arXiv:1410.0230, 2014
O. Bodini, A. Genitrini and F. Peschanski, The Combinatorics of Nondeterminism, In proc. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'13), Leibniz International Proceedings in Informatics, pp 425436, 2013.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Patternavoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.
M. Bremner, S. Madariaga, Lie and Jordan products in interchange algebras, arXiv preprint arXiv:1408.3069, 2014
M. Bremner, S. Madariaga, Permutation of elements in double semigroups, arXiv preprint arXiv:1405.2889, 2014
R. Brignall, S. Huczynska and V. Vatter, Simple permutations and algebraic generating functions
MarieLouise Bruner and Martin Lackner, On the Likelihood of SinglePeaked Preferences, arXiv preprint, 2015.
Alexander Burstein, Sergi Elizalde and Toufik Mansour, Restricted Dumont permutations, Dyck paths and noncrossing partitions, arXiv math.CO/0610234. [Theorem 3.5]
A. Burstein, J. Pantone, Two examples of unbalanced Wilfequivalence, arXiv:1402.3842, 2014.
D. Callan, An application of a bijection of Mansour, Deng, and Du, arXiv preprint arXiv:1210.6455, 2012.
HuiQin Cao, Hao Pan, A Sterntype congruence for the Schröder numbers, arXiv:1512.06310 [math.NT], 2015.
F. Chapoton, F. Hivert, J.C. Novelli, A setoperad of formal fractions and dendriformlike suboperads, arXiv preprint arXiv:1307.0092, 2013
F. Chapoton, S. Giraudo, Enveloping operads and bicoloured noncrossing configurations, arXiv preprint arXiv:1310.4521, 2013
W. Y. C. Chen, L. H. Liu and C. J. Wang, Linked Partitions and Permutation Tableaux, arXiv preprint arXiv:1305.5357, 2013
J. Cigler, Hankel determinants of some polynomial sequences, 2012.
M. Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87103.
S. Crowley, Integral Transforms of the Harmonic Sawtooth Map, The Riemann Zeta Function, Fractal Strings, and a Finite Reflection Formula, arXiv preprint arXiv:1210.5652, 2012.
S. Crowley, Mellin and Laplace Integral Transforms Related to the Harmonic Sawtooth Map and a Diversion Into The Theory Of Fractal Strings, 2012.
R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449, 2013
B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.7), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747, 2014
S.P. Eu and T.S. Fu, A simple proof of the Aztec diamond problem
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792, 2012.  From N. J. A. Sloane, Oct 03 2012
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 474.
Olivier Gérard, Illustration of initial terms
Étienne Ghys, Quand beaucoup de courbes se rencontrent — Images des Mathématiques, CNRS, 2009.
Étienne Ghys, Intersecting curves, Amer. Math. Monthly, 120 (2013), 232242.
Samuele Giraudo, Operads from posets and Koszul duality, arXiv preprint, 2015.
Li Guo and Jun Pei, Averaging algebras, Schröder numbers and rooted trees, arXiv preprint arXiv:1401.7386, 2014
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 159
S. Kamioka, Laurent biorthogonal polynomials, qNarayana polynomials and domino tilings of the Aztec diamonds, arXiv preprint arXiv:1309.0268, 2013
Sergey Kitaev and Jeffrey Remmel, Simple marked mesh patterns, arXiv preprint arXiv:1201.1323, 2012
Nate Kube and Frank Ruskey, Sequences That Satisfy a(na(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
Laradji, A. and Umar, A. Combinatorial results for semigroups of orderpreserving partial transformations, Journal of Algebra 278, (2004), 342359.
Laradji, A. and Umar, A. Combinatorial results for semigroups of orderdecreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8
Philippe Leroux, Hochschild twococycles and the good triple (As,Hoch,Mag^\infty), arXiv:0806.4093
Peter Luschny, The Lost Catalan Numbers And The Schröder Tableaux.
J.C. Novelli and J.Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, Fundamenta Mathematicae 193 (2007), no. 3, 189241.
P. Peart and W.J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
Jun Pei, Li Guo, Averaging algebras, Schröder numbers, rooted trees and operads, Journal of Algebraic Combinatorics, Volume 42, Issue 1, August 2015, pp 73109; arXiv:1401.7386 [math.RA], 2014.
E. Pergola and R. A. Sulanke, Schröder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.
Markus Saers, Dekai Wu and Chris Quirk, On the Expressivity of Linear Transductions, The 13th Machine Translation Summit.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261272.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers [Corrected annotated scanned copy]
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.
R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths
R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin. 5 (1998), Research Paper 47, 11 pp.
ZhiWei Sun, On Delannoy numbers and Schröder numbers, Journal of Number Theory, Volume 131, Issue 12, December 2011, Pages 23872397; doi:10.1016/j.jnt.2011.06.005; arXiv 1009.2486.
ZhiWei Sun, Conjectures involving combinatorial sequences, arXiv preprint arXiv:1208.2683, 2012.  N. J. A. Sloane, Dec 25 2012
Z.W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in ShangriLa (eds., S. Kanemitsu, H.Z. Li and J.Y. Liu), Proc. the 6th ChinaJapan Sem. Number Theory (Shanghai, August 1517, 2011), World Sci., Singapore, 2013, pp. 244258.  N. J. A. Sloane, Dec 28 2012
Paul Tarau, On Typedirected Generation of Lambda Terms, preprint, 2015.
V. K. Varma and H. Monien, Renormalization of twobody interactions due to higherbody interactions of lattice bosons, arXiv preprint arXiv:1211.5664, 2012.  N. J. A. Sloane, Jan 03 2013
Yi Wang and BaoXuan Zhu, Proofs of some conjectures on monotonicity of numbertheoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595, 2013
M. S. Waterman, Home Page (contains copies of his papers)
Eric Weisstein's World of Mathematics, Schröder Number
J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247262.
J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Contextfree coalgebras, 2013.
S.n. Zheng and S.l. Yang, On theShifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics 2014, Article ID 848374.
Index entries for "core" sequences


FORMULA

G.f.: (1x(16*x+x^2)^(1/2))/(2*x).
a(n) = 2*hypergeom([ n+1, n+2], [2], 1).  Vladeta Jovovic, Apr 24 2003
For n > 0, a(n) = (1/n)*sum(k = 0, n, 2^k*C(n, k)*C(n, k1)).  Benoit Cloitre, May 10 2003
The g.f. satisfies (1x)A(x)xA(x)^2 = 1.  Ralf Stephan, Jun 30 2003
For the asymptotic behavior see A001003 (remembering that A006318 = 2*A001003).  N. J. A. Sloane, Apr 10 2011
Row sums of A088617 and A060693. a(n) = sum (k = 0..n, C(n+k, n)*C(n, k)/k+1).  Philippe Deléham, Nov 28 2003
With offset 1 : a(1) = 1, a(n) = a(n1) + sum(i = 1, n1, a(i)*a(ni)).  Benoit Cloitre, Mar 16 2004
a(n) = sum(k = 0, n, A000108(k)*binomial(n+k, nk)).  Benoit Cloitre, May 09 2004
a(n) = Sum_{k = 0..n} A011117(n, k).  Philippe Deléham, Jul 10 2004
a(n) = (CentralDelannoy[n+1]  3 CentralDelannoy[n])/(2n) = (CentralDelannoy[n+1] + 6 CentralDelannoy[n]  CentralDelannoy[n1])/2 for n>=1 where CentralDelannoy is A001850.  David Callan, Aug 16 2006
The Hankel transform of this sequence is A006125(n+1) = [1, 2, 8, 64, 1024, 32768, ...]; example: Det([1, 2, 6, 22 ; 2, 6, 22, 90; 6, 22, 90, 394; 22, 90, 394, 1806 ]) = 64.  Philippe Deléham, Sep 03 2006
A123164(n+1)  A123164(n) = (2n+1)a (n >= 0);
and 2*A123164(n) = (n+1)a(n)  (n1)a(n1) (n > 0).  Abdullahi Umar, Oct 11 2008
Define the general Delannoy numbers d(i, j) as in A001850. Then a(k) = d(2*k, k)  d(2*k, k1) and a(0) = 1, sum[{(1)^j}*{d(n, j) + d(n1, j1)}*a(nj)] = 0, j = 0, 1, ..., n.  Peter E John, Oct 19 2006
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n1} + a_0*a_{n1} + a_1*a_{n2} + ... + a_{n2}*a_1 for n >= t. For example, Phi([1]) is the Catalan numbers A000108. The present sequence is (essentially) Phi([2]).  Gary W. Adamson, Oct 27 2008
G.f.: 1/(12x/(1x/(12x/(1x/(12x/(1x/(12x/(1x/(12x/(1x.... (continued fraction).  Paul Barry, Dec 08 2008
G.f.: 1/(1xx/(1xx/(1xx/(1xx/(1xx/(1... (continued fraction).  Paul Barry, Jan 29 2009
a(n) ~ ((3+2*sqrt(2))^n)/(n*sqrt(2*Pi*n)*sqrt(3*sqrt(2)4))*(1(9*sqrt(2)+24)/(32*n)+...).  G. Nemes (nemesgery(AT)gmail.com), Jan 25 2009
Logarithmic derivative yields A002003.  Paul D. Hanna, Oct 25 2010
a(n) = the upper left term in M^(n+1), M = the production matrix:
1, 1, 0, 0, 0, 0,...
1, 1, 1, 0, 0, 0,...
2, 2, 1, 1, 0, 0,...
4, 4, 2, 1, 1, 0,...
8, 8, 8, 2, 1, 1,...
...  Gary W. Adamson, Jul 08 2011
a(n) is the sum of top row terms in Q^n, Q = an infinite square production matrix as follows:
1, 1, 0, 0, 0, 0,...
1, 1, 2, 0, 0, 0,...
1, 1, 1, 2, 0, 0,...
1, 1, 1, 1, 2, 0,...
1, 1, 1, 1, 1, 2,...
...  Gary W. Adamson, Aug 23 2011
From Tom Copeland, Sep 21 2011: (Start)
With F(x) = (13*xsqrt(16*x+x^2))/(2*x) an o.g.f. (nulling the n = 0 term) for A006318, G(x) = x/(2+3*x+x^2) is the compositional inverse.
Consequently, with H(x) = 1/ (dG(x)/dx) = (2+3*x+x^2)^2 / (2x^2),
a(n)=(1/n!)*[(H(x)*d/dx)^n] x evaluated at x = 0, i.e.,
F(x) = exp[x*H(u)*d/du] u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). (End)
a(n1) = number of ordered complete binary trees with n leaves having k internal vertices colored black, the remaining n  1  k internal vertices colored white, and such that each vertex and its rightmost child have different colors ([Drake, Example 1.6.7]). For a refinement of this sequence see A175124.  Peter Bala, Sep 29 2011
Recurrence: (n2)*a(n2)  3*(2*n1)*a(n1) + (n+1)*a(n) = 0.  Vaclav Kotesovec, Oct 05 2012
G.f.: A(x) = (1  x  sqrt(16x+x^2))/(2*x)= (1  G(0))/x; G(k) = 1 + x  2*x/G(k+1); (continued fraction, 1step).  Sergei N. Gladkovskii, Jan 04 2012
G.f.: A(x) = (1  x  sqrt(16x+x^2))/(2*x)= (G(0)1)/x; G(k)= 1  x/(1  2/G(k+1)); (continued fraction, 2step).  Sergei N. Gladkovskii, Jan 04 2012
a(n+1) = a(n) + sum (a(k)*(nk): k = 0..n).  Reinhard Zumkeller, Nov 13 2012
G.f.: 1/Q(0) where Q(k) = 1 + k*(1x)  x  x*(k+1)*(k+2)/Q(k+1); (continued fraction).  Sergei N. Gladkovskii, Mar 14 2013
a(1n) = a(n).  Michael Somos, Apr 03 2013
G.f.: 1/x  1  U(0)/x, where U(k)= 1  x  x/U(k+1) ; (continued fraction).  Sergei N. Gladkovskii, Jul 16 2013
G.f.: (2  2*x  G(0))/(4*x), where G(k)= 1 + 1/( 1  x*(6x)*(2*k1)/(x*(6x)*(2*k1) + 2*(k+1)/G(k+1) )); (continued fraction).  Sergei N. Gladkovskii, Jul 16 2013
a(n) = 1/(n+1) (Sum_{j=0..n} C(n+j,j)*C(n+j+1,j+1)*(Sum_{k=0..nj} (1)^k*C(n+j+k,k))).  Graham H. Hawkes, Feb 15 2015
a(n) = hypergeom([n, n+1], [2], 1).  Peter Luschny, Mar 23 2015
a(n) = sqrt(2) * LegendreP(n,1,3) where LegendreP is the associated Legendre function of the first kind (in Maple's notation).  Robert Israel, Mar 23 2015


EXAMPLE

a(3) = 22 since the top row of Q^n = (6, 6, 6, 4, 0, 0, 0,...); where 22 = (6 + 6 + 6 + 4).
G.f. = 1 + 2*x + 6*x^2 + 22*x^3 + 90*x^4 + 394*x^5 + 1806*x^6 + 8858*x^7 + 41586*x^8 + ...


MAPLE

Order := 24: solve(series((yy^2)/(1+y), y)=x, y); # then A(x)=y(x)/x
BB:=(1zsqrt(16*z+z^2))/2: BBser:=series(BB, z=0, 24): seq(coeff(BBser, z, n), n=1..23); # Zerinvary Lajos, Apr 10 2007
A006318_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*a[w1]+add(a[j]*a[wj1], j=1..w1) od; convert(a, list)end: A006318_list(22); # Peter Luschny, May 19 2011
A006318 := n> add(binomial(n+k, nk) * binomial(2*k, k)/(k+1), k=0..n): seq(A006318(n), n=0..22); # Johannes W. Meijer, Jul 14 2013
seq(simplify(hypergeom([n, n+1], [2], 1)), n=0..100); # Robert Israel, Mar 23 2015


MATHEMATICA

a[0] = 1; a[n_Integer] := a[n] = a[n  1] + Sum[a[k]*a[n  1  k], {k, 0, n  1}]; Array[a[#] &, 30]
InverseSeries[Series[(y  y^2)/(1 + y), {y, 0, 24}], x] (* then A(x) = y(x)/x  Len Smiley, Apr 11 2000 *)
CoefficientList[Series[(1  x  (1  6x + x^2)^(1/2))/(2x), {x, 0, 30}], x] (* Harvey P. Dale, May 01 2011 *)
a[ n_] := 2 Hypergeometric2F1[ n + 1, n + 2, 2, 1]; (* Michael Somos, Apr 03 2013 *)
a[ n_] := With[{m = If[ n < 0, 1  n, n]}, SeriesCoefficient[(1  x  Sqrt[ 1  6 x + x^2])/(2 x), {x, 0, m}]]; (* Michael Somos, Jun 10 2015 *)


PROG

(PARI) {a(n) = if( n<0, n = 1n); polcoeff( (1  x  sqrt( 1  6*x + x^2 + x^2 * O(x^n))) / 2, n+1)}; /* Michael Somos, Apr 03 2013 */
(PARI) {a(n) = if( n<1, 1, sum( k=0, n, 2^k * binomial( n, k) * binomial( n, k1)) / n)};
(Sage) # Generalized algorithm of L. Seidel
def A006318_list(n) :
D = [0]*(n+1); D[1] = 1
b = True; h = 1; R = []
for i in range(2*n) :
if b :
for k in range(h, 0, 1) : D[k] += D[k1]
h += 1;
else :
for k in range(1, h, 1) : D[k] += D[k1]
R.append(D[h1]);
b = not b
return R
A006318_list(23) # Peter Luschny, Jun 02 2012
(Haskell)
a006318 n = a004148_list !! n
a006318_list = 1 : f [1] where
f xs = y : f (y : xs) where
y = head xs + sum (zipWith (*) xs $ reverse xs)
 Reinhard Zumkeller, Nov 13 2012
(Python)
from gmpy2 import divexact
A006318 = [1, 2]
for n in range(3, 10**3):
....A006318.append(divexact(A006318[1]*(6*n9)(n3)*A006318[2], n))
# Chai Wah Wu, Sep 01 2014


CROSSREFS

Apart from leading term, twice A001003. Cf. A025240.
Sequences A085403, A086456, A103137, A112478 are essentially the same sequence.
Main diagonal of A033877.
Cf. A088617, A060693. Row sums of A104219. Bisections give A138462, A138463.
Cf. A144156.  Gary W. Adamson, Sep 12 2008
Cf. A002003.  Paul D. Hanna, Oct 25 2010
Row sums of A175124.
Cf. A004148.
Sequence in context: A049134 A086456 * A155069 A103137 A165546 A053617
Adjacent sequences: A006315 A006316 A006317 * A006319 A006320 A006321


KEYWORD

nonn,easy,core,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from David W. Wilson
Edited by Charles R Greathouse IV, Apr 20 2010


STATUS

approved



