A165407 Expansion of 1/(1-x-x^3*c(x^3)), c(x) the g.f. of A000108.

1, 1, 1, 2, 3, 4, 7, 11, 16, 27, 43, 65, 108, 173, 267, 440, 707, 1105, 1812, 2917, 4597, 7514, 12111, 19196, 31307, 50503, 80380, 130883, 211263, 337284, 548547, 885831, 1417582, 2303413, 3720995, 5965622, 9686617, 15652239, 25130844, 40783083, 65913927

Offset

0,4

Comments

Hankel transform is A010892(n+1).

Row sums of A165408.

Number of UF-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are UF-equivalent iff the positions of pattern UF are identical in these paths. This also works for the pattern FU. - Sergey Kirgizov, Apr 08 2018

a(n) is the total number of lattice paths from (0,0) to (n-2*i,i) that do not go above the diagonal x=y using steps in {(1,0), (0,1)}. - Alois P. Heinz, Sep 20 2022

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000

Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.

J.-L. Baril and A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1

Formula

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

a(n) = Sum_{k=0..n} if(n<=3k, C((n+k)/2,k)*((3*k-n)/2 + 1)*(1+(-1)^(n-k) )/(2*(k+1)).

a(n) = Sum_{k=0..n+1} Fibonacci(n-k+1)*(0^k - A000108((k-2)/3)*(1+2*cos(2*Pi*(k-2)/3))/3).

(n+1)*a(n) = (n+1)*a(n-1) + (n+1)*a(n-2) +2*(2*n-7)*a(n-3) -2*(2*n-7)*a(n-4) -2*(2*n-7)*a(n-5). - R. J. Mathar, Nov 15 2011

a(3*n) = A026726(n); a(3*n+1) = A026671(n); a(3*n+2) = A026674(n+1). - Philippe Deléham, Feb 01 2014

Limit_{n->oo} a(n+1)/a(n) = A001622. - Alois P. Heinz, Sep 15 2022

Maple

b:= proc(x, y) option remember; `if`(y<=x, `if`(x=0, 1,
      b(x-1, y)+`if`(y>0, b(x, y-1), 0)), 0)
    end:
a:= n-> add(b(n-2*i, i), i=0..n/3):
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 20 2022

Mathematica

b[x_, y_]:= b[x, y]= If[y<=x, If[x==0, 1, b[x-1, y] +If[y>0, b[x, y-1], 0]], 0];
a[n_] := Sum[b[n-2*i, i], {i, 0, n/3}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 08 2022, after Alois P. Heinz *)
CoefficientList[Series[(Sqrt[1-4*x^3] -1+2*x)/(2*x*(1-x-x^2)), {x, 0, 50}], x] (* G. C. Greubel, Nov 09 2022 *)

Prog

(Magma) R<x>:=PowerSeriesRing(Rationals(), 50); Coefficients(R!( (Sqrt(1-4*x^3) -1+2*x)/(2*x*(1-x-x^2)) )); // G. C. Greubel, Nov 09 2022
(SageMath)
def A165407_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( 2/(1-2*x+sqrt(1-4*x^3)) ).list()
A165407_list(50) # G. C. Greubel, Nov 09 2022

Crossrefs

Cf. A000045, A000108, A001622, A010892, A165408.

Trisections give: A026726, A026671, A026674.

Sequence in context: A222023 A221997 A221998 * A039897 A297789 A222122

Adjacent sequences: A165404 A165405 A165406 * A165408 A165409 A165410

Keyword

nonn,easy

Author

Paul Barry, Sep 17 2009

Status

approved