|
|
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
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(n) = 2*C(n,2) + 12*C(n,3) + 24*C(n,4) = n*(n-1)*(n^2-3*n+3).
For n > 1, a(n) = floor(n^7/(n^3-1)). - Gary Detlefs, Feb 10 2010
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Ryan Witko (witko(AT)nyu.edu), Mar 11 2004
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|