

A110110


Number of symmetric Schroeder paths of length 2n (A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,1) and H=(2,0) steps and never going below the xaxis).


3



1, 2, 4, 8, 18, 38, 88, 192, 450, 1002, 2364, 5336, 12642, 28814, 68464, 157184, 374274, 864146, 2060980, 4780008, 11414898, 26572086, 63521352, 148321344, 354870594, 830764794, 1989102444, 4666890936, 11180805570, 26283115038
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) = A026003(n1)+A026003(n) (n>=1; indeed, every symmetric Schroeder path of length 2n is either a left factor L of length n1 of a Schroeder path, followed by a H=(2,0) step and followed by the mirror image of L, or it is a left factor of length n of a Schroeder paths, followed by its mirror image).
a(n) is the number of sequences (f(n)) composed of n letters using letters a, b, c with the following rules. Each new sequence is built by adding a letter to the right end of a previous generation sequence. Letters a and b may not be adjacent. The number of c's <= n/2 in each sequence. Example: f(1) = {[a] [b]}, f(2) = {[aa], [ac], [bb], [bc]}, f(3) = {[aaa] [aac] [aca] [acb] [bbb] [bbc] [bcb] [bca]}.  Roger Ford, Jul 13 2014


LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000
Frédéric Bihan, Francisco Santos, PierreJean Spaenlehauer, A Polyhedral Method for Sparse Systems with many Positive Solutions, arXiv:1804.05683 [math.CO], 2018.
S. Samieinia, The number of continuous curves in digital geometry, Port. Math. 67 (1) (2010) 7589.
Jacob A. Siehler, Selections Without Adjacency on a Rectangular Grid, arXiv:1409.3869 [math.CO], 2014, p.9.


FORMULA

G.f.: (1 + x) * ( 1 + sqrt( 1  6*x^2 + x^4) / (1  2*x  x^2)) / (2*x).  Michael Somos, Feb 07 2011
G.f.: (1+z)R(z^2)/[1zR(z^2)], where R=1+zR+zR^2=[1zsqrt(16z+z^2)]/(2z) is the g.f. of the large Schroeder numbers.
a(2*n) = A050146(n+1).  Michael Somos, Feb 07 2011
From Roger Ford, May 25 2014: (Start)
a(2*n) = 3*a(2*n1)  2*A026003(2*n2), n>0.
a(2*n+1) = a(2*n) + 2*A026003(2*n)  A006318(n).
(End)
a(n) ~ sqrt(6*sqrt(2)8) * (1+sqrt(2))^(n+2)/ (2*sqrt(Pi*n)).  Vaclav Kotesovec, Mar 09 2016


EXAMPLE

a(2)=4 because we have HH, UDUD, UHD and UUDD.
1 + 2*x + 4*x^2 + 8*x^3 + 18*x^4 + 38*x^5 + 88*x^6 + 192*x^7 + 450*x^8 + ...


MAPLE

RR:=(1z^2sqrt(16*z^2+z^4))/2/z^2: G:=(1+z)*RR/(1z*RR): Gser:=series(G, z=0, 36): 1, seq(coeff(Gser, z^n), n=1..33);


MATHEMATICA

CoefficientList[Series[(1+x) * (1 + Sqrt[1  6*x^2 + x^4] / (1  2*x  x^2)) / (2*x), {x, 0, 30}], x] (* Vaclav Kotesovec, Mar 09 2016 *)


PROG

(PARI) {a(n) = if( n<0, 0, polcoeff( (1 + x) * ( 1 + sqrt( 1  6*x^2 + x^4 + x^2 * O(x^n)) / (1  2*x  x^2)) / (2*x), n))} /* Michael Somos, Feb 07 2011 */


CROSSREFS

Cf. A026003, A006318.
Sequence in context: A220839 A288206 A218078 * A300221 A233437 A321200
Adjacent sequences: A110107 A110108 A110109 * A110111 A110112 A110113


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Jul 12 2005


STATUS

approved



