|
| |
|
|
A007477
|
|
Shifts 2 places left when convolved with itself.
(Formerly M0789)
|
|
25
|
|
|
|
1, 1, 1, 2, 3, 6, 11, 22, 44, 90, 187, 392, 832, 1778, 3831, 8304, 18104, 39666, 87296, 192896, 427778, 951808, 2124135, 4753476, 10664458, 23981698, 54045448, 122041844, 276101386, 625725936, 1420386363, 3229171828, 7351869690, 16760603722, 38258956928, 87437436916, 200057233386, 458223768512, 1050614664580
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Words of length n in language defined by L = 1 + a + (L)L: L(0)=1, L(1)=a, L(2)=(), L(3)=(a)+()a, L(4)=(())+(a)a+()(), ...
a(n) = number of Motzkin n-paths (A001006) in which no flatstep (F) is immediately followed by either an upstep (U) or a flatstep, in other words, each flatstep is either followed by a downstep (D) or ends the path. For example, a(4)=3 counts UDUD, UFDF, UUDD. - David Callan, Jun 07 2006
a(n) = number of Dyck (n+1)-paths (A000108) containing no UDUs and no subpaths of the form UUPDD where P is a nonempty Dyck path. For example, a(4)=3 counts UUUDDUUDDD, UUDDUUDDUD, UUUDDUDDUD. - David Callan, Sep 25 2006
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-1}*a_0 for n >= t. For example phi([1]) is the Catalan numbers A000108. The present sequence is (essentially) phi([0,1,1]). - Gary W. Adamson and R. J. Mathar, Oct 27 2008
For n>=2, a(n) gives number of possible, ways to parse an English sentence consisting of just n+1 copies of word "buffalo", with one particular "plausible" grammar. See the Wikipedia page and my Python source at OEIS Wiki. Whether these are really intelligible sentences is of course debatable. See A213705 for a more plausible example in the Finnish language. - Antti Karttunen, Sep 14 2012
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210; arXiv:math/0205301 [math.CO], 2002.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon, Pinnacle sets revisited, arXiv:2106.05248 [math.CO], 2021.
|
|
|
FORMULA
|
a(n) = sum( a(k) * a(n-2-k) ), n>1.
G.f. A(x) satisfies the equation 0 = 1 + x - A(x) + (x*A(x))^2.
The g.f. satisfies A(x)-x^2*A(x)^2 = 1+x. - Ralf Stephan, Jun 30 2003
G.f.: (1-sqrt(1-4x^2-4x^3))/(2x^2).
G.f.: 1/(1-x/(1-x^2/(1-x^2/(1-x/(1-x^2/(1-x^2/(1-x/(1-x^2/(1-x^2/(1-... (continued fraction). - Paul Barry, Jul 30 2010
D-finite with recurrence: (n+2)*a(n) +(n+1)*a(n-1) +4*(-n+1)*a(n-2) +2*(-4*n+9)*a(n-3) +2*(-2*n+7)*a(n-4)=0. - R. J. Mathar, Dec 02 2012
a(n) = Sum_{k=0..n-2} binomial(2*k+2,n-k-2)*binomial(n-k-2,k)/(k+1), n>1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Nov 22 2014
a(n) ~ sqrt(3 - 4*r^2) * (4*r)^n * (1+r)^(n+1) / (sqrt(Pi)*n^(3/2)), where r = 0.41964337760708056627592628232664330021208937304879612338939... is the root of the equation 4*r^2*(1+r) = 1. - Vaclav Kotesovec, Jul 03 2021
|
|
|
MAPLE
|
A007477 := proc(n) option remember; local k; if n <= 1 then 1 else add(A007477(k)*A007477(n-k-2), k=0..n-2); fi; end;
unprotect(phi);
phi:=proc(t, u, M) local i, a;
a:=Array(0..M); for i from 0 to t-1 do a[i]:=u[i+1]; od:
for i from t to M do a[i]:=add(a[j]*a[i-1-j], j=0..i-1); od:
[seq(a[i], i=0..M)]; end;
phi(3, [0, 1, 1], 30);
|
|
|
MATHEMATICA
|
f[x_] := (1 - Sqrt[1 - 4x^2 - 4x^3])/2; Drop[ CoefficientList[ Series[f[x], {x, 0, 32}], x], 2] (* Jean-François Alcover, Nov 22 2011, after Pari *)
|
|
|
PROG
|
(PARI) a(n)=polcoeff((1-sqrt(1-4*x^2-4*x^3+x^3*O(x^n)))/2, n+2)
(Haskell)
a007477 n = a007477_list !! n
a007477_list = 1 : 1 : f [1, 1] where
f xs = y : f (y:xs) where y = sum $ zipWith (*) (tail xs) (reverse xs)
(Maxima) a(n):=if n<2 then 1 else sum((binomial(2*k+2, n-k-2)*binomial(n-k-2, k))/(k+1), k, 0, n-2); /* Vladimir Kruchinin, Nov 22 2014 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
