%I #47 Sep 08 2022 08:44:59
%S 1,1,4,8,22,52,132,324,808,2000,4968,12320,30576,75856,188224,467008,
%T 1158752,2875072,7133632,17699904,43916928,108966400,270366848,
%U 670832640,1664466176,4129863936,10246994944,25424785408,63083832832
%N Expansion of (1 - x)/(1 - 2*x - 2*x^2 + 2*x^3).
%C Form the graph with matrix A = [1,1,1,1; 1,0,0,0; 1,0,0,0; 1,0,0,1]. Then a(n) counts closed walks of length n at the degree 5 vertex. - _Paul Barry_, Oct 02 2004
%C Equals the INVERT transform of (1, 3, 1, 1, 1, ...). - _Gary W. Adamson_, Apr 27 2009
%C a(n) is also the number of vertex-transitive cover graphs of lattice quotients of essential lattice congruences of the weak order on the symmetric group S_{n+1}. See Table 1 in the Hoang/Mütze reference in the Links section. - _Torsten Muetze_, Nov 28 2019
%H G. C. Greubel, <a href="/A052528/b052528.txt">Table of n, a(n) for n = 0..1000</a>
%H Hung Phuc Hoang, Torsten Mütze, <a href="https://arxiv.org/abs/1911.12078">Combinatorial generation via permutation languages. II. Lattice congruences</a>, arXiv:1911.12078 [math.CO], 2019.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=455">Encyclopedia of Combinatorial Structures 455</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-2).
%F G.f.: (1 - x)/(1 - 2*x - 2*x^2 + 2*x^3).
%F Recurrence: a(1) = 1, a(0) = 1, a(2) = 4, 2*a(n) - 2*a(n+1) - 2*a(n+2) + a(n+3) = 0.
%F a(n) = Sum_{alpha=RootOf(2*Z^3-2*Z^2-2*Z+1)} (1/37)*(5 - 9*alpha^2 + 12*alpha)* alpha^(-1 - n).
%F a(n) = 2*a(n-2) + Sum_{i=0..n-1} a(i). - _Yuchun Ji_, Dec 29 2018
%p spec := [S,{S=Sequence(Prod(Z,Union(Z,Z,Sequence(Z))))},unlabeled]:
%p seq(combstruct[count](spec,size=n), n=0..20);
%t LinearRecurrence[{2,2,-2}, {1,1,4}, 30] (* _G. C. Greubel_, May 12 2019 *)
%o (PARI) my(x='x+O('x^30)); Vec((1-x)/(1-2*x-2*x^2+2*x^3)) \\ _G. C. Greubel_, May 12 2019
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)/(1 -2*x-2*x^2+2*x^3) )); // _G. C. Greubel_, May 12 2019
%o (Sage) ((1-x)/(1-2*x-2*x^2+2*x^3)).series(x, 30).coefficients(x, sparse=False) # _G. C. Greubel_, May 12 2019
%o (GAP) a:=[1,1,4];; for n in [4..30] do a[n]:=2*a[n-1]+2*a[n-2]-2*a[n-3]; od; a; # _G. C. Greubel_, May 12 2019
%Y Cf. A077937, A052987.
%K nonn,easy
%O 0,3
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E More terms from _James A. Sellers_, Jun 06 2000