A212085 -id:A212085 - cp's OEIS frontend

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

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

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

			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

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

Column k=2 of A212085.
Cf. A027441, A182368, A182406.
Cf. A000217, A002061.

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

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 *)

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

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

A266695 Number of acyclic orientations of the Turán graph T(n,2).

Original entry on oeis.org

1, 1, 2, 4, 14, 46, 230, 1066, 6902, 41506, 329462, 2441314, 22934774, 202229266, 2193664790, 22447207906, 276054834902, 3216941445106, 44222780245622, 578333776748674, 8787513806478134, 127464417117501586, 2121181056663291350, 33800841048945424546

Offset: 0

Alois P. Heinz, Jan 02 2016

nonn

The Turán graph T(n,2) is also the complete bipartite graph K_{floor(n/2),ceiling(n/2)}.

An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.

Alois P. Heinz, Table of n, a(n) for n = 0..475
Beáta Bényi and Peter Hajnal, Combinatorics of poly-Bernoulli numbers, arXiv:1510.05765 [math.CO], 2015; Studia Scientiarum Mathematicarum Hungarica, Vol. 52, No. 4 (2015), 537-558, DOI:10.1556/012.2015.52.4.1325.
P. J. Cameron, C. A. Glass, and R. U. Schumacher, Acyclic orientations and poly-Bernoulli numbers, arXiv:1412.3685 [math.CO], 2014-2018.
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Turán graph

Column k=2 of A267383.
Cf. A099594, A212084, A212085, A266858, A266972.
Bisections give A048163 (even part), A188634 (odd part).

a:= n-> (p-> add(Stirling2(n-p+1, i+1)*Stirling2(p+1, i+1)*
         i!^2, i=0..p))(iquo(n, 2)):
seq(a(n), n=0..25);

a[n_] := With[{q=Quotient[n, 2]}, Sum[StirlingS2[n-q+1, i+1] StirlingS2[ q+1, i+1] i!^2, {i, 0, q}]];
Array[a, 24, 0] (* Jean-François Alcover, Nov 06 2018 *)

a(n) = Sum_{i=0..floor(n/2)} i!^2 * Stirling2(ceiling(n/2)+1,i+1) * Stirling2(floor(n/2)+1,i+1).
a(n) = A099594(floor(n/2),ceiling(n/2)).
a(n) = Sum_{k=0..n} abs(A266972(n,k)).
a(n) ~ n! / (sqrt(1-log(2)) * 2^n * (log(2))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Original entry on oeis.org

1, 1, -1, 0, 1, -4, 6, -3, 0, 1, -9, 36, -75, 78, -31, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0, 1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, 5552680, -6796926, 4787174

Offset: 0

Alois P. Heinz, Apr 30 2012

The complete bipartite graph K_(n,n) has 2n vertices and n^2 = A000290(n) edges. The chromatic polynomial of K_(n,n) has 2n+1 = A005408(n) coefficients.

			3 example graphs:                     +-----------+
.                 o        o   o      o   o   o   |
.                 |        |\ /|      |\ /|\ /|\ /
.                 |        | X |      | X | X | X
.                 |        |/ \|      |/ \|/ \|/ \
.                 o        o   o      o   o   o   |
.                                     +-----------+
Graph:         K_(1,1)    K_(2,2)      K_(3,3)
Vertices:         2          4            6
Edges:            1          4            9
The complete bipartite graph K_(2,2) is the cycle graph C_4 with chromatic polynomial q^4 -4*q^3 +6*q^2 -3*q => row 2 = [1, -4, 6, -3, 0].
Triangle T(n,k) begins:
  1;
  1,  -1,   0;
  1,  -4,   6,    -3,     0;
  1,  -9,  36,   -75,    78,     -31,       0;
  1, -16, 120,  -524,  1400,   -2236,    1930,     -675, ...
  1, -25, 300, -2200, 10650,  -34730,   75170,  -102545, ...
  1, -36, 630, -6915, 52080, -279142, 1074822, -2942445, ...
  ...

Alois P. Heinz, Rows n = 0..90, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Columns k=0-2 give: A000012, (-1)*A000290, A083374.
Row sums and last elements of rows give: A000007.
Row lengths give: A005408.
Sums of absolute values of row elements give: A048163(n+1).
T(n,2n-1) = (-1)*A092552(n).
Cf. A008277, A212085, A182368, A185442, A193233, A193277, A193283, A266695, A266972.

P:= n-> add(Stirling2(n, k) *mul(q-i, i=0..k-1) *(q-k)^n, k=0..n):
T:= n-> seq(coeff(P(n), q, 2*n-k), k=0..2*n):
seq(T(n), n=1..8);

T(n,k) = [q^(2n-k)] Sum_{j=0..n} (q-j)^n * S2(n,j) * Product_{i=0..j-1} (q-i).

T(0,0)=1 prepended by Alois P. Heinz, May 03 2024

A282245 a(n) = 1/n times the number of n-colorings of the complete bipartite graph K_(n,n).

Original entry on oeis.org

0, 1, 14, 453, 25444, 2214105, 276079026, 46716040525, 10304669487848, 2872910342870577, 987880924373494150, 410733590889633758901, 203120943850262404686732, 117838575503522957479230601, 79257755538247144929720855674, 61179085294923281767500772446045

Offset: 1

Alois P. Heinz, Feb 09 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..228
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Cf. A008277, A212085.

a:= n-> add(Stirling2(n, j)*mul(n-i, i=0..j-1)*(n-j)^n, j=1..n)/n:
seq(a(n), n=1..20);

a(n) = 1/n * Sum_{j=1..n} (n-j)^n * Stirling2(n,j) * Product_{i=0..j-1} (n-i).
a(n) = 1/n * A212085(n,n).
a(n) ~ c * d^n * n^(2*n-1) / exp(2*n), where d = 3.42422933454838937778530870500341391459244769750638251404159... and c = 0.646741403357125093928623036806787050141001... . - Vaclav Kotesovec, Feb 18 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A266695 Number of acyclic orientations of the Turán graph T(n,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212084 Triangle T(n,k), n>=0, 0<=k<=2n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete bipartite graph K_(n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A282245 a(n) = 1/n times the number of n-colorings of the complete bipartite graph K_(n,n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula