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!)
A091940 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. 25

%I

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

%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>

%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

%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 Cf. A027441, A182368, A182406.

%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

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 June 22 19:28 EDT 2021. Contains 345388 sequences. (Running on oeis4.)