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

Author

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

Keywords

• easy
• nonn

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

• 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).

Programs

Maple

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

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

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