|
%I #78 Jul 10 2018 02:58:44
%S 1,4,12,24,84,240,732,2184,6564,19680,59052,177144,531444,1594320,
%T 4782972,14348904,43046724,129140160,387420492,1162261464,3486784404,
%U 10460353200,31381059612,94143178824,282429536484,847288609440,2541865828332,7625597484984,22876792454964
%N 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.
%C 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
%C 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
%C 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
%H K. Böhmová, C. Dalfó, C. Huemer, <a href="http://upcommons.upc.edu/bitstream/handle/2117/80848/Kautz-subdigraphs.pdf">On cyclic Kautz digraphs</a>, Preprint 2016.
%H A. Burstein and H. S. Wilf, <a href="https://www.fq.math.ca/Scanned/35-3/burstein.pdf">On cyclic strings without long constant blocks</a>, Fibonacci Quarterly, 35 (1997), 240-247.
%H Cristina Dalfó, <a href="https://arxiv.org/abs/1709.01882">From subKautz digraphs to cyclic Kautz digraphs</a>, arXiv:1709.01882 [math.CO], 2017.
%H C. Dalfó, <a href="https://dx.doi.org/10.1016/j.laa.2017.05.046">The spectra of subKautz and cyclic Kautz digraphs</a>, Linear Algebra and its Applications, 531 (2017), pp. 210-219.
%H A. E. Edlin and D. Zeilberger, <a href="https://doi.org/10.1006/aama.2000.0696">The Goulden-Jackson cluster method for cyclic words</a>, Adv. Appl. Math., 25 (2000), 228-232.
%H Petros Hadjicostas and Lingyun Zhang, <a href="https://doi.org/10.1016/j.disc.2018.03.007">On cyclic strings avoiding a pattern</a>, Discrete Mathematics, 341 (2018), 1662-1674.
%H Jair Taylor, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1">Counting Words with Laguerre Series</a>, Electron. J. Combin., 21 (2014), P2.1.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,3).
%F a(0) = 1, a(1) = 4, a(n) = 3^n + 3*(-1)^n for n >= 2.
%F a(n) = 4 * A054878(n) for n >= 2. - _Joerg Arndt_, Oct 21 2012
%F G.f.: (1 + 2*x + x^2 - 12*x^3)/((1 + x)*(1 - 3*x)). - _Colin Barker_, Oct 22 2012
%F 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]
%F a(n+m) = a(n)*a(m)/4 + a(n+1)*a(m+1)/12. - _Yuchun Ji_, Sep 12 2017
%t nn=28; CoefficientList[Series[1+4x +12x^2/(1+x)^2/(1-4x/(1+x)),{x,0,nn}],x] (* _Geoffrey Critzer_, Apr 05 2014 *)
%o (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 */
%o (PARI) a(n) = if( n<2, [1,4][n+1], 3^n + 3*(-1)^n ); /* _Joerg Arndt_, Oct 21 2012 */
%Y Cf. A092297.
%K nonn,easy
%O 0,2
%A _Amritpal Singh_, Oct 19 2012
%E a(0) = 1 prepended and more terms added by _Joerg Arndt_, Oct 21 2012
|
