OFFSET
1,2
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
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).
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
E.g.f.: exp(x)*x^2*(1 + x)^2. - Stefano Spezia, Oct 08 2022
EXAMPLE
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
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ryan Witko (witko(AT)nyu.edu), Mar 11 2004
EXTENSIONS
More terms from Robert G. Wilson v, Mar 16 2004
STATUS
approved