%I #12 Dec 02 2023 17:33:39
%S 1,26,676,17575,456924,11879348,308845473,8029525374,208755780376,
%T 5427341444303,141102848026504,3668465292908728,95374670274182625,
%U 2479600324280721746,64465939966005856668,1676019064445878090743,43574016075268549637572,1132859952017016284720204
%N Number of words of length n over the alphabet [A-Z] that do not contain the string CAT.
%D H. S. Wilf, The Editor's Corner: Strings, Substrings, and the `Nearest Integer' Function, Amer. Math. Monthly 94 (1987), 855-860.
%H Harvey P. Dale, <a href="/A360509/b360509.txt">Table of n, a(n) for n = 0..706</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (26, 0, -1).
%F a(0)=1, a(1)=26, a(2) = 26^2; thereafter, a(n) = 26*a(n-1) - a(n-3).
%e At length 3, only one word (CAT) is excluded, so a(3) = 26^3 - 1 = 17575.
%p f:=proc(n,A) option remember;
%p if n<0 then 0 elif n=0 then 1 else A*f(n-1,A) - f(n-3,A); fi;
%p end;
%p [seq(f(n,26),n=0..25)];
%t f[n_, A_] := f[n, A] = Which[n < 0, 0, n == 0, 1, True, A*f[n-1, A] - f[n-3, A]];
%t Table[f[n, 26], {n, 0, 25}] (* _Jean-François Alcover_, Apr 14 2023, after Maple code *)
%t LinearRecurrence[{26,0,-1},{1,26,26^2},20] (* _Harvey P. Dale_, Dec 02 2023 *)
%K nonn
%O 0,2
%A _N. J. A. Sloane_, Feb 24 2023