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
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
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved