cp's OEIS Frontend

A054668 Number of distinct non-extendable sequences X={x(1),x(2),...,x(k)} where x(1)=1, the x(i)'s are distinct elements of {1,...,n} with |x(i)-x(i+1)|=1 or 2, for i=1,2,...,k.

%I A054668 #25 Jul 01 2025 09:27:49
%S A054668 1,2,4,8,16,30,56,104,192,354,652,1200,2208,4062,7472,13744,25280,
%T A054668 46498,85524,157304,289328,532158,978792,1800280,3311232,6090306,
%U A054668 11201820,20603360,37895488,69700670,128199520,235795680,433695872,797691074,1467182628,2698569576
%N A054668 Number of distinct non-extendable sequences X={x(1),x(2),...,x(k)} where x(1)=1, the x(i)'s are distinct elements of {1,...,n} with |x(i)-x(i+1)|=1 or 2, for i=1,2,...,k.
%C A054668 Superseeker suggests the g.f. ((x^4)+1)/(x^4-2x+1). If the sequences X, in the enumeration of a(n), are required to contain n then sequence A000073 (tribonacci numbers) is obtained.
%H A054668 Elisa Heinrich Mora and Noah A. Rosenberg, <a href="https://arxiv.org/abs/2506.16577">An nth-cousin mating model and the n-anacci numbers</a>, arXiv:2506.16577 [q-bio.PE], 2025. See p. 7.
%F A054668 a(1) = 1, a(n) = term (4,2) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,0; 2,0,0,1]^n (n > 1). - _Alois P. Heinz_, Jul 24 2008
%e A054668 a(4) = 4, since the allowable sequences are {1,2,3,4}, {1,2,4,3}, {1,3,2,4} and {1,3,4,2}, whereas {1,4,2,3} and {1,4,3,2} violate the spacing condition.
%p A054668 a:= n-> `if`(n=1, 1, (<<1|1|0|0>, <1|0|1|0>, <1|0|0|0>, <2|0|0|1>>^n)[4,2]):
%p A054668 seq(a(n), n=1..50);  # _Alois P. Heinz_, Jul 24 2008
%t A054668 a=b=c=0;Join[{1},Table[d=a+b+c+2;a=b;b=c;c=d,{n,50}]] (* _Vladimir Joseph Stephan Orlovsky_, Apr 19 2011 *)
%Y A054668 Cf. A053623.
%K A054668 nonn
%O A054668 1,2
%A A054668 _John W. Layman_, Apr 18 2000