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

Author

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

Keywords

• nonn
• nice
• easy

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.
• Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
• 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

Crossrefs

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

Second right-hand column of triangle A011117.

A177010 has a closely-related g.f..

Programs

Haskell

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

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

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

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

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

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

Extensions

Minor edits by Johannes W. Meijer, Mar 26 2012