A266972 -id:A266972

Search: a266972 -id:a266972

Displaying 1-3 of 3 results found.

page 1

A266695

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

+10
9

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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.

LINKS

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

FORMULA

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

MAPLE

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

MATHEMATICA

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

CROSSREFS

Column k=2 of A267383.

Cf. A099594, A212084, A212085, A266858, A266972.

Bisections give A048163 (even part), A188634 (odd part).

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jan 02 2016

STATUS

approved

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.

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

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.

LINKS

Alois P. Heinz, Rows n = 0..90, flattened

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Wikipedia, Chromatic Polynomial

FORMULA

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

EXAMPLE

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

...

MAPLE

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

CROSSREFS

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.

KEYWORD

sign,tabf

AUTHOR

Alois P. Heinz, Apr 30 2012

EXTENSIONS

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

STATUS

approved

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.

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

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

REFERENCES

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

LINKS

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

FORMULA

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

MAPLE

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

MATHEMATICA

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

PROG

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

CROSSREFS

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

Cf. A266972.

KEYWORD

nonn,nice,easy

AUTHOR

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

STATUS

approved

page 1

Search completed in 0.008 seconds