|
%I #35 Nov 25 2021 12:55:14
%S 1,1,3,7,16,38,89,209,491,1153,2708,6360,14937,35081,82391,193503,
%T 454460,1067342,2506753,5887345,13826983,32473969,76268168,179122960,
%U 420687105,988023201,2320465339,5449830919,12799440072,30060687862
%N Expansion of (1 - x)/(1 - 2*x - x^2 + x^4).
%C Equals INVERT transform of (1, 2, 2, 1, 1, 1, ...). - _Gary W. Adamson_, Apr 28 2009
%C 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
%H Shanzhen Gao, Keh-Hsun Chen, <a href="http://worldcomp-proceedings.com/proc/p2014/FCS2696.pdf">Tackling Sequences From Prudent Self-Avoiding Walks</a>, FCS'14, The 2014 International Conference on Foundations of Computer Science.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1039">Encyclopedia of Combinatorial Structures 1039</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,0,-1).
%F 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)}.
%F Sum(-(1/106)*(-17 - 22*_alpha + 10*_alpha^2 + 8*_alpha^3)*_alpha^(-1-n), _alpha=RootOf(1 - 2*_Z - _Z^2 + _Z^4)).
%F 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
%p spec := [S,{S=Sequence(Prod(Union(Prod(Z,Z),Z,Sequence(Z)),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
%o (Maxima)
%o 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 */
%o (PARI) Vec((1-x)/(1-2*x-x^2+x^4) + O(x^40)) \\ _Michel Marcus_, Mar 16 2016
%K easy,nonn
%O 0,3
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
