|
%I #69 Apr 15 2023 00:04:42
%S 0,2,18,84,260,630,1302,2408,4104,6570,10010,14652,20748,28574,38430,
%T 50640,65552,83538,104994,130340,160020,194502,234278,279864,331800,
%U 390650,457002,531468,614684,707310,810030,923552,1048608,1185954,1336370,1500660
%N Given n colors, sequence gives number of ways to color the vertices of a square such that no edge has the same color on both of its vertices.
%C Also equals the number of pairs of pairs ((a_1,a_2),(b_1,b_2)) that are disjoint (a_i != b_j) where all elements belong to {1,...,n}. See A212085. - _Lewis Baxter_, Mar 06 2023
%H Alois P. Heinz, <a href="/A091940/b091940.txt">Table of n, a(n) for n = 1..1000</a>
%H OEIS Wiki, <a href="/wiki/Colorings_of_square_grid_graphs">Colorings of square grid graphs</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1).
%F a(n) = 2*C(n,2) + 12*C(n,3) + 24*C(n,4) = n*(n-1)*(n^2-3*n+3).
%F a(n) = (n-1) + (n-1)^4. - _Rainer Rosenthal_, Dec 03 2006
%F G.f.: 2*x^2*(1+4*x+7*x^2)/(1-x)^5. a(n) = 2*A027441(n-1). - _R. J. Mathar_, Sep 09 2008
%F For n > 1, a(n) = floor(n^7/(n^3-1)). - _Gary Detlefs_, Feb 10 2010
%F a(n) = 2 * A000217(n-1) * A002061(n-1), n >= 1. - _Daniel Forgues_, Jul 14 2016
%F E.g.f.: exp(x)*x^2*(1 + x)^2. - _Stefano Spezia_, Oct 08 2022
%e a(4) = 84 since there are 84 different ways to color the vertices of a square with 4 colors such that no two vertices that share an edge are the same color.
%e There are 4 possible colors for the first vertex and 3 for the second vertex. For the third vertex, divide into two cases: the third vertex can be the same color as the first vertex, and then the fourth vertex has 3 possible colors (4 * 3 * 1 * 3 = 36 colorings). Or the third vertex can be a different color from the first vertex, and then the fourth vertex has 2 possible colors (4 * 3 * 2 * 2 = 48 colorings). So there are a total of 36 + 48 = 84. - _Michael B. Porter_, Jul 24 2016
%p a := n -> (n-1)+(n-1)^4; for n to 35 do a(n) end do; # _Rainer Rosenthal_, Dec 03 2006
%t Table[2Binomial[n, 2] + 12Binomial[n, 3] + 24Binomial[n, 4], {n, 35}] (* _Robert G. Wilson v_, Mar 16 2004 *)
%t Table[(n-1)^4+(n-1),{n,1,60}] (* _Vladimir Joseph Stephan Orlovsky_, May 12 2011 *)
%Y Column k=2 of A212085.
%Y Cf. A027441, A182368, A182406.
%Y Cf. A000217, A002061.
%K nonn,easy
%O 1,2
%A Ryan Witko (witko(AT)nyu.edu), Mar 11 2004
%E More terms from _Robert G. Wilson v_, Mar 16 2004
|
