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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A010683 Let S(x,y) = number of lattice paths from (0,0) to (x,y) that use the step set { (0,1), (1,0), (2,0), (3,0), ....} and never pass below y = x. Sequence gives S(n-1,n) = number of 'Schröder' trees with n+1 leaves and root of degree 2. 13
1, 2, 7, 28, 121, 550, 2591, 12536, 61921, 310954, 1582791, 8147796, 42344121, 221866446, 1170747519, 6216189936, 33186295681, 178034219986, 959260792775, 5188835909516, 28167068630713, 153395382655222 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

a(n) = number of compound propositions "on the negative side" that can be made from n simple propositions.

Convolution of A001003 (the little Schröder numbers) with itself. - Emeric Deutsch, Dec 27 2003

Number of dissections of a convex polygon with n+3 sides that have a triangle over a fixed side (the base) of the polygon. - Emeric Deutsch, Dec 27 2003

a(n-1) = number of royal paths from (0,0) to (n,n), A006318, with exactly one diagonal step on the line y=x. - David Callan, Mar 14 2004

Number of short bushes (i.e., ordered trees with no vertices of outdegree 1) with n+2 leaves and having root of degree 2. Example: a(2)=7 because, in addition to the five binary trees with 6 edges (they do have 4 leaves) we have (i) two edges rb, rc hanging from the root r with three edges hanging from vertex b and (ii) two edges rb, rc hanging from the root r with three edges hanging from vertex c. - Emeric Deutsch, Mar 16 2004

The a(n) equal the Fi2 sums, see A180662, of Schröder triangle A033877. - Johannes W. Meijer, Mar 26 2012

Row sums of A144944 and of A186826. - Reinhard Zumkeller, May 11 2013

LINKS

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

A. Bacher, Directed and multi-directed animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365 [math.CO], 2013-2015. See R(t).

D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

Kevin Brown, Hipparchus on Compound Statements, 1994-2010.

Laurent Habsieger, Maxim Kazarian and Sergei Lando, On the second number of Plutarch, Am. Math. Monthly, Vol. 105, No. 5 (May, 1998), p. 446.

H. Kwong, On recurrences of Fahr and Ringel: An Alternate Approach, Fib. Quart., 48 (2010), 363-365; see p. 364.

J. W. Meijer, Famous numbers on a chessboard, Acta Nova, Volume 4, No.4, December 2010. pp. 589-598.

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

D. G. Rogers and L. W. Shapiro, Deques, trees and lattice paths, in Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference. Lecture Notes in Mathematics, Vol. 884 (Springer, Berlin, 1981), pp. 293-303. Math. Rev., 83g, 05038; Zentralblatt, 469(1982), 05005. See Figs. 7a and 8b.

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

Index entries for sequences related to trees

FORMULA

G.f.: ((1-t)^2-(1+t)*sqrt(1-6*t+t^2))/(8*t^2) = A(t)^2, with o.g.f. A(t) of A001003.

a(n) = (2/n)*sum(binomial(n, k)*binomial(n+k+1, k-1), k=1..n) = 2*hypergeom([1-n, n+3], [2], -1), n>=1. a(0)=1. - Wolfdieter Lang, Sep 12 2005.

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

Let M = the production matrix:

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

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

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

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

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

...

a(n) = upper entry in the vector (M(T))^n * [1,0,0,0,...]; where T is the transpose operation. - Gary W. Adamson, Jul 08 2011

Recurrence: (n+2)*(2*n-1)*a(n) = 6*(2*n^2-1)*a(n-1)-(n-2)*(2*n+1)*a(n-2). - Vaclav Kotesovec, Oct 07 2012

a(n) ~ sqrt(48+34*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 07 2012

Recurrence (an alternative): (n+2)*a(n)  = (4-n)*a(n-4) + 2*(2*n-5)*a(n-3) + 10*(n-1)*a(n-2) + 2*(2*n+1)*a(n-1), n>=4. - Fung Lam, Feb 18 2014

a(n) = (n+1)*hypergeom([1-n, -n], [3], 2). - Peter Luschny, Nov 19 2014

a(n) = (A001003(n) + A001003(n+1))/2 = sum(A001003(k) * A001003(n-k), k=0..n). - Johannes W. Meijer, Apr 29 2015

MAPLE

a := proc(n) local k: if n=0 then 1 else (2/n)*sum(binomial(n, k)* binomial(n+k+1, k-1), k=1..n) fi: end: seq(a(n), n=0..21); # Johannes W. Meijer, Mar 26 2012, revised Mar 31 2015

MATHEMATICA

f[ x_, y_ ] := f[ x, y ] = Module[ {return}, If[ x == 0, return = 1, If[ y == x-1, return = 0, return = f[ x, y-1 ] + Sum[ f[ k, y ], {k, 0, x-1} ] ] ]; return ]; Do[ Print[ Table[ f[ k, j ], {k, 0, j} ] ], {j, 10, 0, -1} ]

a[n_] := 2*Hypergeometric2F1[1-n, n+3, 2, -1]; a[0]=1; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 09 2014, after Wolfdieter Lang *)

PROG

(Haskell)

a010683 = sum . a144944_row  -- Reinhard Zumkeller, May 11 2013

(Sage)

a = lambda n: (n+1)*hypergeometric([1-n, -n], [3], 2)

[simplify(a(n)) for n in range(22)] # Peter Luschny, Nov 19 2014

(PARI) x='x+O('x^100); Vec(((1-x)^2-(1+x)*sqrt(1-6*x+x^2))/(8*x^2)) \\ Altug Alkan, Dec 19 2015

CROSSREFS

Cf. A001003.

Second right-hand column of triangle A011117.

A177010 has a closely-related g.f.

Sequence in context: A150658 A026770 A241371 * A276852 A293266 A150659

Adjacent sequences:  A010680 A010681 A010682 * A010684 A010685 A010686

KEYWORD

nonn,nice,easy

AUTHOR

Robert Sulanke (sulanke(AT)diamond.idbsu.edu), N. J. A. Sloane

EXTENSIONS

Minor edits by Johannes W. Meijer, Mar 26 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 19 17:22 EDT 2018. Contains 305594 sequences. (Running on oeis4.)