|
%I M1659
%S 1,2,6,22,90,394,1806,8558,41586,206098,1037718,5293446,27297738,
%T 142078746,745387038,3937603038,20927156706,111818026018,600318853926,
%U 3236724317174,17518619320890,95149655201962,518431875418926
%N Large Schroeder numbers.
%C The number of perfect matchings in a triangular grid of n squares (n=1,4,9,16,25...). - Roberto E. Martinez II (martinez(AT)deas.harvard.edu), Nov 05 2001
%C a(n)=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
%C Twice A001003 (except for the first term).
%C a(n)=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
%C Comments from Jonathan Vos Post, Dec 23, 2004: "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) correspond 1-to-1 with prime super-Catalan numbers also called prime little Schroeder numbers (intersection of A001003 and A000040) which are listed as A092840 and indexed as A092839.
%C "The 3-almost prime large Schroeder numbers a(7)=8558, a(11)=5293446, a(17)=111818026018, a(19)=3236724317174, a(21)=95149655201962 (intersection of A006318 and A014612) correspond 1-to-1 with semiprime super-Catalan numbers also called semiprime little Schroeder 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).
%C "Eric Weisstein comments that the Schroeder numbers bear the relationship to the Delannoy numbers [A001850] as the Catalan numbers [A000108] do to the binomial coefficients."
%C a(n)=number of lattice paths from (0,0) to (n+1,n+1) consisting of unit steps north N=(0,1) and variable-length 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 Schroeder numbers A001003 (offset). - _David Callan_, Jun 07 2006
%C a(n)=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 D-C | | A-B 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
%C a(n) = number of (colored) Motzkin n-paths 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
%C a(n)=number of separable permutations, i.e. permutations avoiding 2413 and 3142, see Shapiro and Stephens. - _Vincent Vatter_, Aug 16 2006
%C 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 DELEHAM_, Sep 03 2006
%C Triangle A144156 has row sums = A006318 with left border A001003. [From _Gary W. Adamson_, Sep 12 2008]
%C a(n) is also the number of order-preserving and order-decreasing partial transformations (of an n-chain). Equivalently, it is the order of the Schroeder monoid, PC sub n. [From _Abdullahi Umar_, Oct 02 2008]
%C Sum_{n=0...infinity} a(n)/10^n-1 = [9-sqrt(41)]/2. 1/Sqrt(41)= sum_{n=0...infinity} Delannoy number(n)/10^n. [From M. Dols (markdols99(AT)yahoo.com), Jun 22 2010]
%C a(n) is also the dimension of the space Hoch(n) related to Hochschild two cocyles. [From Ph. Leroux (ph_ler_math(AT)yahoo.com), Aug 24 2010]
%C Let W=(w(n,k)) denote the augmentation triangle (as at A193091) of A154325; then w(n,n)=A006318(n). [From Clark Kimberling, Jul 30 2011]
%C Conjecture: For each n>2, the polynomial sum_{k=0}^n a(k)*x^{n-k} is irreducible modulo some prime p < n*(n+1). [From _Zhi-Wei Sun_, Apr 7, 2013]
%D M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
%D M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
%D Barcucci, E.; Del Lungo, A.; Pergola, E.; and Pinzani, R.; Some permutations with forbidden subsequences and their inversion number. Discrete Math. 234 (2001), no. 1-3, 1-15.
%D Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%D P. Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2. - From _N. J. A. Sloane_, Dec 29 2012
%D Arkady BERENSTEIN, Vladimir RETAKH, Christophe REUTENAUER and Doron ZEILBERGER, The Reciprocal of Sum_{n >= 0} a^n b^n for non-commuting a and b, Catalan numbers and non-commutative quadratic equations, Arxiv preprint arXiv:1206.4225, 2012. - From _N. J. A. Sloane_, Nov 28 2012
%D S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
%D D. Callan, An application of a bijection of Mansour, Deng, and Du, arXiv preprint arXiv:1210.6455, 2012. - From _N. J. A. Sloane_, Jan 01 2013
%D William Y. C. Chen and Carol J. Wang, Noncrossing Linked Partitions and Large (3, 2)-Motzkin Paths, Discrete Math., 312 (2012), 1918-1922; http://www.billchen.org/publications/appear-noncrossing/appear-noncrossing.htm. - From _N. J. A. Sloane_, Jun 08 2012
%D J. Cigler, Hankel determinants of some polynomial sequences, http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf, 2012. - From _N. J. A. Sloane_, Jan 02 2013
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81, #21, (4), q_n.
%D S. Crowley, Mellin and Laplace Integral Transforms Related to the Harmonic Sawtooth Map and a Diversion Into The Theory Of Fractal Strings, http://vixra.org/pdf/1202.0079v2.pdf, 2012.
%D 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. - From _N. J. A. Sloane_, Jan 01 2013
%D D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
%D 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, 4108-4115. See p. 4109.
%D E. Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
%D C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.
%D Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012
%D Egge, Eric S., Restricted signed permutations counted by the Schroeder numbers. Discrete Math. 306 (2006), 552-563. [Many applications of these numbers.]
%D 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
%D S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.
%D S. Gire, Arbres, permutations a motifs exclus et cartes planaire: quelques problemes algorithmiques et combinatoires, Ph.D. Thesis, Universite Bordeaux I, 1993.
%D N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
%D Guruswami, Venkatesan, Enumerative aspects of certain subclasses of perfect graphs. Discrete Math. 205 (1999), 97-117.
%D 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; http://repository.wit.ie/1693/1/AoifeThesis.pdf
%D D. E. Knuth, The Art of Computer Programming, Vol. 1, Section 2.2.1, Problem 11.
%D D. Kremer, Permutations with forbidden subsequences and a generalized Schroeder number, Discrete Math. 218 (2000) 121-130.
%D Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
%D G. Kreweras, Sur les hi\'{e}rarchies de segments, Cahiers Bureau Universitaire Recherche Op\'{e}rationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.
%D Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%D Laradji, A. and Umar, A. Asymptotic results for semigroups of order-preserving partial transformations. Comm. Algebra 34 (2006), 1071-1075. [From _Abdullahi Umar_, Oct 11 2008]
%D Philippe Leroux, Hochschild two-cocycles and the good triple (As,Hoch,Mag^\infty): arXiv:0806.4093 [From Ph. Leroux (ph_ler_math(AT)yahoo.com), Aug 24 2010]
%D L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.
%D Markus Saers, Dekai Wu and Chris Quirk, On the Expressivity of Linear Transductions, http://www.cse.ust.hk/~dekai/library/WU_Dekai/SaersWuQuirk_Mtsummit2011.pdf.
%D L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schroeder numbers and the N-kings problem, SIAM J. Discrete Math., Vol. 4 (1991), pp. 275-280.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178 and also Problems 6.39 and 6.40.
%D P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
%D R. A. Sulanke, Bijective recurrences concerning Schroeder paths, Electron. J. Combin. 5 (1998), Research Paper 47, 11 pp.
%D Zhi-Wei Sun, On Delannoy numbers and Schroeder numbers, Journal of Number Theory, Volume 131, Issue 12, December 2011, Pages 2387-2397; http://www.sciencedirect.com/science/article/pii/S0022314X11001715.; arXiv 1009.2486v4.
%D Zhi-Wei Sun, Conjectures involving combinatorial sequences, Arxiv preprint arXiv:1208.2683, 2012. - From _N. J. A. Sloane_, Dec 25 2012
%D 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 China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258; http://math.nju.edu.cn/~zwsun/142p.pdf. - From _N. J. A. Sloane_, Dec 28 2012
%D V. K. Varma and H. Monien, Renormalization of two-body interactions due to higher-body interactions of lattice bosons, arXiv preprint arXiv:1211.5664, 2012. - From _N. J. A. Sloane_, Jan 03 2013
%D J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247-262.
%D J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Context-free coalgebras, 2013; http://oai.cwi.nl/oai/asset/21313/21313A.pdf
%H T. D. Noe, <a href="/A006318/b006318.txt">Table of n, a(n) for n = 0..100</a>
%H A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, R. Pinter, <a href="http://front.math.ucdavis.edu/1011.1889">Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations</a>, arXiv:1011.1889 [math.CO]. - From _N. J. A. Sloane_, Dec 27 2012
%H C. Banderier and D. Merlini, <a href="http://www.dsi.unifi.it/~merlini/poster.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.
%H E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, <a href="http://www.dmtcs.org/volumes/abstracts/dm040103.abs.html">Permutations avoiding an increasing number of length-increasing forbidden subsequences</a>
%H E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="http://www.mat.univie.ac.at/~slc/opapers/s46rinaldi.html">ECO method and hill-free generalized Motzkin paths</a>
%H R. Brignall, S. Huczynska and V. Vatter, <a href="http://arXiv.org/abs/math.CO/0608391">Simple permutations and algebraic generating functions</a>
%H Alexander Burstein, Sergi Elizalde and Toufik Mansour, <a href="http://arXiv.org/abs/math.CO/0610234">Restricted Dumont permutations, Dyck paths and noncrossing partitions</a>, arXiv math.CO/0610234. [Theorem 3.5]
%H M. Ciucu, <a href="http://www.math.gatech.edu/~ciucu/list.html">Perfect matchings of cellular graphs</a>, J. Algebraic Combin., 5 (1996) 87-103.
%H B. Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.6.7)</a>, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
%H S.-P. Eu and T.-S. Fu, <a href="http://arXiv.org/abs/math.CO/0412041">A simple proof of the Aztec diamond problem</a>
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 474.
%H Olivier Gérard, <a href="/A006318/a006318.pdf">Illustration of initial terms</a>
%H Étienne Ghys, <a href="http://images.math.cnrs.fr/Quand-beaucoup-de-courbes-se.html">Quand beaucoup de courbes se rencontrent</a> — Images des Mathématiques, CNRS, 2009.
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=159">Encyclopedia of Combinatorial Structures 159</a>
%H Sergey Kitaev and Jeffrey Remmel, <a href="http://arxiv.org/abs/1201.1323">Simple marked mesh patterns</a>, Arxiv preprint arXiv:1201.1323, 2012
%H Laradji, A. and Umar, A. <a href="http://dx.doi.org/10.1016/j.jalgebra.2003.10.023">Combinatorial results for semigroups of order-preserving partial transformations</a>, Journal of Algebra 278, (2004), 342-359.
%H Laradji, A. and Umar, A. <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial results for semigroups of order-decreasing partial transformations</a>, J. Integer Seq. 7 (2004), 04.3.8
%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/TheLostCatalanNumbers">The Lost Catalan Numbers And The Schröder Tableaux</a>.
%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/0511200">Hopf algebras and dendriform structures arising from parking functions</a>, to appear in Fundamenta Mathematicae
%H P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Generating Functions via Hankel and Stieltjes Matrices</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H E. Pergola and R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Schroeder Triangles, Paths and Parallelogram Polyominoes</a>, J. Integer Sequences, 1 (1998), #98.1.7.
%H R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">Moments of generalized Motzkin paths</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.
%H R. A. Sulanke, <a href="http://math.boisestate.edu/~sulanke/recentpapindex.html">Moments, Narayana numbers and the cut and paste for lattice paths</a>
%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SchroederNumber.html">Schroeder Number</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H Olivier Gérard, <a href="/A006318/a006318.pdf">Illustration of initial terms</a>
%F G.f.: (1-x-(1-6*x+x^2)^(1/2))/(2*x).
%F a(n) = 2*hypergeom([ -n+1, n+2], [2], -1). - _Vladeta Jovovic_, Apr 24 2003
%F For n>0, a(n)=(1/n)*sum(k=0, n, 2^k*C(n, k)*C(n, k-1)) - _Benoit Cloitre_, May 10 2003
%F The g.f. satisfies (1-x)A(x)-xA(x)^2 = 1. - _Ralf Stephan_, Jun 30 2003
%F For the asymptotic behavior see A001003 (remembering that A006318 = 2*A001003). - _N. J. A. Sloane_, Apr 10 2011.
%F 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
%F With offset 1 : a(1)=1, a(n)=a(n-1)+sum(i=1, n-1, a(i)*a(n-i)). - _Benoit Cloitre_, Mar 16 2004
%F a(n) = sum(k=0, n, A000108(k)*binomial(n+k, n-k)) - _Benoit Cloitre_, May 09 2004
%F a(n) = Sum_{k = 0..n} A011117(n, k). - _Philippe Deléham_, Jul 10 2004
%F a(n) = (CentralDelannoy[n+1] - 3 CentralDelannoy[n])/(2n) = (-CentralDelannoy[n+1] + 6 CentralDelannoy[n] - CentralDelannoy[n-1])/2 for n>=1 where CentralDelannoy is A001850. - _David Callan_, Aug 16 2006
%F 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 DELEHAM_, Sep 03 2006
%F A123164(n+1) - A123164(n) = (2n+1)a (n>=0);
%F and 2*A123164(n) = (n+1)a(n) - (n-1)a(n-1) (n>0). - _Abdullahi Umar_, Oct 11 2008
%F Define the general Delannoy numbers d(i,j) as in A001850. Then a(k) = d(2*k,k) - d(2*k,k-1) and a(0).=1, sum[{(-1)^j}*{d(n,j)+d(n-1,j-1)}*a(n-j)] = 0, j=0,1,...,n. - Peter John (peter.john(AT)tu-ilmenau.de), Oct 19 2006
%F Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*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
%F G.f.: 1/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x/(1-2x/(1-x.... (continued fraction). [From _Paul Barry_, Dec 08 2008]
%F G.f.: 1/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction). [From _Paul Barry_, Jan 29 2009]
%F a(n) ~ ((3+2*sqrt(2))^n)/(n*sqrt(2*pi*n)*sqrt(3*sqrt(2)-4))*(1-(9*sqrt(2)+24)/(32*n)+...) [From G. Nemes (nemesgery(AT)gmail.com), Jan 25 2009]
%F Logarithmic derivative yields A002003. [From _Paul D. Hanna_, Oct 25 2010]
%F a(n) = the upper left term in M^(n+1), M = the production matrix:
%F 1, 1, 0, 0, 0, 0,...
%F 1, 1, 1, 0, 0, 0,...
%F 2, 2, 1, 1, 0, 0,...
%F 4, 4, 2, 1, 1, 0,...
%F 8, 8, 8, 2, 1, 1,...
%F ... - Gary W. Adamson, Jul 08 2011
%F a(n) is the sum of top row terms in Q^n, Q = an infinite square production matrix as follows:
%F 1, 1, 0, 0, 0, 0,...
%F 1, 1, 2, 0, 0, 0,...
%F 1, 1, 1, 2, 0, 0,...
%F 1, 1, 1, 1, 2, 0,...
%F 1, 1, 1, 1, 1, 2,...
%F ... - Gary W. Adamson, Aug 23 2011
%F From _Tom Copeland_, Sept 21 2011: (Start)
%F With F(x) = (1-3*x-sqrt(1-6*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.
%F Consequently, with H(x) = 1/ (dG(x)/dx) = (2+3*x+x^2)^2 / (2-x^2),
%F a(n)=(1/n!)*[(H(x)*d/dx)^n] x evaluated at x=0, i.e.,
%F F(x) = exp[x*H(u)*d/du] u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). (End)
%F a(n-1) = 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
%F Recurrence: (n-2)*a(n-2) - 3*(2*n-1)*a(n-1) + (n+1)*a(n) = 0. - _Vaclav Kotesovec_, Oct 05 2012
%F G.f.: A(x)=(1 - x - sqrt(1-6x+x^2))/(2*x)= (1 - G(0))/x; G(k)= 1 + x - 2*x/G(k+1); (continued fraction ,1-step ). - _Sergei N. Gladkovskii_, Jan 04 2012
%F G.f.: A(x)=(1 - x - sqrt(1-6x+x^2))/(2*x)= (G(0)-1)/x; G(k)= 1 - x/(1 - 2/G(k+1)); (continued fraction ,2-step ). - Sergei N. Gladkovskii, Jan 04 2012
%F a(n+1) = a(n) + sum (a(k)*(n-k): k=0..n). - _Reinhard Zumkeller_, Nov 13 2012
%F G.f.: 1/Q(0) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Mar 14 2013
%F a(-1-n) = a(n). - _Michael Somos_, Apr 03 2013
%e a(3) = 22 since the top row of Q^n = (6, 6, 6, 4, 0, 0, 0,...); where 22 = (6 + 6 + 6 + 4).
%e 1 + 2*x + 6*x^2 + 22*x^3 + 90*x^4 + 394*x^5 + 1806*x^6 + 8858*x^7 + 41586*x^8 + ...
%p Order := 24: solve(series((y-y^2)/(1+y),y)=x,y); # then A(x)=y(x)/x
%p BB:=(-1-z-sqrt(1-6*z+z^2))/2: BBser:=series(BB, z=0, 24): seq(coeff(BBser, z, n), n=1..23); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 10 2007
%p A006318_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
%p for w from 1 to n do a[w] := 2*a[w-1]+add(a[j]*a[w-j-1], j=1..w-1) od; convert(a,list)end: A006318_list(22); # _Peter Luschny_, May 19 2011
%t 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 ]
%t InverseSeries[Series[(y-y^2)/(1+y), {y, 0, 24}], x] (* then A(x)=y(x)/x *) - Len Smiley, Apr 11 2000
%t CoefficientList[Series[(1-x-(1-6x+x^2)^(1/2))/(2x),{x,0, 30}], x] (* _Harvey P. Dale_, May 01 2011 *)
%t a[n_] := 2*Hypergeometric2F1[-n+1, n+2, 2, -1] (* _Michael Somos_, Apr 03 2013 *)
%o (PARI) {a(n) = if( n<0, n = -1-n); polcoeff( (1 - x - sqrt( 1 - 6*x + x^2 + x^2 * O(x^n))) / 2, n+1)} /* _Michael Somos_, Apr 03 2013 */
%o (PARI) {a(n) = if( n<1, 1, sum( k=0, n, 2^k * binomial( n, k) * binomial( n, k-1)) / n)}
%o (Sage) # Generalized algorithm of L. Seidel
%o def A006318_list(n) :
%o D = [0]*(n+1); D[1] = 1
%o b = True; h = 1; R = []
%o for i in range(2*n) :
%o if b :
%o for k in range(h,0,-1) : D[k] += D[k-1]
%o h += 1;
%o else :
%o for k in range(1,h, 1) : D[k] += D[k-1]
%o R.append(D[h-1]);
%o b = not b
%o return R
%o A006318_list(23) # _Peter Luschny_, June 02 2012
%o (Haskell)
%o a006318 n = a004148_list !! n
%o a006318_list = 1 : f [1] where
%o f xs = y : f (y : xs) where
%o y = head xs + sum (zipWith (*) xs $ reverse xs)
%o -- _Reinhard Zumkeller_, Nov 13 2012
%Y Apart from leading term, twice A001003. Cf. A025240.
%Y Sequences A085403, A086456, A103137, A112478 are essentially the same sequence.
%Y Main diagonal of A033877.
%Y Cf. A088617, A060693. Row sums of A104219. Bisections give A138462, A138463.
%Y A144156 [From _Gary W. Adamson_, Sep 12 2008]
%Y Cf. A002003. [From _Paul D. Hanna_, Oct 25 2010]
%Y Row sums of A175124.
%Y Cf. A004148.
%K nonn,easy,core,nice,changed
%O 0,2
%A _N. J. A. Sloane_.
%E More terms from _David W. Wilson_
%E Edited by _Charles R Greathouse IV_, Apr 20 2010
|
