A212084 -id:A212084 - cp's OEIS frontend

A048144 a(n) = Sum_{k=0..n} (k!)^2 * Stirling_2(n,k)^2.

1, 1, 5, 73, 2069, 95401, 6487445, 610093513, 75796724309, 12020754177001, 2369364111428885, 568128719132038153, 162835627057766030549, 54975855375379966645801, 21593185551426744571090325, 9762238510837560633366673993, 5033241437347149354018370856789

Offset: 0

N. J. A. Sloane

Number of digraphs with loops, with labeled vertices and labeled arcs, with n arcs and with no vertex of indegree 0 or outdegree 0, cf. A121936, A122418, A122399. - Vladeta Jovovic, Sep 06 2006
Chromatic invariant of the complete bipartite graph K_{n+1,n+1}. - Eric W. Weisstein, Jul 11 2011
Generally, for p >= 1, Sum_{k=0..n} (k!*StirlingS2(n,k))^p is asymptotic to n^(p*n+1/2) * sqrt(Pi/(2*p*(1-log(2))^(p-1))) / (exp(p*n) * log(2)^(p*n+1)). - Vaclav Kotesovec, May 10 2014

Alois P. Heinz, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Chromatic Invariant
Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Cf. A000670, A242280, A212084, A120732, A104602, A272644, A371761.

a := proc(n) local A, j; A := proc(n, k) option remember; if n = 0 then n^k else add(binomial(k + `if`(j>0, 1, 0), j+1) * A(n-1, k-j), j = 0..k) fi end: A(n,n) end:
seq(a(n), n = 0..16);  # Peter Luschny, Nov 20 2024

Table[Sum[(k!)^2*StirlingS2[n,k]^2,{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 07 2014 *)

a(n) = sum(k=0, n, k!^2*stirling(n, k, 2)^2); \\ Michel Marcus, Mar 07 2020

from functools import cache
from math import comb as binomial
@cache
def A(n, k): return int(k == 0) if n == 0 else sum(binomial(k + int(j > 0), j + 1) * A(n - 1, k - j) for j in range(k + 1))
a = lambda n: A(n, n)
print([a(n) for n in range(17)])  # Peter Luschny, Nov 20 2024

E.g.f.: Sum_{n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*(exp(j*x)-1)^n. a(n) = Sum_{k=0..n} Stirling2(n,k)*k!*A104602(k). - Vladeta Jovovic, Mar 25 2006
a(n) ~ sqrt(Pi/(1-log(2))) * n^(2*n+1/2) / (2*exp(2*n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, May 09 2014
E.g.f.: Sum_{n>=0} (1 - exp(-n*x))^n * exp(-n*x). - Paul D. Hanna, Mar 26 2018
E.g.f.: Sum_{n>=0} (exp(n*x) - 1)^n * exp(-n*(n+1)*x). - Paul D. Hanna, Mar 26 2018
a(n) = A272644(2n,n). - Alois P. Heinz, Oct 17 2024
a(n) = A371761(n, n). - Peter Luschny, Nov 20 2024
a(n) = (n!)^2 * [(x*y)^n] 1 / (exp(x) + exp(y) - exp(x + y)). - Ilya Gutkovskiy, Apr 24 2025

A092552 Let X_{m,n}(q) be the chromatic polynomial of the complete bipartite graph K_{m,n}. Then a(n) is the negative of the coefficient of the linear term of X_{n,n}(q).

Original entry on oeis.org

0, 1, 3, 31, 675, 25231, 1441923, 116914351, 12764590275, 1805409270031, 321113303226243, 70146437009397871, 18462286083671614275, 5762225835975165678031, 2104263061425865873128963, 888881838896989670838028591, 430058409024841744606172532675

Offset: 0

Michael Lugo (mtlugo(AT)mit.edu), Apr 09 2004

nonn

From Arvind Ayyer, Oct 25 2020: (Start)
Equivalently, a(n) is the number of acyclic orientations with a unique sink in K_{n,n}.
a(n) is also the number of toppleable permutations in S_{2n-1}. A toppleable permutation pi in S_{2n-1} satisfies pi_i <= n-1+i for 1 <= i <= n-1 and pi_i >= i-n+1 for n <= i <= 2n-1. The a(3)=3 toppleable permutations in S_3 are 123, 213 and 132. (End)

			a(2) = 3 since the chromatic polynomial of K_{2,2}(q) is q^4-4*q^3+6*q^2-3*q.
E.g.f.: A(x) = x + 3*x^2/2! + 31*x^3/3! + 675*x^4/4! + 25231*x^5/5! +...
where A(x) = (1-exp(-x)) + (1-exp(-2*x))^2/2 + (1-exp(-3*x))^3/3 +... - _Paul D. Hanna_, Dec 06 2012
O.g.f.: F(x) = x + 3*x^2 + 31*x^3 + 675*x^4 + 25231*x^5 +...
where F(x) = x/(1+x) + 2^1*2!*x^2/((1+2*1*x)*(1+2*2*x)) + 3^2*3!*x^3/((1+3*1*x)*(1+3*2*x)*(1+3*3*x)) + 4^3*4!*x^4/((1+4*1*x)*(1+4*2*x)*(1+4*3*x)*(1+4*4*x)) +... - _Paul D. Hanna_, Jan 05 2013

Alois P. Heinz, Table of n, a(n) for n = 0..238
A. Ayyer, D. Hathcock and P. Tetali, Toppleable Permutations, Excedances and Acyclic Orientations, arXiv:2010.11236 [math.CO], 2020. For the precise definition of a toppleable permutation.

Cf. A008277, A212084, A220179, A136126, A306209.

a:= n-> -coeff(add(Stirling2(n, k) *mul(q-i, i=0..k-1)
             *(q-k)^n, k=1..n), q, 1):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 30 2012

Table[Sum[k!*(k-1)!*StirlingS2[n,k]^2,{k,1,n}],{n,0,20}] (* Vaclav Kotesovec, Jun 21 2013 *)

{a(n)=n!*polcoeff(sum(k=1,n,(1-exp(-k*x+x*O(x^n)))^k/k),n)} \\ Paul D. Hanna, Dec 06 2012
for(n=0,20,print1(a(n),", "))

{Stirling2(n, k)=n!*polcoeff(((exp(x+x*O(x^n))-1)^k)/k!, n)}
{a(n)=if(n<=0, 0, sum(k=1, n, k!*(k-1)! * Stirling2(n, k)^2))} \\ Paul D. Hanna, Dec 30 2012
for(n=0, 20, print1(a(n), ", "))

{a(n)=if(n<1,0,polcoeff(sum(m=1, n, m^(m-1)*m!*x^m/prod(k=1, m, 1+m*k*x+x*O(x^n))), n))} \\ Paul D. Hanna, Jan 05 2013

From Alois P. Heinz, Apr 30 2012: (Start)
a(n) = (-1) * [q] Sum_{j=1..n} (q-j)^n*S2(n,j)*Product_{i=0..j-1} (q-i).
a(n) = (-1) * A212084(n,2n-1). (End)
E.g.f.: Sum_{n>=1} (1 - exp(-n*x))^n / n. - Paul D. Hanna, Dec 06 2012
a(n) = Sum_{k=1..n} k!*(k-1)! * Stirling2(n, k)^2. - Paul D. Hanna, Dec 30 2012, corrected by Vaclav Kotesovec, Jun 21 2013
O.g.f.: Sum_{n>=1} n^(n-1) * n! * x^n / Product_{k=1..n} (1 + n*k*x). - Paul D. Hanna, Jan 05 2013
a(n) = A136126(2*n-1,n), where triangle A136126(n,k) is the number of permutations of {1,2,...,k+n} having excedance set {1,2,...,k}. - Paul D. Hanna, Feb 01 2013
a(n) ~ sqrt(Pi) * n^(2*n-1/2) / (sqrt(1-log(2)) * exp(2*n) * (log(2))^(2*n)). - Vaclav Kotesovec, Nov 07 2014
a(n) = A306209(2n-1,n-1) for n > 0. - Alois P. Heinz, Feb 01 2019

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

A212085 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the complete bipartite graph K_(k,k).

Original entry on oeis.org

0, 0, 2, 0, 2, 6, 0, 2, 18, 12, 0, 2, 42, 84, 20, 0, 2, 90, 420, 260, 30, 0, 2, 186, 1812, 2420, 630, 42, 0, 2, 378, 7332, 18500, 9750, 1302, 56, 0, 2, 762, 28884, 127220, 121590, 30702, 2408, 72, 0, 2, 1530, 112740, 825860, 1324470, 583422, 81032, 4104, 90

Offset: 1

Alois P. Heinz, Apr 30 2012

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

A(n,k) is the number of pairs of strings of length k over an alphabet of size n such that the strings do not share any letter. - Lin Zhangruiyu, Aug 19 2022

			A(3,1) = 6 because there are 6 3-colorings of the complete bipartite graph K_(1,1): 1-2, 1-3, 2-1, 2-3, 3-1, 3-2.
Square array A(n,k) begins:
   0,   0,    0,      0,       0,        0,         0, ...
   2,   2,    2,      2,       2,        2,         2, ...
   6,  18,   42,     90,     186,      378,       762, ...
  12,  84,  420,   1812,    7332,    28884,    112740, ...
  20, 260, 2420,  18500,  127220,   825860,   5191220, ...
  30, 630, 9750, 121590, 1324470, 13284630, 126657750, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Wikipedia, Chromatic Polynomial

Rows n=1-3 give: A000004, A007395, A068293(k+1).
Columns k=1-2 give: A002378(n-1), A091940.
Cf. A008277, A212084, A266695, A282245.

A:= (n, k)-> add(Stirling2(k, j) *mul(n-i, i=0..j-1) *(n-j)^k, j=1..k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);

a[n_, k_] := Sum[(-1)^j*(n-j)^k*Pochhammer[-n, j]*StirlingS2[k, j], {j, 1, k}]; Table[a[n-k, k], {n, 1, 11}, {k, n-1, 1, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)

A(n,k) = Sum_{j=1..k} (n-j)^k * S2(k,j) * Product_{i=0..j-1} (n-i).

A(n,n)/n = A282245(n).

A266972 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: row n gives the coefficients of the chromatic polynomial of the (n,2)-Turán graph, highest powers first.

Original entry on oeis.org

1, 1, 0, 1, -1, 0, 1, -2, 1, 0, 1, -4, 6, -3, 0, 1, -6, 15, -17, 7, 0, 1, -9, 36, -75, 78, -31, 0, 1, -12, 66, -202, 351, -319, 115, 0, 1, -16, 120, -524, 1400, -2236, 1930, -675, 0, 1, -20, 190, -1080, 3925, -9164, 13186, -10489, 3451, 0, 1, -25, 300, -2200, 10650, -34730, 75170, -102545, 78610, -25231, 0

Offset: 0

Alois P. Heinz, Jan 07 2016

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

			Triangle T(n,k) begins:
  1;
  1,   0;
  1,  -1,   0;
  1,  -2,   1,    0;
  1,  -4,   6,   -3,    0;
  1,  -6,  15,  -17,    7,     0;
  1,  -9,  36,  -75,   78,   -31,    0;
  1, -12,  66, -202,  351,  -319,  115,    0;
  1, -16, 120, -524, 1400, -2236, 1930, -675,  0;
  ...

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

Columns k=0-1 give: A000012, (-1)*A002620.
Main diagonal gives A000007.
Cf. A212084, A266695.

P:= n-> (h-> expand(add(Stirling2(h, j)*mul(q-i,
    i=0..j-1)*(q-j)^(n-h), j=0..h)))(iquo(n, 2)):
T:= n-> (p-> seq(coeff(p, q, n-i), i=0..n))(P(n)):
seq(T(n), n=0..12);

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

Sum_{k=0..n} abs(T(n,k)) = A266695(n).

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Original entry on oeis.org

1, 1, 2, 1, 1, 6, 11, 6, 1, 1, 14, 61, 86, 50, 12, 1, 1, 30, 275, 770, 927, 530, 150, 20, 1, 1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1, 1, 126, 4571, 38626, 134981, 228382, 209428, 110768, 34902, 6580, 721, 42, 1, 1, 254, 18061, 248766, 1367310, 3553564, 4989621, 4093126, 2061782, 655788, 132958, 16996, 1316, 56, 1

Offset: 1

Andrew Howroyd, Jun 18 2025

Permuting the colors does not change the coloring. T(n,k) is the number of ways to partition the vertices into k independent sets.

			Triangle begins (n >= 1, k >= 2):
  1;
  1,  2,    1;
  1,  6,   11,    6,     1;
  1, 14,   61,   86,    50,    12,    1;
  1, 30,  275,  770,   927,   530,  150,   20,   1;
  1, 62, 1141, 5710, 12160, 12632, 6987, 2130, 355, 30, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2500 (rows 1..50)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Vertex Coloring.

Row sums are A001247.
Columns k=2..5 are A000012, A000918, A384980, A384981.
Cf. A008277, A212084, A274310.

T(n,k) = sum(j=1, k-1, stirling(n,j,2)*stirling(n,k-j,2))
for(n=1, 7, print(vector(2*n-1,k,T(n,k+1))))

T(n,k) = Sum_{j=1..k-1} Stirling2(n,j)*Stirling2(n,k-j).

T(n,k) = A274310(2*n-1, k-1).

cp's OEIS Frontend

A048144 a(n) = Sum_{k=0..n} (k!)^2 * Stirling_2(n,k)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A092552 Let X_{m,n}(q) be the chromatic polynomial of the complete bipartite graph K_{m,n}. Then a(n) is the negative of the coefficient of the linear term of X_{n,n}(q).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212085 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the complete bipartite graph K_(k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A266972 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: row n gives the coefficients of the chromatic polynomial of the (n,2)-Turán graph, highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A384968 Triangle read by rows: T(n,k) is the number of proper vertex colorings of the n-complete bipartite graph using exactly k interchangeable colors, 2 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula