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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.
(Formerly M2898 N1163)
133
1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

a(n) = number of ways to insert parentheses in a string of n+1 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.

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, Nov 11 2001

Stanley gives several other interpretations for these numbers.

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, Dec 27 2003

a(n+1)=number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004

Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.

Also row sums of A086810, A033282. - Philippe Deléham, May 09 2004

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, Jul 20 2005

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

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, Aug 16 2006

Triangle A144156 has row sums = A006318 with left border A001003. - Gary W. Adamson, Sep 12 2008

Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009

a(n) = A144944(n,n) = A186826(n,0). - Reinhard Zumkeller, May 11 2013

Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014

REFERENCES

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.

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

Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.- From N. J. A. Sloane, Oct 08 2012

N. Bernasconi et al., On properties of random dissections and triangulations, Combinatorica, 30 (6) (2010), 627-654.

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.

Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155, also p. 179, line -9. - N. J. A. Sloane, Apr 18 2014

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.

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. - From N. J. A. Sloane, Jun 08 2012

J. Cigler, Continued fractions associated with q-Schroeder-like numbers, http://homepage.univie.ac.at/johann.cigler/preprints/schroeder-rama.pdf, 2012. - From N. J. A. Sloane, Dec 29 2012

J. Cigler, Hankel determinants of some polynomial sequences, http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf, 2012. - From N. J. A. Sloane, Jan 02 2013

C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.

D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012

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

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

Drmota, Michael; de Mier, Anna; Noy, Marc. Extremal statistics on non-crossing configurations. Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (2). - N. J. A. Sloane, May 18 2014

I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing permutations, Discrete Math., 204 (1999), 203-229.

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997

Gabriel, Nathan; Peske, Katherine; Pudwell, Lara; Tay, Samuel, Pattern avoidance in ternary trees. J. Integer Seq. 15 (2012), no. 1, Article 12.1.5, 20 pp.

D. Gouyou-Beauchamps and B. Vauquelin, Deux proprietes combinatoires des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.

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

P.-Y. Huang, S.-C. Liu, Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.

M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.

D. E. Knuth, The Art of Computer Programming, Vol. 1, various sections (e.g. p. 534 of 2nd ed.).

D. E. Knuth, The Art of Computer Programming, Vol. 1, (p. 539 of 3rd ed.).

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.6, Problem 66, p. 479.

G. Kreweras, Les preordres totaux compatibles avec un ordre partiel. Math. Sci. Humaines No. 53 (1976), 5-30.

J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1979), 253-270.

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.

R. A. Perez, A brief but historic article of Siegel, Notices AMS, 58 (2011), 558-566.

L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), http://faculty.valpo.edu/lpudwell/slides/notredame.pdf, 2012. - From N. J. A. Sloane, Jan 03 2013

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.

E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15 (1870), 361-376.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

M. Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101, http://ami.ektf.hu.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 178.

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.

I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 198.

Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.

Wen-jin Woan, A Relation Between Restricted and Unrestricted Weighted Motzkin Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.7.

E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3.

LINKS

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

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

Marcelo Aguiar and Walter Moreira, Combinatorics of the free Baxter algebra, see Corollary 3.3.iii.

A. Bacher, Directed and multi-directed animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365, 2013. - From N. J. A. Sloane, Feb 04 2013

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths

P. Barry, Comparing two matrices of generalized moments defined by continued fraction expansions, arXiv preprint arXiv:1311.7161, 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

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

H. Bottomley, Illustration of initial terms

Mathilde Bouvel, Cedric Chauve, Marni Mishna and Dominique Rossin, Average-case analysis of perfect sorting by reversals, Arxiv preprint arXiv:1201.0940, 2012

F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).

W. Y. C. Chen, T. Mansour and S. H. F. Yan, Matchings avoiding partial patterns

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

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 69, 474-475, etc.

D. Foata and D. Zeilberger, [math/9805015] A Classic Proof of a Recurrence for a Very Classical Sequence

D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence

Evangelos Georgiadis, Akihiro Munemasa and Hajime Tanaka, A note on super Catalan numbers, Jan 08 2011.

Olivier Gérard, Illustration of initial terms (a)

Olivier Gérard, Illustration of initial terms (b)

Li Guo and Jun Pei, Averaging algebras, Schroeder numbers and rooted trees, arXiv preprint arXiv:1401.7386, 2014

Guo-Niu Han, Enumeration of Standard Puzzles

Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]

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.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 42

V. V. Kruchinin and D. V. Kruchinin, A Method for Obtaining Generating Function for Central Coefficients of Triangles, Arxiv preprint arXiv:1206.0877, 2012. - From N. J. A. Sloane, Oct 28 2012

Peter Luschny, The Lost Catalan Numbers And The Schröder Tableaux.

D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.

W. Mlotkowski and K. A. Penson, The probability measure corresponding to 2-plane trees, ArXiv preprint arXiv:1304.6544, 2013.

G. Muntingh, Implicit Divided Differences, Little Schroder Numbers and Catalan Numbers, Arxiv preprint arXiv:1204.2709, 2012. - From N. J. A. Sloane, Oct 05 2012

Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959, 2012.

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014

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

O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, arXiv:1209.1355 [math.CO].

O. Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory A, 125 (2014), 357-378. - From Oliver Pechenik, Apr 22 2014

E. Pergola and R. A. Sulanke, Schroeder Triangles, Paths and Parallelogram Polyominoes, J. Integer Sequences, 1 (1998), #98.1.7.

N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences

N. J. A. Sloane, Transforms

L. M. Smiley, Variants of Schroeder Dissections

R. P. Stanley, Hipparchus, Plutarch, Schr"oder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

Y. Sun, Z. Wang, Consecutive pattern avoidances in non-crossing trees, Graph. Combinat. 26 (2010) 815-832

Eric Weisstein's World of Mathematics, Bracketing

Eric Weisstein's World of Mathematics, Super Catalan Number

Wikipedia, Schroeder-Hipparchus numbers.

Index entries for sequences related to parenthesizing

FORMULA

(n+1) * a(n) = (6*n-3) * a(n-1) - (n-2) * a(n-2) if n>1. a(0) = a(1) = 1.

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, Jun 10 2002

a(n+1) = -a(n) + 2*Sum_{k=1..n} a(k)*a(n+1-k). - Philippe Deléham, Jan 27 2004

G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x + x^2)).

a(n) ~ W*(3+sqrt(8))^n*n^(-3/2) where W = (1/4)*sqrt((sqrt(18)-4)/Pi) [See Knuth I, p. 534, or Perez. Note that the formula on line 3, page 475 of Flajolet and Sedgewick seems to be wrong - it has to be multiplied by 2^(1/4).] - N. J. A. Sloane, Apr 10 2011

Right asymptotic for A001003 is a(n) ~ W*(3+sqrt(8))^n*n^(-3/2), where W = (1+sqrt(2))/(2*2^(3/4)*sqrt(pi)) = 0.404947065905750651736243... Result in book by D. Knuth (p. 539 of 3rd edition, exercise 12) is for sequence b(n), but a(n) = b(n+1)/2. Therefore is asymptotic a(n) ~ b(n) * (3+sqrt(8))/2. - Vaclav Kotesovec, Sep 09 2012

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. - Philippe Deléham, Mar 02 2004

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, Mar 14 2004

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, May 24 2005

E.g.f. of a(n+1) is exp(3*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta Jovovic, Mar 31 2004

Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.

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

a(n) = Sum_{k=0..n} A088617(n, k)*2^k*(-1)^(n-k). - Philippe Deléham, Jan 21 2004

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, Mar 14 2004

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

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. - Wolfdieter Lang, Sep 12 2005

a(m+n+1) = Sum_{k>=0} A110440(m, k)*A110440(n, k)*2^k = A110440(m+n, 0). - Philippe Deléham, Sep 14 2005

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. - Wolfdieter Lang, Aug 23 2005

Starting (1, 3, 11, 45,...), = row sums of triangle A126216 = A001263 * [1, 2, 4, 8, 16,...]. - Gary W. Adamson, Nov 30 2007

From Paul Barry, May 15 2009: (Start)

G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).

G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).

G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction). (End)

G.f.: 1 / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / ... )))). - Michael Somos, May 19 2013

a(n) = (LegendreP(n+1,3)-3*LegendreP(n,3))/(4*n) for n>0. - Mark van Hoeij, Jul 12 2010

a(n) = upper left term in M^n, where M is the production matrix:

1, 1, 0, 0, 0, 0,...

2, 2, 2, 0, 0, 0,...

1, 1, 1, 1, 0, 0,...

2, 2, 2, 2, 2, 0,...

1, 1, 1, 1, 1, 1,...

...

- Gary W. Adamson, Jul 08 2011

a(n) is the sum of top row terms of Q^(n-1), where Q is the infinite square production matrix:

1, 2, 0, 0, 0,...

1, 1, 2, 0, 0,...

1, 1, 1, 2, 0,...

1, 1, 1, 1, 2,...

... - Gary W. Adamson, Aug 23 2011

Let h(t) = (1-t)^2/(2*(1-t)^2-1) = 1/(1-(2*t+3*t^2+4*t^3+...)), an o.g.f. for A003480, then for A001003 a(n) = (1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=1. (Cf. A086810.) - Tom Copeland, Sep 06 2011

A006318(n) = 2*a(n) if n>0. - Michael Somos, Mar 31 2007

BINOMIAL transform is A118376 with offset 0. REVERT transform is A153881. INVERT transform is A006318. INVERT transform of A114710. HANKEL transform is A139685. PSUM transform is A104858. - Michael Somos, May 19 2013

G.f.: 1 + x/(Q(0) - x) 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(n)=(-1)^n*LegendreP(n,-1,-3)/sqrt(2), n>0, LegendreP(n,a,b) is the Legendre function. - Karol A. Penson, Jul 06 2013

Integral representation as n-th moment of a positive weight function W(x) = W_a(x) + W_c(x), where W_a(x) = Dirac(x)/2, is the discrete (atomic) part, and  W_c(x) = sqrt(8-(x-3)^2)/(4*Pi*x) is the continuous part of W(x) defined on (3 sqrt(8),3+sqrt(8)): a(n) = int( x^n*W_a(x), x=-eps..eps ) + int( x^n*W_c(x), x = 3-sqrt(8)..3+sqrt(8) ), for any eps>0, n>=0. W_c(x) is unimodal, of bounded variation and W_c(3-sqrt(8)) = W_c(3+sqrt(8)) = 0. Note that the position of the Dirac peak (x=0) lies outside support of W_c(x). - Karol A. Penson and Wojciech Mlotkowski, Aug 05 2013

EXAMPLE

1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 197*x^5 + 903*x^6 + 4279*x^7 + 20793*x^8 + ...

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.

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.

a(4) = 45 since the top row of Q^3 = (11, 14, 12, 8, 0, 0, 0,...); (11 + 14 + 12 + 8) = 45.

MAPLE

t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1, x, 40);

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, Apr 10 2007

seq (sum(binomial(n, j)*binomial(n+j, n-1), j=0..n)/(2*n), n=1..23); # Zerinvary Lajos, Apr 10 2007

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); # Alois P. Heinz, Apr 01 2009

# Computes n -> [a[0], a[1], .., a[n]]

A001003_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;

for w from 1 to n do a[w] := a[w-1]+2*add(a[j]*a[w-j-1], j=1..w-1) od;

convert(a, list) end: A001003_list(100); # Peter Luschny, May 17 2011

MATHEMATICA

Table[Length[Flatten[Nest[ #/.a_Integer:> Join[Range[0, a + 1], Range[a, 0, -1]] &, {0}, n]]], {n, 0, 10}]; 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, 24, 0]

a[n_] := Hypergeometric2F1[-n + 1, n + 2, 2, -1]; a[0] = 1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 09 2011, after Vladeta Jovovic *)

PROG

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

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

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

(Python) The objective of this implementation is efficiency.

# n -> [a(0), a(1), ..., a(n)]

def A001003_list(n):

....a = [0 for i in range(0, n)]

....a[0] = 1

....for w in range(1, n):

........s = 0

........for j in range(1, w):

............s += a[j]*a[w-j-1]

........a[w] = a[w-1]+2*s

....return a

# Peter Luschny, May 17 2011

(Sage) # Generalized algorithm of L. Seidel

def A001003_list(n) :

    D = [0]*(n+1); D[1] = 1/2

    b = True; h = 2; R = [1]

    for i in range(2*n-2) :

        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

A001003_list(24) # Peter Luschny, Jun 02 2012

(Haskell)

a001003 = last . a144944_row  -- Reinhard Zumkeller, May 11 2013

(Python)

from gmpy2 import divexact

A001003 = [1, 1]

for n in range(3, 10**3):

....A001003.append(divexact(A001003[-1]*(6*n-9)-(n-3)*A001003[-2], n))

# Chai Wah Wu, Sep 01 2014

CROSSREFS

See A000108, A001190, A001699, A000081 for other ways to count parentheses.

Cf. A000311, A006318, A010683, A065096.

Row sums of A033877.

Cf. A054726, A059435, A025240, A080243, A085403, A086456, A086616, A035011.

Right-hand column 1 of triangle A011117.

See also convolution triangle A011117.

Cf. A144156.

Sequence in context: A049177 A217889 A217890 * A080243 A151131 A151132

Adjacent sequences:  A001000 A001001 A001002 * A001004 A001005 A001006

KEYWORD

nonn,easy,nice,core

AUTHOR

N. J. A. Sloane

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 September 20 04:05 EDT 2014. Contains 246983 sequences.