A010683 - OEIS

%I #111 Jul 30 2024 05:34:48

%S 1,2,7,28,121,550,2591,12536,61921,310954,1582791,8147796,42344121,

%T 221866446,1170747519,6216189936,33186295681,178034219986,

%U 959260792775,5188835909516,28167068630713,153395382655222

%N 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.

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

%C Convolution of A001003 (the little Schröder numbers) with itself. - _Emeric Deutsch_, Dec 27 2003

%C 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

%C 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

%C 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

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

%C Row sums of A144944 and of A186826. - _Reinhard Zumkeller_, May 11 2013

%H T. D. Noe, <a href="/A010683/b010683.txt">Table of n, a(n) for n=0..200</a>

%H A. Bacher, <a href="http://arxiv.org/abs/1301.1365">Directed and multi-directed animals on the square lattice with next nearest neighbor edges</a>, arXiv preprint arXiv:1301.1365 [math.CO], 2013-2015. See R(t).

%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="http://arxiv.org/abs/1503.05242">Colored partitions of a convex polygon by noncrossing diagonals</a>, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

%H Kevin Brown, <a href="http://www.mathpages.com/home/kmath397/kmath397.htm">Hipparchus on Compound Statements</a>, 1994-2010.

%H Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, <a href="https://arxiv.org/abs/2407.19583">Pattern-avoiding Cayley permutations via combinatorial species</a>, arXiv:2407.19583 [math.CO], 2024.

%H Shishuo Fu, Zhicong Lin, and Yaling Wang, <a href="https://arxiv.org/abs/2009.04269">Refined Wilf-equivalences by Comtet statistics</a>, arXiv:2009.04269 [math.CO], 2020.

%H Laurent Habsieger, Maxim Kazarian and Sergei Lando, <a href="http://www.jstor.org/stable/3109806">On the second number of Plutarch</a>, Am. Math. Monthly, Vol. 105, No. 5 (May, 1998), p. 446.

%H H. Kwong, <a href="https://www.fq.math.ca/Papers1/48-4/Kwong.pdf">On recurrences of Fahr and Ringel: An Alternate Approach</a>, Fib. Quart., 48 (2010), 363-365; see p. 364.

%H J. W. Meijer, <a href="https://www.ucbcba.edu.bo/Publicaciones/revistas/actanova/documentos/v4n4/Ensayos_Meijer2010_PI_.3r.pdf">Famous numbers on a chessboard</a>, Acta Nova, Volume 4, No.4, December 2010. pp. 589-598.

%H E. Pergola and R. A. Sulanke, <a href="https://cs.uwaterloo.ca/journals/JIS/PergolaSulanke/">Schroeder Triangles, Paths and Parallelogram Polyominoes</a>, J. Integer Sequences, 1 (1998), #98.1.7.

%H D. G. Rogers and L. W. Shapiro, <a href="http://dx.doi.org/10.1007/BFb0091826">Deques, trees and lattice paths</a>, 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.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/hip.pdf">Hipparchus, Plutarch, Schröder and Hough</a>, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F 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.

%F From _Wolfdieter Lang_, Sep 12 2005: (Start)

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

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

%F 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

%F From _Gary W. Adamson_, Jul 08 2011: (Start)

%F Let M = the production matrix:

%F   1, 2, 0, 0, 0, 0, ...

%F   1, 2, 1, 0, 0, 0, ...

%F   1, 2, 1, 2, 0, 0, ...

%F   1, 2, 1, 2, 1, 0, ...

%F   1, 2, 1, 2, 1, 2, ...

%F   ...

%F a(n) is the upper entry in the vector (M(T))^n * [1,0,0,0,...]; where T is the transpose operation. (End)

%F 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

%F a(n) ~ sqrt(48+34*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 07 2012

%F 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

%F a(n) = (n+1)*hypergeometric2F1([1-n, -n], [3], 2). - _Peter Luschny_, Nov 19 2014

%F a(n) = (A001003(n) + A001003(n+1))/2 = sum(A001003(k) * A001003(n-k), k=0..n). - _Johannes W. Meijer_, Apr 29 2015

%p 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:

%p seq(a(n), n=0..21); # _Johannes W. Meijer_, Mar 26 2012, revised Mar 31 2015

%t 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];

%t (* Do[Print[Table[f[ k, j ], {k, 0, j}]], {j, 10, 0, -1}] *)

%t Table[f[x, x+1], {x,0,21}]

%t (* Second program: *)

%t a[n_] := 2*Hypergeometric2F1[1-n, n+3, 2, -1]; a[0]=1;

%t Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Dec 09 2014, after _Wolfdieter Lang_ *)

%o (Haskell)

%o a010683 = sum . a144944_row  -- _Reinhard Zumkeller_, May 11 2013

%o (Sage)

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

%o [simplify(a(n)) for n in range(22)] # _Peter Luschny_, Nov 19 2014

%o (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

%o (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

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

%Y Second right-hand column of triangle A011117.

%Y A177010 has a closely-related g.f..

%K nonn,nice,easy

%O 0,2

%A Robert Sulanke (sulanke(AT)diamond.idbsu.edu), _N. J. A. Sloane_

%E Minor edits by _Johannes W. Meijer_, Mar 26 2012