%I #56 Oct 27 2024 20:29:20
%S 1,1,3,8,23,68,207,644,2040,6558,21343,70186,232864,778550,2620459,
%T 8872074,30195288,103246502,354508628,1221846856,4225644866,
%U 14659644348,51002664023,177909901566,622093882290,2180123564130,7656055966092
%N Number of words of length n in a simple grammar.
%C The grammar defines a language L consisting of words from the alphabet S = {e, w, n, s}. If each letter in S is regarded as an integer lattice step, e = (1,0), w = (-1,0), n = (0,1), s = (0,-1), then each word is a path in the two-dimensional integer lattice starting from (0,0), never going below the x-axis and ending on the x-axis. Thus, this is a variant of Motzkin paths with two kinds of level steps. The algebraic definition is L = 1 + Le + Lw + LnLs - w where each word is regarded as a noncommutative monomial with variables in S. Replacing each letter in S by x and L by the g.f. A(x) leads to x + A(x) = (1 + x*A(x))^2. If we let y = x + x*x*A, then y^2 - y = x^3 - x which is an elliptic curve. - _Michael Somos_, Mar 28 2020
%C The Hankel number wall for the sequence L(0), L(1), ... has a zigzag diagonal sequence b(0) = 1, b(1) = 1. b(2) = e, b(3) = ew+ns, b(4) = na(ee-ew-ns), ... which is a generalized Somos-5 sequence with b(i)*b(i+5) = -n*s*b(i+1)*b(i+4) + e*n*s*b(i+2)*b(i+3). Define sequence c(0) = 0, c(1) = 1, c(i) = b(i-2) for i>1, and c(i) = -(-n*s)^(-i)*c(-i) if i<0. Then c(i)*c(i+5) = -n*s*c(i+1)*c(i+4) + e*n*s*c(i+2)*c(i+3) for all i in Z. If e=w=n=s=1, then c(i) = A006769(i) * (-1)^[mod(i,4)=3]. - _Michael Somos_, Oct 14 2024
%H Michael De Vlieger, <a href="/A056010/b056010.txt">Table of n, a(n) for n = 0..1000</a>
%H Paul Barry, <a href="https://arxiv.org/abs/2306.05025">Integer sequences from elliptic curves</a>, arXiv:2306.05025 [math.NT], 2023.
%H Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.
%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/nwic.html">Number Walls in Combinatorics</a>.
%F L = 1 + Le + Lw + LnLs - w.
%F a(n) = 2*a(n-1) + a(0)*a(n-2) + ... + a(n-2)*a(0) for n>1.
%F The Somos-4 sequence A006720(n+2) is the Hankel transform of a(n-1). See A001906 for definition of Hankel transform.
%F Let s(n)= A006769(n). Then 0 = f( -s(n-1) * s(n+1) / s(n)^2, -s(n) * s(n+2) / s(n+1)^2 ) where f(u, v) = u + v - (1 + u*v)^2.
%F G.f. A(x) satisfies 0 = f(x, A(x)) where f(u, v) = u + v - (1 + u*v)^2.
%F G.f.: (1 - 2*x - sqrt( 1 - 4*x + 4*x^3) ) / (2*x^2).
%F From _Paul Barry_, Mar 04 2010: (Start)
%F G.f.: ((1-x)/(1-2x))c(x^2(1-x)/(1-2x)^2), c(x) the g.f. of A000108;
%F a(n) = Sum_{k=0..floor(n/2)} (A000108(k) * Sum_{i=0..k+1} C(k+1,i)*C(n-i,n-2k-i)*(-1)^i*2^(n-2k-i)). (End)
%F a(n) = A025262(n+2) if n >= 0.
%F 0 = a(n)*(+16*a(n+1) - 64*a(n+3) + 22*a(n+4)) + a(n+1)*(+32*a(n+2) - 14*a(n+3)) + a(n+2)*(+16*a(n+3) - 10*a(n+4)) + a(n+3)*(+2*a(n+3) + a(n+4)) if n>=0. - _Michael Somos_, Jan 18 2015
%e L(0) = 1, L(1) = e, L(2) = ee + ew + ns, L(3) = eee + ewe + nse + eew + eww + nsw + nes + ens.
%e G.f. = 1 + x + 3*x^2 + 8*x^3 + 23*x^4 + 68*x^5 + 207*x^6 + 644*x^7 + ...
%t CoefficientList[Series[(1 - 2 x - Sqrt[1 - 4 x + 4 x^3])/(2 x^2), {x, 0, 26}], x] (* _Michael De Vlieger_, Oct 30 2019 *)
%t a[ n_] := SeriesCoefficient[ (2 - 2*x)/(1 - 2*x + (1 - 4*x + 4*x^3)^(1/2)), {x, 0, n}]; (* _Michael Somos_, Oct 27 2024 *)
%t a[ n_] := If[ n<0, 0, SeriesCoefficient[Nest[(1 + x*#)^2 - x&, 1 + O[x], n], {x, 0, n}]]; (* _Michael Somos_, Oct 27 2024 *)
%o (PARI) {a(n) = if( n<0, 0, polcoef( (1 - 2*x - sqrt( 1 - 4*x + 4*x^3 + x^3 * O(x^n)) ) / (2*x^2), n))};
%o (PARI) {a(n) = if( n<0, 0, polcoef( (2 - 2*x)/(1 - 2*x + (1 - 4*x + 4*x^3 + x*O(x^n))^(1/2)), n))}; /* _Michael Somos_, Oct 27 2024 */
%Y Cf. A001006, A006720, A006769, A025262.
%K nonn,changed
%O 0,3
%A _Michael Somos_, Aug 01 2000