A052967 Expansion of (1 - x)/(1 - 2*x - x^2 + x^4).

1, 1, 3, 7, 16, 38, 89, 209, 491, 1153, 2708, 6360, 14937, 35081, 82391, 193503, 454460, 1067342, 2506753, 5887345, 13826983, 32473969, 76268168, 179122960, 420687105, 988023201, 2320465339, 5449830919, 12799440072, 30060687862

Offset

0,3

Comments

Equals INVERT transform of (1, 2, 2, 1, 1, 1, ...). - Gary W. Adamson, Apr 28 2009

a(n) is the number of perfect matchings in the graph with vertices labeled 1 to 2n with edges {i,j} for |i-j| <= 3. - Robert Israel, Jan 22 2019

Links

Table of n, a(n) for n=0..29.

Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1039

Index entries for linear recurrences with constant coefficients, signature (2,1,0,-1).

Formula

Recurrence: {a(1)=1, a(0)=1, a(2)=3, a(3)=7, a(n)-a(n+2)-2*a(n+3)+a(n+4)}.

Sum(-(1/106)*(-17 - 22*_alpha + 10*_alpha^2 + 8*_alpha^3)*_alpha^(-1-n), _alpha=RootOf(1 - 2*_Z - _Z^2 + _Z^4)).

a(n) = Sum_{k=0..n} (Sum_{m=0..k} (binomial(k,m)*Sum_{i=0..n-k-m}(binomial(m,i)*binomial(n-i-2*m-1,n-k-i-m)))). - Vladimir Kruchinin, Mar 16 2016

Maple

spec := [S, {S=Sequence(Prod(Union(Prod(Z, Z), Z, Sequence(Z)), Z))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);

Prog

(Maxima)
a(n):=sum(sum(binomial(k, l)*sum(binomial(l, i)*binomial(n-i-2*l-1, n-k-i-l), i, 0, n-k-l), l, 0, k), k, 0, n); /* Vladimir Kruchinin, Mar 16 2016  */
(PARI) Vec((1-x)/(1-2*x-x^2+x^4) + O(x^40)) \\ Michel Marcus, Mar 16 2016

Crossrefs

Sequence in context: A095263 A010912 A192665 * A297498 A239040 A323225

Adjacent sequences: A052964 A052965 A052966 * A052968 A052969 A052970

Keyword

easy,nonn

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Status

approved