login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056010 Number of words of length n in a simple grammar. 6
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

LINKS

Michael De Vlieger, Table of n, a(n) for n = 0..1000

Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.

M. Somos, Number Walls in Combinatorics.

FORMULA

L = 1 + L(e+w) + 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).

Contribution 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

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

Cf. A006720, A025262.

Sequence in context: A199103 A057198 A025262 * A002712 A192679 A193418

Adjacent sequences:  A056007 A056008 A056009 * A056011 A056012 A056013

KEYWORD

nonn

AUTHOR

Michael Somos, Aug 01 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 24 07:45 EST 2020. Contains 332199 sequences. (Running on oeis4.)