%I A006318 M1659
%S A006318 1,2,6,22,90,394,1806,8558,41586,206098,1037718,5293446,27297738,
%T A006318 142078746,745387038,3937603038,20927156706,111818026018,600318853926,
%U A006318 3236724317174,17518619320890,95149655201962,518431875418926
%N A006318 Large Schroeder numbers.
%C A006318 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 A006318 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
%C A006318 Twice A001003 (except for the first term).
%C A006318 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
%C A006318 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 A006318 "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 A006318 "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."
%C A006318 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
%C A006318 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
%C A006318 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
%C A006318 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
%C A006318 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
%C A006318 Triangle A144156 has row sums = A006318 with left border A001003. [From
Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]
%C A006318 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 A. Umar (aumarh(AT)squ.edu.om),
Oct 02 2008]
%D A006318 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A006318 M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product,
Discrete Math., 259 (2002), 19-36.
%D A006318 Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal
Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%D A006318 S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem
for succession rules, Discr. Math., 298 (2005), 142-154.
%D A006318 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 81, #21, (4), q_n.
%D A006318 E. Deutsch, A bijective proof of an equation linking the Schroeder numbers,
large and small, Discrete Math., 241 (2001), 235-240.
%D A006318 C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math.
9 (1974), 341-358.
%D A006318 S. Getu et al., How to guess a generating function, SIAM J. Discrete
Math., 5 (1992), 497-499.
%D A006318 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and
related issues, Discr. Math., 308 (2008), 1209-1221.
%D A006318 D. E. Knuth, The Art of Computer Programming, Vol. 1, Section 2.2.1,
Problem 11.
%D A006318 G. Kreweras, Sur les hi\'{e}rarchies de segments, Cahiers Bureau Universitaire
Recherche Op\'{e}rationnelle, Cahier 20, Inst. Statistiques, Univ.
Paris, 1973.
%D A006318 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 A006318 L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta
Math., 26 (1961), 223-229.
%D A006318 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 A006318 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
page 178 and also Problems 6.39 and 6.40.
%D A006318 P. R. Stein and M. S. Waterman, On some new sequences generalizing the
Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
%D A006318 R. A. Sulanke, Bijective recurrences concerning Schroeder paths, Electron.
J. Combin. 5 (1998), Research Paper 47, 11 pp.
%D A006318 M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008),
2544-2563.
%D A006318 Laradji, A. and Umar, A. Combinatorial results for semigroups of order-decreasing
partial transformations J. Integer Seq. 7 (2004), 04.3.8, 14 pp.
[From A. Umar (aumarh(AT)squ.edu.om), Oct 02 2008]
%D A006318 Laradji, A. and Umar, A. Asymptotic results for semigroups of order-preserving
partial transformations. Comm. Algebra 34 (2006), 1071-1075. [From
A. Umar (aumarh(AT)squ.edu.om), Oct 11 2008]
%H A006318 T. D. Noe, <a href="b006318.txt">Table of n, a(n) for n = 0..100</a>
%H A006318 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 A006318 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 A006318 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 A006318 R. Brignall, S. Huczynska and V. Vatter, <a href="http://arXiv.org/abs/
math.CO/0608391">Simple permutations and algebraic generating functions</
a>
%H A006318 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 A006318 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 A006318 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 A006318 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=159">
Encyclopedia of Combinatorial Structures 159</a>
%H A006318 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 A006318 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 A006318 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 A006318 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 A006318 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 A006318 M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">
Home Page</a> (contains copies of his papers)
%H A006318 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
SchroederNumber.html">Link to a section of The World of Mathematics.</
a>
%H A006318 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A006318 Laradji, A. and Umar, A., <a href="http://www.cs.uwaterloo.ca/journals/
JIS/">Combinatorial Results for Semigroups of Order-Decreasing Partial
Transformations </a>, Journal of Integer Sequences, Vol. 7 (2004),
Article 04.3.8. [From A. Umar (aumarh(AT)squ.edu.om), Oct 02 2008]
%H A006318 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
474
%F A006318 G.f.: (1-x-(1-6*x+x^2)^(1/2))/(2*x).
%F A006318 a(n) = 2*hypergeom([ -n+1, n+2], [2], -1). - Vladeta Jovovic (vladeta(AT)eunet.rs),
Apr 24 2003
%F A006318 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
%F A006318 The g.f. satisfies (1-x)A(x)-xA(x)^2 = 1. - Ralf Stephan (ralf(AT)ark.in-berlin.de),
Jun 30 2003
%F A006318 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
%F A006318 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
%F A006318 a(n)=sum(k=0, n, A000108(k)*binomial(n+k, n-k)) - Benoit Cloitre (benoit7848c(AT)orange.fr),
May 09 2004
%F A006318 a(n) = Sum_{k = 0..n} A011117(n, k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr),
Jul 10 2004
%F A006318 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
%F A006318 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
%F A006318 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.
%F A006318 Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008: 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]).
%F A006318 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 (pbarry(AT)wit.ie), Dec 08 2008]
%F A006318 G.f.: 1/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
[From Paul Barry (pbarry(AT)wit.ie), Jan 29 2009]
%F A006318 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]
%p A006318 Order := 24: solve(series((y-y^2)/(1+y),y)=x,y); # then A(x)=y(x)/x
%p A006318 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
%t A006318 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 A006318 InverseSeries[Series[(y-y^2)/(1+y), {y, 0, 24}], x] (* then A(x)=y(x)/
x *) - Len Smiley Apr 11 2000
%o A006318 (PARI) a(n)=polcoeff((1-x-sqrt(1-6*x+x^2+x^2*O(x^n)))/2,n+1)
%o A006318 (PARI) a(n)=if(n<1,1,sum(k=0,n,2^k*binomial(n,k)*binomial(n,k-1))/n)
%Y A006318 Apart from leading term, twice A001003. Cf. A025240.
%Y A006318 Sequences A085403, A086456, A103137, A112478 are essentially the same
sequence.
%Y A006318 Main diagonal of A033877.
%Y A006318 Cf. A088617, A060693. Row sums of A104219. Bisections give A138462, A138463.
%Y A006318 A144156 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]
%Y A006318 Contribution from A. Umar (aumarh(AT)squ.edu.om), Oct 11 2008: (Start)
%Y A006318 A123164(n+1) - A123164(n) = (2n+1)A006318 (n>=0);
%Y A006318 2A123164(n) = (n+1)A006318 - (n-1)A006318 (n>0). (End)
%Y A006318 Sequence in context: A049126 A049134 A086456 this_sequence A155069 A103137
A165546
%Y A006318 Adjacent sequences: A006315 A006316 A006317 this_sequence A006319 A006320
A006321
%K A006318 nonn,easy,core,nice
%O A006318 0,2
%A A006318 N. J. A. Sloane (njas(AT)research.att.com).
%E A006318 More terms from David W. Wilson (davidwwilson(AT)comcast.net)
|
