A266972 -id:A266972 - cp's OEIS frontend

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

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

A061776 Start with a single triangle; at n-th generation add a triangle at each vertex, allowing triangles to overlap; sequence gives number of triangles in n-th generation.

Original entry on oeis.org

1, 3, 6, 12, 18, 30, 42, 66, 90, 138, 186, 282, 378, 570, 762, 1146, 1530, 2298, 3066, 4602, 6138, 9210, 12282, 18426, 24570, 36858, 49146, 73722, 98298, 147450, 196602, 294906, 393210, 589818, 786426, 1179642, 1572858, 2359290, 3145722, 4718586, 6291450

Offset: 0

N. J. A. Sloane, R. K. Guy, Jun 23 2001

Number of 3-colorings of the (n,2)-Turán graph. - Alois P. Heinz, Jun 07 2024

R. Reed, The Lemming Simulation Problem, Mathematics in School, 3 (#6, Nov. 1974), front cover and pp. 5-6.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
R. Reed, The Lemming Simulation Problem, Mathematics in School, 3 (#6, Nov. 1974), front cover and pp. 5-6. [Scanned photocopy of pages 5, 6 only, with annotations by R. K. Guy and N. J. A. Sloane]
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

A061777 gives total population of triangles at n-th generation.

Cf. A266972.

A061776 := proc(n) if n mod 2 = 0 then 6*(2^(n/2)-1); else 3*(2^((n-1)/2)-1)+3*(2^((n+1)/2)-1); fi; end; # for n >= 1

a[0]=1; a[n_/;EvenQ[n]]:=6*(2^(n/2)-1); a[n_/;OddQ[n]] := 3*(2^((n-1)/2)-1) + 3*(2^((n+1)/2)-1); a /@ Range[0, 37] (* Jean-François Alcover, Apr 22 2011, after Maple program *)
CoefficientList[Series[(1 + 2 x) (1 + x^2) / ((1 - x) (1 - 2 x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 19 2013 *)
LinearRecurrence[{1,2,-2},{1,3,6,12},40] (* Harvey P. Dale, Mar 27 2019 *)

a(n)=([0,1,0; 0,0,1; -2,2,1]^n*[1;3;6])[1,1] \\ Charles R Greathouse IV, Feb 19 2017

Explicit formula given in Maple line.
a(n) = a(n-1)+2*a(n-2)-2*a(n-3) for n>3. G.f.: (1+2*x)*(1+x^2)/((1-x)*(1-2*x^2)). - Colin Barker, May 08 2012
a(n) = 3*A027383(n-1) for n>0, a(0)=1. - Bruno Berselli, May 08 2012

cp's OEIS Frontend

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

A061776 Start with a single triangle; at n-th generation add a triangle at each vertex, allowing triangles to overlap; sequence gives number of triangles in n-th generation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula