0,2

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

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 (callan(AT)stat.wisc.edu), Mar 14 2004

Twice A001003 (except for the first term).

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 (callan(AT)stat.wisc.edu), Aug 02 2004

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.

"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 Weisstein (http://mathworld.wolfram.com/Schroeder.html) comments that the Schroeder numbers bear the relationship to the Delannoy numbers [A001850] as the Catalan numbers [A000108] do to the binomial coefficients."

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 (callan(AT)stat.wisc.edu), Jun 07 2006

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 (callan(AT)stat.wisc.edu), Jul 14 2006

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 (callan(AT)stat.wisc.edu), Aug 16 2006

a(n)=number of separable permutations, i.e. permutations avoiding 2413 and 3142, see Shapiro and Stephens. - Vince Vatter (vince(AT)mcs.st-and.ac.uk), 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 DELEHAM (kolotoko(AT)wanadoo.fr), Sep 03 2006

M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.

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

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

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

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.

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

N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

D. E. Knuth, The Art of Computer Programming, Vol. 1, Section 2.2.1, Problem 11.

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

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

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.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178 and also Problems 6.39 and 6.40.

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

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

T. D. Noe, Table of n, a(n) for n = 0..100

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

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]

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

S.-P. Eu and T.-S. Fu, A simple proof of the Aztec diamond problem

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 159

J.-C. Novelli and J.-Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, to appear in Fundamenta Mathematicae

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.

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

M. S. Waterman, Home Page (contains copies of his papers)

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for "core" sequences

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 (vladeta(AT)Eunet.yu), 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 (benoit7848c(AT)orange.fr), May 10 2003

The g.f. satisfies (1-x)A(x)-xA(x)^2 = 1. - Ralf Stephan (ralf(AT)ark.in-berlin.de), Jun 30 2003

Row sums of A088617 and A060693. a(n) = sum (k=0..n, C(n+k, n)*C(n, k)/k+1). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 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 (benoit7848c(AT)orange.fr), Mar 16 2004

a(n)=sum(k=0, n, A000108(k)*binomial(n+k, n-k)) - Benoit Cloitre (benoit7848c(AT)orange.fr), May 09 2004

a(n) = Sum_{k = 0..n} A011117(n, k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 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 (callan(AT)stat.wisc.edu), 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 DELEHAM (kolotoko(AT)wanadoo.fr), Sep 03 2006

Comment from Peter John (peter.john(AT)tu-ilmenau.de), Oct 19 2006: 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.

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 (zerinvarylajos(AT)yahoo.com), Apr 10 2007

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

(PARI) a(n)=polcoeff((1-x-sqrt(1-6*x+x^2+x^2*O(x^n)))/2, n+1)

(PARI) a(n)=if(n<1, 1, sum(k=0, n, 2^k*binomial(n, k)*binomial(n, k-1))/n)

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.

Sequence in context: A049126 A049134 A086456 this_sequence A103137 A053617 A089449

Adjacent sequences: A006315 A006316 A006317 this_sequence A006319 A006320 A006321

nonn,easy,core,nice

njas

More terms from David W. Wilson (davidwwilson(AT)comcast.net)