login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 1 01:06 EDT 2020. Contains 333152 sequences. (Running on oeis4.)