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.

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

Offset: 0

Author

Amritpal Singh, Oct 19 2012

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A092297.

Programs

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 *)

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 */

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

Extensions

a(0) = 1 prepended and more terms added by Joerg Arndt, Oct 21 2012