

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(n1,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) 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(n1) = 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 multidirected animals on the square lattice with next nearest neighbor edges, arXiv preprint arXiv:1301.1365 [math.CO], 20132015. 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, 19942010.
Shishuo Fu, Zhicong Lin, and Yaling Wang, Refined Wilfequivalences 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), 363365; see p. 364.
J. W. Meijer, Famous numbers on a chessboard, Acta Nova, Volume 4, No.4, December 2010. pp. 589598.
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. 293303. 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.: ((1t)^2(1+t)*sqrt(16*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, k1), k=1..n) = 2*hypergeom([1n, 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
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)
Dfinite with recurrence: (n+2)*(2*n1)*a(n) = 6*(2*n^21)*a(n1)(n2)*(2*n+1)*a(n2).  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) = (4n)*a(n4) + 2*(2*n5)*a(n3) + 10*(n1)*a(n2) + 2*(2*n+1)*a(n1), n>=4.  Fung Lam, Feb 18 2014
a(n) = (n+1)*hypergeom([1n, n], [3], 2).  Peter Luschny, Nov 19 2014
a(n) = (A001003(n) + A001003(n+1))/2 = sum(A001003(k) * A001003(nk), 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, k1), 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 == x1, return = 0, return = f[ x, y1 ] + Sum[ f[ k, y ], {k, 0, x1} ] ] ]; 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[1n, n+3, 2, 1]; a[0]=1;
Table[a[n], {n, 0, 21}] (* JeanFranç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([1n, n], [3], 2)
[simplify(a(n)) for n in range(22)] # Peter Luschny, Nov 19 2014
(PARI) x='x+O('x^100); Vec(((1x)^2(1+x)*sqrt(16*x+x^2))/(8*x^2)) \\ Altug Alkan, Dec 19 2015


CROSSREFS

Cf. A001003.
Second righthand column of triangle A011117.
A177010 has a closelyrelated 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



