%I A001003 M2898 N1163
%S A001003 1,1,3,11,45,197,903,4279,20793,103049,518859,2646723,13648869,
%T A001003 71039373,372693519,1968801519,10463578353,55909013009,300159426963,
%U A001003 1618362158587,8759309660445,47574827600981,259215937709463,1416461675464871
%N A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan
numbers or little Schroeder numbers.
%C A001003 There are two schools of thought about the index for the first term.
I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.
%C A001003 a(n) = number of ways to insert parentheses in a string of n symbols.
The parentheses must be balanced but there is no restriction on the
number of pairs of parentheses. The number of letters inside a pair
of parentheses must be at least 2. Parentheses enclosing the whole
string are ignored.
%C A001003 Also length of list produced by a variant of the Catalan producing iteration:
replace each integer k by the list 0,1,..,k,k+1,k,...,1,0 and get
the length a(n) of the resulting (flattened) list after n iterations.
- Wouter Meeussen (wouter.meeussen(AT)pandora.be), Nov 11 2001
%C A001003 Stanley gives several other interpretations for these numbers.
%C A001003 Number of Schroeder paths of semilength n-1 (i.e. lattice paths from
(0,0) to (2n-2,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not
going below the x-axis) with no peaks at level 1. Example: a(3)=3
because among the six Schroeder paths of semilength two HH, UHD,
UUDD, HUD, UDH and UDUD, only the first three have no peaks at level
1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 27 2003
%C A001003 a(n+1)=number of Dyck n-paths in which the interior vertices of the ascents
are colored white or black. - David Callan (callan(AT)stat.wisc.edu),
Mar 14 2004
%C A001003 Number of possible schedules for n time slots in the first-come first-served
(FCFS) printer policy.
%C A001003 Also row sums of A086810, A033282 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr),
May 09 2004
%C A001003 a(n+1) = number of pairs (u,v) of same-length compositions of n, 0's
allowed in u but not in v and u dominates v (meaning u_1 >= v_1,
u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts
(2,2), (1+1,1+1), (2+0,1+1). - David Callan (callan(AT)stat.wisc.edu),
Jul 20 2005
%C A001003 The big Schroeder number (A006318) is the number of Schroeder paths from
(0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)).
These paths fall in two classes: those with steps on the main diagonal
and those without. These two classes are equinumerous and the number
of paths in either class is the little Schroeder number a(n) (half
the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu),
Oct 14 2005
%C A001003 With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each
upstep U getting one of 2 colors and each flatstep F getting one
of 3 colors. Example. With their colors immediately following upsteps/
flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D,
F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan
(callan(AT)stat.wisc.edu), Aug 16 2006
%C A001003 Triangle A144156 has row sums = A006318 with left border A001003. [From
Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]
%C A001003 Shifts left when INVERT transform applied twice. [From Alois P. Heinz
(heinz(AT)hs-heilbronn.de), Apr 01 2009]
%D A001003 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A001003 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A001003 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and
related issues, Discr. Math., 308 (2008), 1209-1221.
%D A001003 D. Arques and A. Giorgetti, Une bijection geometrique entre une famille
d'hypercartes et une famille de polygones enumerees par la serie
de Schroeder, Discrete Math., 217 (2000), 17-32.
%D A001003 P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989),
89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas,
Annals of Discrete Math., 43 (1989), 89-102.
%D A001003 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.
%D A001003 E. Deutsch, A bijective proof of an equation linking the Schroeder numbers,
large and small, Discrete Math., 241 (2001), 235-240.
%D A001003 I. M. H. Etherington, Some problems of non-associative combinations,
Edinburgh Math. Notes, 32 (1940), 1-6.
%D A001003 D. Foata and D. Zeilberger, A classic proof of a recurrence for a very
classical sequence, J. Comb Thy A 80 380-384 1997.
%D A001003 D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Problem 66.
%D A001003 G. Kreweras, Les preordres totaux compatibles avec un ordre partiel.
Math. Sci. Humaines No. 53 (1976), 5-30.
%D A001003 J. S. Lew, Polynomial enumeration of multidimensional lattices, Math.
Systems Theory, 12 (1979), 253-270.
%D A001003 T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial
formula for partitions of a polygon, for permanent preponderance
and for non-associative products, Bull. Amer. Math. Soc., 54 (1948),
352-360.
%D A001003 J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.
%D A001003 E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15
(1870), 361-376.
%D A001003 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
page 178.
%D A001003 H. N. V. Temperley and D. G. Rogers, A note on Baxter's generalization
of the Temperley-Lieb operators, pp. 324-328 of Combinatorial Mathematics
(Canberra, 1977), Lect. Notes Math. 686, 1978.
%D A001003 I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood
City, CA, 1991, p. 198.
%D A001003 C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
%D A001003 D. Gouyou-Beauchamps and B. Vauquelin, Deux proprietes combinatoires
des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.
%D A001003 M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math.,
185 (1998), 77-87.
%D A001003 Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the
Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article
06.1.1.
%D A001003 Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in
the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article
05.3.7.
%D A001003 Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal
Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%D A001003 Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal
of Integer Sequences, Vol. 8 (2005), Article 05.1.6.
%D A001003 Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted
Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article
06.1.7.
%H A001003 T. D. Noe, <a href="b001003.txt">Table of n, a(n) for n=0..199</a>
%H A001003 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.nrbook.com/
abramowitz_and_stegun/">Handbook of Mathematical Functions</a>, National
Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972
[alternative scanned copy].
%H A001003 Marcelo Aguiar and Walter Moreira, <a href="http://front.math.ucdavis.edu/
math.CO/0510169">Combinatorics of the free Baxter algebra</a>, see
Corollary 3.3.iii.
%H A001003 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 A001003 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 A001003 H. Bottomley, <a href="a001003.gif">Illustration of initial terms</a>
%H A001003 F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/NCC-html/
NCC.html">Combinatorics of Non-Crossing Configurations</a>, Studies
in Automatic Combinatorics, Volume II (1997).
%H A001003 W. Y. C. Chen, T. Mansour and S. H. F. Yan, <a href="http://arXiv.org/
abs/math.CO/0504342">Matchings avoiding partial patterns</a>
%H A001003 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 A001003 D. Foata and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/9805015">
[math/9805015] A Classic Proof of a Recurrence for a Very Classical
Sequence</a>
%H A001003 D. Foata and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/
mamarim/mamarimPDF/classic.pdf">A classic proof of a recurrence for
a very classical sequence</a>
%H A001003 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=42">
Encyclopedia of Combinatorial Structures 42</a>
%H A001003 D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://www.dsi.unifi.it/
~merlini/fun01.ps">Waiting patterns for a printer</a>, FUN with algorithm'01,
Isola d'Elba, 2001.
%H A001003 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 A001003 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 A001003 N. J. A. Sloane, <a href="http://arXiv.org/abs/math.CO/0312448">The On-Line
Encyclopedia of Integer Sequences</a>
%H A001003 L. M. Smiley, <a href="http://arXiv.org/abs/math.CO/9907057">Variants
of Schroeder Dissections</a>
%H A001003 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers.html">Hipparchus,
Plutarch, Schr"oder and Hough</a>, Am. Math. Monthly, Vol. 104, No.
4, p. 344, 1997.
%H A001003 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Bracketing.html">Link to a section of The World of Mathematics.</
a>
%H A001003 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
SuperCatalanNumber.html">Link to a section of The World of Mathematics.</
a>
%H A001003 <a href="Sindx_Par.html#parens">Index entries for sequences related to
parenthesizing</a>
%H A001003 N. J. A. Sloane, <a href="transforms.txt">Transforms</a> [From Alois
P. Heinz (heinz(AT)hs-heilbronn.de), Apr 01 2009]
%H A001003 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
69
%F A001003 a(n) = 3*a(n-1) + 2*A065096(n-2) (n>2). If g(x) = 1 + 3x + 11x^2 + 45x^3
+ ... + a(n)*x^n + ..., then g(x) = 1 + 3(x*g(x)) + 2(x*g(x))^2,
g(x)^2 = 1 + 6x + 31x^2 + 156x^3 + ... + A065096(n)*x^n + ... - Paul
D. Hanna (pauldhanna(AT)juno.com), Jun 10 2002
%F A001003 a(n+1) = -a(n) + 2*Sum_{k=1..n} a(k)*a(n+1-k). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr),
Jan 27 2004
%F A001003 The Hankel transform of this sequence gives A006125 = 1, 1, 2, 8, 64,
1024, ...; example : det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197;
11, 45, 197, 903]) = 2^6 = 64 . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr),
Mar 02 2004
%F A001003 a(n+1)=Sum_{k, 0, (n-1)/2} 2^k 3^(n-1-2k) binomial(n-1, 2k) CatalanNumber(k).
This formula counts colored Dyck paths by the same parameter by which
Touchard's identity counts ordinary Dyck paths: number of DDUs (U=up
step, D=down step). See also Gouyou-Beauchamps reference. - David
Callan (callan(AT)stat.wisc.edu), Mar 14 2004
%F A001003 a(n)=(1/(n+1))sum{k=0..n, C(n+1, k)C(2n-k, n)(-1)^k*2^(n-k)} [with offset
0]; a(n)=(1/(n+1))sum{k=0..n, C(n+1, k+1)C(n+k, k)(-1)^(n-k)*2^k}
[with offset 0]; a(n)=sum{k=0..n, (1/(k+1))*C(n, k)C(n+k, k)(-1)^(n-k)*2^k}
[with offset 0]; a(n)=sum{k=0..n, A088617(n, k)*(-1)^(n-k)*2^k} [with
offset 0]; - Paul Barry (pbarry(AT)wit.ie), May 24 2005
%F A001003 (n+1)*a(n)= (6*n-3)* a(n-1) -(n-2)*a(n-2) if n>1. a(0)= a(1)= 1.
%F A001003 G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x
+ x^2)) .
%F A001003 E.g.f. of a(n+1)= exp(3*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta
Jovovic (vladeta(AT)eunet.rs), Mar 31 2004
%F A001003 Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.
%F A001003 For n>=1, a(n)=sum(k=0, n, 2^k*N(n, k)) where N(n, k) =1/n*C(n, k)*C(n,
k+1) are the Narayana numbers (A001263) - Benoit Cloitre (benoit7848c(AT)orange.fr),
May 10 2003. This formula counts colored Dyck paths by number of
peaks, which is easy to see because the Narayana numbers count Dyck
paths by number of peaks and the number of peaks determines the number
of interior ascent vertices.
%F A001003 a(n) = Sum_{k=0..n} A088617(n, k)*2^k*(-1)^(n-k). - DELEHAM Philippe
(kolotoko(AT)wanadoo.fr), Jan 21 2004
%F A001003 For n > 0, a(n) = 1/(n+1) * sum_{k = 0 .. n-1} binomial(2*n-k, n)*binomial(n-1,
k). This formula counts colored Dyck paths (as above) by number of
white vertices. - David Callan (callan(AT)stat.wisc.edu), Mar 14
2004
%F A001003 a(n-1)=(diff(((1-x)/(1-2*x))^n, x$(n-1)))/n!|_{x=0}. (For a proof see
the comment on the unsigned row sums of triangle A111785.)
%F A001003 a(n)= (1/n)*sum(binomial(n, k)*binomial(n+k, k-1), k=1..n) = hypergeom([1-n,
n+2], [2], -1), n>=1. W. Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de),
Sep 12 2005.
%F A001003 a(m+n+1) = Sum_{k, k>=0} A110440(m, k)*A110440(n, k)*2^k = A110440(m+n,
0) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Sep 14 2005
%F A001003 Sum over partitions formula (reference Schroeder paper p. 362, eq. (1)
II). Number the partitions of n according to Abramowitz-Stegun p.
831-2 (see reference under A105805) with k=1..p(n)= A000041(n). For
n>=1: a(n-1)=sum(A048996(n,k)*a(1)^e(k, 1)*a(1)^e(k, 2)*...*a(n-2)^e(k,
n-1), k=2..p(n)) if the k-th partition of n in the mentioned order
is written as (1^e(k, 1), 2^e(k, 2), ..., (n-1)e(k, n-1)). Note that
the first (k=1) partition (n^1) has to be omitted. W. Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_D\
OT_de), Aug 23 2005.
%F A001003 Starting (1, 3, 11, 45,...), = row sums of triangle A126216 = A001263
* [1, 2, 4, 8, 16,...]. - Gary W. Adamson (qntmpkt(AT)yahoo.com),
Nov 30 2007
%F A001003 Contribution from Paul Barry (pbarry(AT)wit.ie), May 15 2009: (Start)
%F A001003 G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).
%F A001003 G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
%F A001003 G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction).
(End)
%e A001003 a(2) = 3: abc, a(bc), (ab)c; a(3) = 11: abcd, (ab)cd, a(bc)d, ab(cd),
(ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, ((ab)c)d.
%e A001003 Sum over partitions formula: a(3) = 2*a(0)*a(2) + 1*a(1)^2 + 3*(a(0)^2)*a(1)
+ 1*a(0)^4 = 6 + 1 + 3 + 1 = 11.
%p A001003 t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1,x,40);
%p A001003 BB:=(1+z-sqrt(1-6*z+z^2))/4: BBser:=series(BB, z=0, 26): seq(coeff(BBser,
z, n), n=1..24); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com),
Apr 10 2007
%p A001003 seq (sum(binomial(n,j)*binomial(n+j,n-1), j=0..n)/(2*n), n=1..23); -
Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 10 2007
%p A001003 invtr:= proc(p) local b; b:= proc(n) option remember; local i; `if` (n<1,
1, add (b(n-i) *p(i-1), i=1..n+1)) end; end: a:='a': f:= (invtr@@2)(a):
a:= proc (n) if n<0 then 1 else f(n-1) fi end: seq (a(n), n=0..30);
[From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Apr 01 2009]
%t A001003 Table[Length[Flatten[Nest[ #/.a_Integer:> Join[Range[0, a+1], Range[a,
0, -1]]&, {0}, n]]], {n, 0, 10}]
%t A001003 Sch[ 0 ]=Sch[ 1 ]=1; Sch[ n_Integer ] := Sch[ n ]=(3(2n-1)Sch[ n-1 ]-(n-2)Sch[
n-2 ])/(n+1); Array[ Sch[ #-1 ]&, 20 ]
%o A001003 (PARI) {a(n)= if(n<1, n==0, sum(k=0, n, 2^k*binomial(n,k)* binomial(n,
k-1) )/(2*n))} /* Michael Somos Mar 31 2007 */
%o A001003 (PARI) {a(n)= local(A); if(n<1, n==0, n--; A= x*O(x^n); n!*simplify(polcoeff(
exp(3*x +A)* besseli(1, 2*x* quadgen(8) +A), n)))} /* Michael Somos
Mar 31 2007 */
%o A001003 (PARI) {a(n)= if(n<0, 0, n++; polcoeff( serreverse( (x -2*x^2)/(1 -x)
+x*O(x^n)), n))} /* Michael Somos Mar 31 2007 */
%Y A001003 See A000108, A001190, A001699, A000081 for other ways to count parentheses.
Cf. A000311, A010683, A065096.
%Y A001003 Row sums of A033877.
%Y A001003 Cf. A054726, A059435, A025240, A080243, A085403, A086456, A086616, A035011.
%Y A001003 Right-hand column 1 of triangle A011117.
%Y A001003 Convolution triangle A011117.
%Y A001003 A006318(n)= 2*(n) if n>0.
%Y A001003 A144156 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 12 2008]
%Y A001003 Sequence in context: A146086 A049177 A080243 this_sequence A151131 A151132
A151133
%Y A001003 Adjacent sequences: A001000 A001001 A001002 this_sequence A001004 A001005
A001006
%K A001003 nonn,easy,nice,core
%O A001003 0,3
%A A001003 N. J. A. Sloane (njas(AT)research.att.com).
|
