login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006318 Large Schroeder numbers.
(Formerly M1659)
172
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 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.

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).

Eric W. Weisstein comments that the Schroeder 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 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

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 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

a(n) is the 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

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 order-preserving and order-decreasing partial transformations (of an n-chain). Equivalently, it is the order of the Schroeder monoid, PC sub n. - Abdullahi Umar, Oct 02 2008

Sum_{n >= 0} a(n)/10^n - 1 = [9-sqrt(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^{n-k} is irreducible modulo some prime p < n*(n+1). - Zhi-Wei Sun, Apr 07 2013

From Jon Perry, May 24 2013: (Start)

Consider a Pascal triangle variant where T(n, k) = T(n, k-1) + T(n-1, k-1) + T(n-1, 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

REFERENCES

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

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), 19-36.

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.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

P. Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

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.

J. Cigler, Hankel determinants of some polynomial sequences, http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf, 2012.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81, #21, (4), q_n.

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. 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, 4108-4115. See p. 4109.

E. Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.

C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.

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

M. Dziemianczuk, Generalizing Delannoy numbers via counting weighted lattice paths, INTEGERS, 13 (2013), #A54.

Egge, Eric S., Restricted signed permutations counted by the Schroeder numbers. Discrete Math. 306 (2006), 552-563. [Many applications of these numbers.]

S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.

Étienne Ghys, Intersecting curves, 2013, http://perso.ens-lyon.fr/ghys/articles/intersectingcurves.pdf; Amer. Math. Monthly, 120 (2013), 232-242.

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, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

Guruswami, Venkatesan, Enumerative aspects of certain subclasses of perfect graphs. Discrete Math. 205 (1999), 97-117.

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 Schroeder number, Discrete Math. 218 (2000) 121-130.

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.

G. Kreweras, Sur les hi\'{e}rarchies de segments, Cahiers Bureau Universitaire Recherche Op\'{e}rationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973.

Laradji, A. and Umar, A. Asymptotic results for semigroups of order-preserving partial transformations. Comm. Algebra 34 (2006), 1071-1075. - Abdullahi Umar, Oct 11 2008

L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.

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.

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.

S.-n. Zheng and S.-l. Yang, On the-Shifted Central Coefficients of Riordan Matrices, Journal of Applied Mathematics, Volume 2014, Article ID 848374, 8 pages; http://dx.doi.org/10.1155/2014/848374

LINKS

Fung Lam, Table of n, a(n) for n = 0..2000 (terms 0..100 by T. D. Noe)

A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, R. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-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 length-increasing forbidden subsequences

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free 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 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

J. Bloom, A. Burstein, Egge triples and unbalanced Wilf-equivalence, arXiv:1410.0230, 2014.

O. Bodini, A. Genitrini and F. Peschanski, The Combinatorics of Non-determinism, In proc. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'13), Leibniz International Proceedings in Informatics, pp 425-436, 2013.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

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

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 Wilf-equivalence, arXiv:1402.3842, 2014.

D. Callan, An application of a bijection of Mansour, Deng, and Du, arXiv preprint arXiv:1210.6455, 2012.

F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, 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

M. Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87-103.

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.

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.

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.

Li Guo and Jun Pei, Averaging algebras, Schroeder 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, q-Narayana 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(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.

Laradji, A. and Umar, A. Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8

Philippe Leroux, Hochschild two-cocycles 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, 189-241.

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

E. Pergola and R. A. Sulanke, Schroeder 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), 261-272.

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 Schroeder paths, Electron. J. Combin. 5 (1998), Research Paper 47, 11 pp.

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.2486.

Zhi-Wei 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 China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258. - N. J. A. Sloane, Dec 28 2012

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. - N. J. A. Sloane, Jan 03 2013\

Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic 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, Schroeder Number

J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247-262.

J. Winter, M. M. Bonsangue and J. J. M. M. Rutten, Context-free coalgebras, 2013.

Index entries for "core" sequences

FORMULA

G.f.: (1-x-(1-6*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, k-1)). - Benoit Cloitre, May 10 2003

The g.f. satisfies (1-x)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(n-1) + sum(i = 1, n-1, a(i)*a(n-i)). - Benoit Cloitre, Mar 16 2004

a(n) = sum(k = 0, n, A000108(k)*binomial(n+k, n-k)). - 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[n-1])/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) - (n-1)a(n-1) (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, 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 E John, Oct 19 2006

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

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). - Paul Barry, Dec 08 2008

G.f.: 1/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(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) = (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.

Consequently, with H(x) = 1/ (dG(x)/dx) = (2+3*x+x^2)^2 / (2-x^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(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

Recurrence: (n-2)*a(n-2) - 3*(2*n-1)*a(n-1) + (n+1)*a(n) = 0. - Vaclav Kotesovec, Oct 05 2012

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

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

a(n+1) = a(n) + sum (a(k)*(n-k): k = 0..n). - Reinhard Zumkeller, Nov 13 2012

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

a(-1-n) = 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*(6-x)*(2*k-1)/(x*(6-x)*(2*k-1) + 2*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 16 2013

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((y-y^2)/(1+y), y)=x, y); # then A(x)=y(x)/x

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, 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[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

A006318 := n-> add(binomial(n+k, n-k) * binomial(2*k, k)/(k+1), k=0..n): seq(A006318(n), n=0..22); # Johannes W. Meijer, Jul 14 2013

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 *)

PROG

(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 */

(PARI) {a(n) = if( n<1, 1, sum( k=0, n, 2^k * binomial( n, k) * binomial( n, k-1)) / 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[k-1]

            h += 1;

        else :

            for k in range(1, h, 1) : D[k] += D[k-1]

            R.append(D[h-1]);

        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*n-9)-(n-3)*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

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson

Edited by Charles R Greathouse IV, Apr 20 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 26 04:18 EST 2014. Contains 250017 sequences.