OFFSET
0,2
COMMENTS
Number of length-n words with 4 letters and no two adjacent identical letters (including, for n >= 2, the first and last letter). - Joerg Arndt, Oct 21 2012
a(n), for n > 1, apparently is the trace of the n-th power of the adjacency matrix of the complete 4-graph, a 4 X 4 matrix with diagonal elements all zeros and off-diagonal all ones (cf. A054878). - Tom Copeland, Nov 06 2012
The corrected formula by Geoffrey Critzer below (for a general k) is a special case of Theorem 2 in Burstein and Wilf (1997). See also Edlin and Zeilberger (2000), Corollary 5.5 in Taylor (2014), and Section 5 in Hadjicostas and Zhang (2018). - Petros Hadjicostas, Jul 09 2018
LINKS
K. Böhmová, C. Dalfó, C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
C. Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), pp. 210-219.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Index entries for linear recurrences with constant coefficients, signature (2,3).
FORMULA
a(0) = 1, a(1) = 4, a(n) = 3^n + 3*(-1)^n for n >= 2.
a(n) = 4 * A054878(n) for n >= 2. - Joerg Arndt, Oct 21 2012
G.f.: (1 + 2*x + x^2 - 12*x^3)/((1 + x)*(1 - 3*x)). - Colin Barker, Oct 22 2012
Generally for such words on k letters, g.f.: 1 + k*x + (k^2-k)*x^2/(1 + x)^2/(1 - k*x/(1 + x)). - Geoffrey Critzer, Apr 05 2014 [Corrected by Petros Hadjicostas, Jul 08 2018]
a(n+m) = a(n)*a(m)/4 + a(n+1)*a(m+1)/12. - Yuchun Ji, Sep 12 2017
MATHEMATICA
nn=28; CoefficientList[Series[1+4x +12x^2/(1+x)^2/(1-4x/(1+x)), {x, 0, nn}], x] (* Geoffrey Critzer, Apr 05 2014 *)
PROG
(Maxima) a[0]:1$ a[1]:4$ a[n]:=3^n + 3*(-1)^n$ makelist(a[n], n, 0, 40); /* Martin Ettl, Oct 21 2012 */
(PARI) a(n) = if( n<2, [1, 4][n+1], 3^n + 3*(-1)^n ); /* Joerg Arndt, Oct 21 2012 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Amritpal Singh, Oct 19 2012
EXTENSIONS
a(0) = 1 prepended and more terms added by Joerg Arndt, Oct 21 2012
STATUS
approved