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

Author

Paul Barry, Sep 17 2009

Keywords

• nonn
• easy

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.

Crossrefs

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

Trisections give: A026726, A026671, A026674.

Programs

Magma

R:=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

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

SageMath

def A165407_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 2/(1-2*x+sqrt(1-4*x^3)) ).list()
A165407_list(50) # G. C. Greubel, Nov 09 2022

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=ceiling(n/3)..n} 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