A372326 -id:A372326 - cp's OEIS frontend

A033815 Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

1, 1, 14, 426, 24024, 2170680, 287250480, 52370755920, 12585067447680, 3854801333416320, 1465957162768492800, 677696237345719468800, 374281829360322587827200, 243388909697235614324812800, 184070135024053703140543027200, 160192129141963141211280644352000

Offset: 0

N. J. A. Sloane

Also turns up as the solution to Problem #18, p. 326 of Alan Tucker's Applied Combinatorics, 4th ed, Wiley NY 2002 [Tucker's `n' is the `2n' here]. - John L Leonard, Sep 15 2003
Number of acyclic orientations of the Turán graph T(2n,n). - Alois P. Heinz, Jan 13 2016
n-th term of the n-th forward differences of n!. - Alois P. Heinz, Feb 22 2019

R. P. Stanley, Enumerative Combinatorics I, Chap.2, Exercise 10, p. 89.

Reinhard Zumkeller, Table of n, a(n) for n = 0..200
Leo Chao, Paul DesJarlais and John L Leonard, A binomial identity, via derangements, Math. Gaz. 89 (2005), 268-270.
Ira Gessel, Enumerative applications of symmetric functions, Séminaire Lotharingien de Combinatoire, B17a (1987), 17 pp.

Main diagonal of array in A068106 and of A047920.
Cf. A000142, A002119, A116854, A267383.
Column k=2 of A372326.

a033815 n = a116854 (2 * n + 1) (n + 1)
-- Reinhard Zumkeller, Aug 31 2014

A033815 := proc(n) local i; add(binomial(n, i)*(-1)^i*(2*n - i)!, i = 0 .. n) end;
# second Maple program:
A:= proc(n, k) A(n, k):= `if`(k=0, n!, A(n+1, k-1) -A(n, k-1)) end:
a:= n-> A(n$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 22 2019

a[n_] := (2n)!*Hypergeometric1F1[-n, -2n, -1]; Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Jun 13 2012, after Vladimir Reshetnikov *)

a(n) = A002119(n)*n!*(-1)^n.
D-finite with recurrence a(n) = 2n*(2n-1)*a(n-1) + n*(n-1)*a(n-2).
a(n) = Sum_{i=0..n} binomial(n, i)*(-1)^i*(2*n-i)!.
From John L Leonard, Sep 15 2003: (Start)
a(n) = Sum_{i=0..n} C(n, i)*(2n-i)!*Sum_{j=0..2n-i} (-1)^j/j!.
a(n) = n!*Sum_{i=0..n} C(n, i)*n!/(n-i)!*Sum_{j=0..n-i} (-1)^j*C(n-i, j)*(n-j)!/i!. (End)
a(n) = Sum_{k=0..n} binomial(n,k)*A000166(n+k). - Vladeta Jovovic, Sep 04 2006
a(n) = A116854(2*n+1,n+1). - Reinhard Zumkeller, Aug 31 2014
a(n) = A267383(2n,n). - Alois P. Heinz, Jan 13 2016
a(n) ~ sqrt(Pi) * 2^(2*n + 1) * n^(2*n + 1/2) / exp(2*n + 1/2). - Vaclav Kotesovec, Feb 18 2017
a(n) = n!*exp(-1/2)*((-1)^n * BesselI(n+1/2,1/2)*Pi^(1/2) + BesselK(n+1/2,1/2)/Pi^(1/2) ). - Mark van Hoeij, Jul 15 2022

A370961 a(n) = number of acyclic orientations of the complete tripartite graph K_{n,n,n}.

Original entry on oeis.org

1, 6, 426, 122190, 90768378, 138779942046, 379578822373866, 1689637343582548590, 11434884125767376107098, 111765072808554847704145086, 1515592947854931941485836600906, 27609710924806869786487193747541390, 658043992934027491354757341987635993018

Offset: 0

N. J. A. Sloane, Apr 04 2024

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..155 (terms n = 1..16 from Don Knuth)
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).

Cf. A212220, A266858, A267383, A370960.
Main diagonal of A372254.
Row n=3 of A372326.

a(n) = A266858(3n) = A267383(3n,3). - Alois P. Heinz, Apr 17 2024

a(n) = Sum_{k=0..3n} (-1)^k * A212220(n,k). - Alois P. Heinz, May 02 2024

More terms from Don Knuth, Apr 07 2024

a(0)=1 prepended by Alois P. Heinz, Apr 17 2024

A370613 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.

Original entry on oeis.org

1, 1, 1, 5, 9, 63, 509, 2959, 22453, 247949, 3080991, 28988331, 407320739, 5122243495, 82583577967, 1430027615585, 22556817627789, 395098668828675, 7979894546677853, 154786744386253387, 3355612019167352821, 78865333300205585345, 1769663675666499515751

Offset: 0

Alois P. Heinz, Apr 30 2024

nonn

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.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

Row sums of A370614.

Cf. A000009, A267383, A372254, A372261, A372326, A372395.

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`(i*(i+1)/2 abs(b(0, n$2)):
seq(a(n), n=0..22);

A370614 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 into distinct parts; triangle T(n,k), n>=0, k = 1..A000009(n), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 8, 1, 16, 46, 1, 32, 146, 330, 1, 64, 454, 1066, 1374, 1, 128, 1394, 4718, 5658, 10554, 1, 256, 4246, 20266, 23118, 41506, 57054, 101502, 1, 512, 12866, 85310, 93930, 237686, 302730, 525642, 657210, 1165104, 1, 1024, 38854, 354106, 380094

Offset: 0

Alois P. Heinz, Apr 30 2024

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.

			Triangle T(n,k) begins:
  1;
  1;
  1;
  1,   4;
  1,   8;
  1,  16,   46;
  1,  32,  146,   330;
  1,  64,  454,  1066,  1374;
  1, 128, 1394,  4718,  5658, 10554;
  1, 256, 4246, 20266, 23118, 41506, 57054, 101502;
  ...

Alois P. Heinz, Rows n = 0..46, flattened
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

Columns k=1-2 give: A000012, A011782 (for n>=3).
Row sums give A370613.
Cf. A000009, A267383, A372254, A372261, A372326, A372396.

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`(i*(i+1)/2 sort(b(n$2, [0]))[]:
seq(T(n), n=0..12);

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

Alois P. Heinz, Apr 17 2024

nonn

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.

Alois P. Heinz, Table of n, a(n) for n = 0..21
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph
Wikipedia, Turán graph

Main diagonal of A372326.

Cf. A267383.

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

Alois P. Heinz, Apr 29 2024

nonn

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.

Alois P. Heinz, Table of n, a(n) for n = 0..333
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

Row sums of A372396.

Cf. A000041, A267383, A372254, A372261, A372326, A370613.

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

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

Alois P. Heinz, Apr 29 2024

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.

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

Alois P. Heinz, Rows n = 0..28, flattened
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

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.

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

T(n,A000041(n)) = A000142(n).

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

cp's OEIS Frontend

A033815 Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A370961 a(n) = number of acyclic orientations of the complete tripartite graph K_{n,n,n}.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A370613 Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A370614 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 into distinct parts; triangle T(n,k), n>=0, k = 1..A000009(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula