|
| |
|
|
A006318
|
|
Large Schroeder numbers.
(Formerly M1659)
|
|
152
| |
|
|
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; 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 (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 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
Triangle A144156 has row sums = A006318 with left border A001003. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 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. [From A. Umar (aumarh(AT)squ.edu.om), Oct 02 2008]
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]
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]
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]
|
|
|
REFERENCES
| M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
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.
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.
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.
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.
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.
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.
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. 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]
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]
L. Moser and W. Zayachkowski, Lattice paths with diagonal steps, Scripta Math., 26 (1961), 223-229.
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.
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.
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.
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.
J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247-262.
|
|
|
LINKS
| 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.
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
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 474.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 159
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
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, Schroeder Number
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 (vladeta(AT)eunet.rs), 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
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). - 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.
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]).
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]
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]
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]
Logarithmic derivative yields A002003. [From Paul D. Hanna (pauldhanna(AT)juno.com), 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
Contribution from Tom Copeland, Sept 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
Conjecture: (n+1)*a(n) +(n+3)*a(n-1) +(n+19)*a(n-2) +7*(87-35*n)*a(n-3)+ 42*(n-4)*a(n-4) = 0. - R. J. Mathar, Nov 14 2011
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
|
|
|
EXAMPLE
| a(3) = 22 since the top row of Q^n = (6, 6, 6, 4, 0, 0, 0,...); where 22 = (6 + 6 + 6 + 4)
|
|
|
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 (zerinvarylajos(AT)yahoo.com), 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
|
|
|
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] (* From Harvey P. Dale, May 01 2011 *)
|
|
|
PROG
| (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)}
|
|
|
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.
A144156 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]
Contribution from A. Umar (aumarh(AT)squ.edu.om), Oct 11 2008: (Start)
A123164(n+1) - A123164(n) = (2n+1)A006318 (n>=0);
2 A123164(n) = (n+1)A006318(n) - (n-1)A006318(n-1) (n>0). (End)
Cf. A002003. [From Paul D. Hanna (pauldhanna(AT)juno.com), Oct 25 2010]
Row sums of A175124.
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 (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from David W. Wilson (davidwwilson(AT)comcast.net)
Edited by Charles R Greathouse IV (charles.greathouse(AT)case.edu), Apr 20 2010
|
| |
|
|
