login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

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 December 7 09:33 EST 2019. Contains 329843 sequences. (Running on oeis4.)