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.

0, 2, 18, 84, 260, 630, 1302, 2408, 4104, 6570, 10010, 14652, 20748, 28574, 38430, 50640, 65552, 83538, 104994, 130340, 160020, 194502, 234278, 279864, 331800, 390650, 457002, 531468, 614684, 707310, 810030, 923552, 1048608, 1185954, 1336370, 1500660

Offset: 1

Author

Ryan Witko (witko(AT)nyu.edu), Mar 11 2004

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• OEIS Wiki, Colorings of square grid graphs
• Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Crossrefs

Column k=2 of A212085.

Cf. A027441, A182368, A182406.

Cf. A000217, A002061.

Programs

Maple

a := n -> (n-1)+(n-1)^4; for n to 35 do a(n) end do; # Rainer Rosenthal, Dec 03 2006

Mathematica

Table[2Binomial[n, 2] + 12Binomial[n, 3] + 24Binomial[n, 4], {n, 35}] (* Robert G. Wilson v, Mar 16 2004 *)
Table[(n-1)^4+(n-1),{n,1,60}] (* Vladimir Joseph Stephan Orlovsky, May 12 2011 *)

Formula

a(n) = 2*C(n,2) + 12*C(n,3) + 24*C(n,4) = n*(n-1)*(n^2-3*n+3).

a(n) = (n-1) + (n-1)^4. - Rainer Rosenthal, Dec 03 2006

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

For n > 1, a(n) = floor(n^7/(n^3-1)). - Gary Detlefs, Feb 10 2010

a(n) = 2 * A000217(n-1) * A002061(n-1), n >= 1. - Daniel Forgues, Jul 14 2016

E.g.f.: exp(x)*x^2*(1 + x)^2. - Stefano Spezia, Oct 08 2022

Extensions

More terms from Robert G. Wilson v, Mar 16 2004