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.

1, 2, 7, 28, 121, 550, 2591, 12536, 61921, 310954, 1582791, 8147796, 42344121, 221866446, 1170747519, 6216189936, 33186295681, 178034219986, 959260792775, 5188835909516, 28167068630713, 153395382655222

Offset

0,2

Comments

a(n) is the 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, and 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.

Shishuo Fu, Zhicong Lin, and Yaling Wang, Refined Wilf-equivalences by Comtet statistics, arXiv:2009.04269 [math.CO], 2020.

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.

From Wolfdieter Lang, Sep 12 2005: (Start)

a(n) = (2/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k+1, k-1).

a(n) = 2*hypergeometric2F1([1-n, n+3], [2], -1), n>=1. a(0)=1. (End)

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

From Gary W. Adamson, Jul 08 2011: (Start)

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) is the upper entry in the vector (M(T))^n * [1,0,0,0,...]; where T is the transpose operation. (End)

D-finite with 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)*hypergeometric2F1([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)*add(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}] *)
Table[f[x, x+1], {x, 0, 21}]
(* Second program: *)
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
(Magma) [n le 2 select n else (6*(2*(n-1)^2-1)*Self(n-1) - (n-3)*(2*n-1)*Self(n-2))/((n+1)*(2*n-3)): n in [1..30]]; // G. C. Greubel, Mar 11 2023

Crossrefs

Cf. A001003, A006318, A033877, A144944, A180662, A186826.

Second right-hand column of triangle A011117.

A177010 has a closely-related g.f..

Sequence in context: A026770 A241371 A368970 * A276852 A352861 A293266

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