|
| |
|
|
A056010
|
|
Number of words of length n in a simple grammar.
|
|
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
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
|
|
|
LINKS
|
|
|
|
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).
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)
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
|
|
|
EXAMPLE
|
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 + ...
|
|
|
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 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, polcoeff( (1 - 2*x - sqrt( 1 - 4*x + 4*x^3 + x^3 * O(x^n)) ) / (2*x^2), n))};
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
