cp's OEIS Frontend

A208880 Number of words either empty or beginning with the first letter of the cyclic n-ary alphabet, where each letter of the alphabet occurs twice and letters of neighboring word positions are equal or neighbors in the alphabet.

%I A208880 #16 Jun 13 2015 00:54:11
%S A208880 1,1,3,30,62,114,202,346,582,966,1590,2602,4242,6898,11198,18158,
%T A208880 29422,47650,77146,124874,202102,327062,529254,856410,1385762,2242274,
%U A208880 3628142,5870526,9498782,15369426,24868330,40237882,65106342,105344358,170450838,275795338
%N A208880 Number of words either empty or beginning with the first letter of the cyclic n-ary alphabet, where each letter of the alphabet occurs twice and letters of neighboring word positions are equal or neighbors in the alphabet.
%C A208880 The first and the last letters are considered neighbors in a cyclic alphabet.  The words are not considered cyclic here.
%C A208880 Also the number of (2*n-1)-step walks on n-dimensional cubic lattice from (1,0,...,0) to (2,2,...,2) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,n}.
%H A208880 Alois P. Heinz, <a href="/A208880/b208880.txt">Table of n, a(n) for n = 0..1000</a>
%H A208880 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).
%F A208880 G.f.: -(11*x^6-10*x^5-22*x^4+24*x^3+2*x^2-2*x+1)/((x^2+x-1)*(x-1)^2).
%e A208880 a(0) = 1: the empty word.
%e A208880 a(1) = 1 = |{aa}|.
%e A208880 a(2) = 3 = |{aabb, abab, abba}|.
%e A208880 a(3) = 30 = |{aabbcc, aabcbc, aabccb, aacbbc, aacbcb, aaccbb, ababcc, abacbc, abaccb, abbacc, abbcac, abbcca, abcabc, abcacb, abcbac, abcbca, abccab, abccba, acabbc, acabcb, acacbb, acbabc, acbacb, acbbac, acbbca, acbcab, acbcba, accabb, accbab, accbba}|.
%p A208880 a:= n-> `if`(n<3, 1+n*(n-1),
%p A208880         (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
%p A208880          <<2, 2, 14, 30>>)[1, 1]):
%p A208880 seq(a(n), n=0..40);
%t A208880 Join[{1,1,3},LinearRecurrence[{3,-2,-1,1},{30,62,114,202},40]] (* _Harvey P. Dale_, Mar 09 2015 *)
%Y A208880 Row n=2 of A208879.
%K A208880 nonn,walk,easy
%O A208880 0,3
%A A208880 _Alois P. Heinz_, Mar 02 2012