cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 20 results.

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

Original entry on oeis.org

1, 1, 14, 122190, 4154515368024, 1835278052687560517522520, 26375779571296696625528695444035039796080, 25932533306693349690666903275634586837883421559437937952074800, 3259525010466811026507391843042719132975543560928683870154345751824625274129141118944640
Offset: 0

Views

Author

Alois P. Heinz, Apr 17 2024

Keywords

Comments

The Turán graph T(n^2,n) is the complete n-partite graph K_{n,...,n}.
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

Crossrefs

Main diagonal of A372326.
Cf. A267383.

Formula

a(n) = A267383(n^2,n).

A372395 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.

Original entry on oeis.org

1, 1, 3, 11, 65, 411, 3535, 31081, 337185, 3846557, 50329253, 691740489, 10725769171, 172411994899, 3050277039465, 56428854605627, 1124781474310649, 23349607769846667, 518744693882444419, 11949343411110856153, 291921874093876965453, 7395266131906154621501
Offset: 0

Views

Author

Alois P. Heinz, Apr 29 2024

Keywords

Comments

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.
All terms are odd.

Links

Crossrefs

Row sums of A372396.
Cf. A000041, A267383, A372254, A372261, A372326, A370613.

Programs

  • Maple
    g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
b:= proc(t, n, i) option remember; `if`(n=0, t!*(-1)^t,
     `if`(i<1, 0, b(t, n, i-1)+add(coeff(g(i), x, m)*
        b(t+m, n-i, min(n-i, i)), m=0..i)))
    end:
a:= n-> abs(b(0, n$2)):
seq(a(n), n=0..21);
  • Mathematica
    g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
b[t_, n_, i_] := b[t, n, i] = If[n == 0, t!*(-1)^t, If[i < 1, 0, b[t, n, i - 1] + Sum[Coefficient[g[i], x, m]*b[t + m, n - i, Min[n - i, i]], {m, 0, i}]]];
a[n_] := Abs[b[0, n, n]];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 24 2024, after Alois P. Heinz *)

A372396 Triangle T(n,k) in which row n lists in increasing order the number of acyclic orientations of complete multipartite graphs K_lambda, where lambda is a partition of n; triangle T(n,k), n>=0, k = 1..A000041(n), read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 6, 1, 8, 14, 18, 24, 1, 16, 46, 54, 78, 96, 120, 1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720, 1, 64, 454, 486, 1066, 1374, 1536, 1902, 2286, 2616, 3000, 3216, 3720, 4320, 5040, 1, 128, 1394, 1458, 4718, 5658, 6144, 6902, 10554, 12090
Offset: 0

Views

Author

Alois P. Heinz, Apr 29 2024

Keywords

Comments

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.

Examples

			Triangle T(n,k) begins:
  1;
  1;
  1,  2;
  1,  4,   6;
  1,  8,  14,  18,  24;
  1, 16,  46,  54,  78,  96, 120;
  1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720;
  ...

Links

Crossrefs

Columns k=1-3 give: A000012, A011782 (for n>=2), A027649(n-2) (for n>=4).
Row sums give A372395.
Cf. A000041, A000142, A001563, A267383, A372254, A372261, A372326, A370614.

Programs

  • Maple
    g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
h:= proc() option remember; local q, l, b; q, l, b:= -1, args,
      proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
        (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
      end; abs(b(0, nops(l)))
    end:
b:= proc(n, i, l) `if`(n=0 or i=1, [h([l[], 1$n, 0])],
     [b(n-i, min(n-i, i), [l[], i])[], b(n, i-1, l)[]])
    end:
T:= n-> sort(b(n$2, []))[]:
seq(T(n), n=0..10);

Formula

T(n,A000041(n)) = A000142(n).
T(n,A000041(n)-1) = A001563(n-1) for n>=2.

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

Original entry on oeis.org

1, 1, 2, 6, 24, 96, 504, 3216, 24024, 177816, 1538424, 15108216, 165392664, 1793999256, 21693217464, 288019921656, 4154515368024, 59434596913656, 924041894967864, 15469081577068056, 276917744041735704, 4921195271561687256, 93549435117715431864
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=4 of A267383.

Formula

a(n) ~ n! / (3 * (1-log(4/3))^(3/2) * 4^n * (log(4/3))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 600, 3720, 27240, 229080, 2170680, 20452440, 217008600, 2550317880, 32808887160, 457907248920, 6355848354360, 95721761831160, 1551458493435480, 26890032710452440, 495810323060597880, 9097662007250393880, 177624183228083188440
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=5 of A267383.

Formula

a(n) ~ n! / (4 * (1 - log(5/4))^2 * 5^n * (log(5/4))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 4320, 30960, 256320, 2399760, 25022880, 287250480, 3284869680, 41344521840, 566715682800, 8391341277360, 133348995238320, 2262083352430320, 38232720235613520, 689864650481977200, 13221780471876281040, 268029961230742291440
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=6 of A267383.

Formula

a(n) ~ n! / (5 * (1 - log(6/5))^(5/2) * 6^n * (log(6/5))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 35280, 287280, 2656080, 27422640, 312273360, 3884393520, 52370755920, 704126188080, 10259633739600, 160825241006640, 2696186419390800, 48104638617656880, 909616190783645520, 18163810790066314800, 361758057531039101520
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=7 of A267383.

Formula

a(n) ~ n! / (6 * (1 - log(7/6))^3 * 7^n * (log(7/6))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 322560, 2943360, 30078720, 339696000, 4196666880, 56255149440, 812752093440, 12585067447680, 194465276369280, 3220308737573760, 56845456896816000, 1064856592650695040, 21087473349235547520, 440007278378842984320
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=8 of A267383.

Formula

a(n) ~ n! / (7 * (1 - log(8/7))^(7/2) * 8^n * (log(8/7))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3265920, 33022080, 369774720, 4536362880, 60451816320, 869007242880, 13397819541120, 220448163358080, 3854801333416320, 67295207974942080, 1248445283166184320, 24512281966435294080, 507579925622189454720
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=9 of A267383.

Formula

a(n) ~ n! / (8 * (1 - log(9/8))^4 * 9^n * (log(9/8))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

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

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 36288000, 402796800, 4906137600, 64988179200, 929459059200, 14266826784000, 233845982899200, 4075249496774400, 75225258805132800, 1465957162768492800, 28530213421847558400, 586170618419794464000
Offset: 0

Views

Author

Alois P. Heinz, Jan 13 2016

Keywords

Comments

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

Crossrefs

Column k=10 of A267383.

Formula

a(n) ~ n! / (9 * (1 - log(10/9))^(9/2) * 10^n * (log(10/9))^(n+1)). - Vaclav Kotesovec, Feb 18 2017
Previous Showing 11-20 of 20 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.