A056010 Number of words of length n in a simple grammar.

1, 1, 3, 8, 23, 68, 207, 644, 2040, 6558, 21343, 70186, 232864, 778550, 2620459, 8872074, 30195288, 103246502, 354508628, 1221846856, 4225644866, 14659644348, 51002664023, 177909901566, 622093882290, 2180123564130, 7656055966092

Offset: 0

Author

Michael Somos, Aug 01 2000

Keywords

• nonn

Comments

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

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

Examples

			L(0) = 1, L(1) = e, L(2) = ee + ew + ns, L(3) = eee + ewe + nse + eew + eww + nsw + nes + ens.
G.f. = 1 + x + 3*x^2 + 8*x^3 + 23*x^4 + 68*x^5 + 207*x^6 + 644*x^7 + ...
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..1000
• Paul Barry, Integer sequences from elliptic curves, arXiv:2306.05025 [math.NT], 2023.
• Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
• Michael Somos, Number Walls in Combinatorics.

Crossrefs

Cf. A001006, A006720, A006769, A025262.

Programs

Mathematica

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 *)
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 *)
a[ n_] := If[ n<0, 0, SeriesCoefficient[Nest[(1 + x*#)^2 - x&, 1 + O[x], n], {x, 0, n}]]; (* Michael Somos, Oct 27 2024 *)

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))};

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

Formula

L = 1 + Le + Lw + LnLs - w.

a(n) = 2*a(n-1) + a(0)*a(n-2) + ... + a(n-2)*a(0) for n>1.

The Somos-4 sequence A006720(n+2) is the Hankel transform of a(n-1). See A001906 for definition of Hankel transform.

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.

G.f. A(x) satisfies 0 = f(x, A(x)) where f(u, v) = u + v - (1 + u*v)^2.

G.f.: (1 - 2*x - sqrt( 1 - 4*x + 4*x^3) ) / (2*x^2).

From Paul Barry, Mar 04 2010: (Start)

G.f.: ((1-x)/(1-2x))c(x^2(1-x)/(1-2x)^2), c(x) the g.f. of A000108;

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)

a(n) = A025262(n+2) if n >= 0.

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