

A218034


Number of ways to seat 4 types of people in n labeled seats around a circle such that no two adjacent people are of the same type.


7



1, 4, 12, 24, 84, 240, 732, 2184, 6564, 19680, 59052, 177144, 531444, 1594320, 4782972, 14348904, 43046724, 129140160, 387420492, 1162261464, 3486784404, 10460353200, 31381059612, 94143178824, 282429536484, 847288609440, 2541865828332, 7625597484984, 22876792454964
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Number of lengthn 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 nth power of the adjacency matrix of the complete 4graph, a 4 X 4 matrix with diagonal elements all zeros and offdiagonal 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

Table of n, a(n) for n=0..28.
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), 240247.
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. 210219.
A. E. Edlin and D. Zeilberger, The GouldenJackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 16621674.
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^2k)*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/(14x/(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

Cf. A092297.
Sequence in context: A025543 A064354 A199903 * A140813 A073841 A032339
Adjacent sequences: A218031 A218032 A218033 * A218035 A218036 A218037


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



