A003024 -id:A003024 - cp's OEIS frontend

A182161 Number of extensional acyclic digraphs on n labeled nodes.

1, 1, 2, 12, 216, 10560, 1297440, 381013920, 258918871680, 398362519618560, 1366301392119014400, 10325798296570753920000, 170397664079650720884864000, 6094923358716319193283074457600, 469649545161250827117772066578739200, 77556106803568453086056722450983544320000

Offset: 0

N. J. A. Sloane, Apr 15 2012

nonn

S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).

Cf. A001192, A003024. Row sums of A182162.

a(n) = n!*A001192(n).

A207259 The number of 2 X 2 matrices with no real eigenvalues and whose entries are integers of absolute value at most n.

Original entry on oeis.org

14, 148, 642, 1832, 4246, 8420, 15202, 25296, 39742, 59668, 86338, 120840, 165174, 220356, 288322, 370816, 470254, 587940, 726994, 888728, 1076422, 1292404, 1539442, 1819440, 2136734, 2493700, 2893586, 3339544, 3835782, 4384036, 4990466, 5656752, 6388158

Offset: 1

W. Edwin Clark, Nov 26 2012

Hiroaki Yamanouchi and Chai Wah Wu, Table of n, a(n) for n = 1..1000 (terms for n = 1..100 from Hiroaki Yamanouchi)

Cf. A003024, A219736, A219744.

a:=proc(n)
local x,y,z,w,Eig,count;
count:=0;
for x from -n to n do
for y from -n to n do
for z from -n to n do
for w from -n to n do
Eig:=LinearAlgebra:-Eigenvalues(Matrix([[x,y],[z,w]]));
if Im(Eig[1]) <> 0  then count:=count+1; fi;
od:
od:
od:
od:
count;
end:

a(n) = (2*n+1)^4 - A219736(n).

a(16)-a(33) from Hiroaki Yamanouchi, Oct 03 2014

A219736 The number of 2 X 2 matrices with all eigenvalues real and whose entries are integers with absolute value at most n.

Original entry on oeis.org

67, 477, 1759, 4729, 10395, 20141, 35423, 58225, 90579, 134813, 193503, 269785, 366267, 486925, 635199, 815105, 1030371, 1286221, 1586447, 1937033, 2342379, 2808221, 3340239, 3945361, 4628467, 5396781, 6257039, 7216457, 8281579, 9461805, 10762495, 12193873

Offset: 1

W. Edwin Clark, Nov 26 2012

Hiroaki Yamanouchi and Chai Wah Wu, Table of n, a(n) for n = 1..1000 (terms for n = 1..100 from Hiroaki Yamanouchi)

Cf. A003024, A207259.

a:=proc(n)
local x,y,z,w,Eig,count;
count:=0;
for x from -n to n do
for y from -n to n do
for z from -n to n do
for w from -n to n do
Eig:=LinearAlgebra:-Eigenvalues(Matrix([[x,y],[z,w]]));
if Im(Eig[1]) = 0  then count:=count+1; fi;
od:
od:
od:
od:
count;
end:

a(n) = (2*n+1)^4 - A207259(n).

a(16)-a(32) from Hiroaki Yamanouchi, Oct 03 2014

A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

Original entry on oeis.org

1, 0, 1, 0, -1, 2, 0, 5, -12, 8, 0, -79, 208, -192, 64, 0, 3377, -9520, 10240, -5120, 1024, 0, -362431, 1079744, -1282560, 778240, -245760, 32768, 0, 93473345, -291615296, 372893696, -255754240, 100925440, -22020096, 2097152, 0, -56272471039, 182582658048, -247557029888, 185511968768, -84263567360, 23488102400, -3758096384, 268435456

Offset: 0

Peter Bala, Apr 16 2013

A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a k-coloring function for the graph. The chromatic polynomial P(G,k) of a simple graph G gives the number of different k-colorings functions of the graph as a function of k. P(G,k) is a polynomial function of k.

The row polynomials R(n,x) of this triangle are defined to be the sum of the chromatic polynomials of all labeled simple graphs on n vertices: R(n,x) = sum {labeled graphs G on n nodes} P(G,x). An example is given below.

			Triangle begins:
  n\k.|..0.....1......2.......3......4.......5
  = = = = = = = = = = = = = = = = = = = = = = =
  .0..|..1
  .1..|..0.....1
  .2..|..0....-1......2
  .3..|..0.....5....-12.......8
  .4..|..0...-79....208....-192.....64
  .5..|..0..3377..-9520...10240..-5120....1024
  ...
Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely
(a)  o    o    o    (b)  o    o----o    (c)  o----o----o
(d)   0
     / \
    0---0
with chromatic polynomials x^3, x^2*(x-1), x*(x-1)^2 and (x-1)^3 - (x-1), respectively. Allowing for labeling, there is 1 labeled graph of type (a), 3 labeled graphs of type (b), 3 labeled graphs of type (c) and 1 labeled graph of type (d). Thus the sum of the chromatic polynomials over all labeled graphs on 3 nodes is x^3 + 3*x^2*(x-1) + 3*x*(x-1)^2  + (x-1)^3 - (x-1) = 5*x - 12*x^2 + 8*x^3.
Row 3 of A058843 is [1,12,8]. Thus R(3,x) = x + 12*x*(x-1) + 8*x*(x-1)*(x-2) = 5*x - 12*x^2 + 8*x^3.

Alois P. Heinz, Rows n = 0..77, flattened
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Exponential structures
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Wikipedia, Graph coloring

Cf. A003024 (alt. row sums), A006125 (main diagonal), A095351 (main subdiagonal), A134531 (column 1), A058843, A322280.

R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
      binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
    end:
T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(R(n)):
seq(T(n), n=0..10);  # Alois P. Heinz, May 16 2024

r[0] = 1; r[1] = x; r[n_] := r[n] = x*Sum[ Binomial[n-1, k]*2^(k*(n-k))*(r[k] /. x -> x-1), {k, 0, n-1}]; row[n_] := CoefficientList[ r[n], x]; Table[ row[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Apr 17 2013 *)

Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function for the triangle is E(z)^x = Sum_{n >= 0} R(n,x)*z^n/(n!*2^C(n,2)) = 1 + x*z + (-x + 2*x^2)*z^2/(2!*2) + (5*x - 12*x^2 + 8*x^3)*z^3/(3!*2^3) + ....
The row polynomials satisfy the recurrence equation: R(0,x) = 1 and
R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).
In terms of the basis of falling factorial polynomials we have, for n >= 1, R(n,x) = Sum_{k = 1..n} A058843(n,k)*x*(x-1)*...*(x-k+1).
The polynomials R(n,x)/2^comb(n,2) form a sequence of binomial type (see Stanley). Setting D = d/dx, the associated delta operator begins D + D^2/(2!*2) + D^3/(3!*2^3) - D^4/(4!*2^4) + 23*D^5/(5!*2^5) + 559*D^6/(6!*2^6) - ... obtained by series reversion of the formal series D - D^2/(2!*2) + 5*D^3/(3!*2^3) - 79*D^4/(4!*2^4) + 3377*D^5/(5!*2^5) - ... coming from column 1 of the triangle.
Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.
The row polynomials evaluated at k is A322280(n,k). - Geoffrey Critzer, Mar 02 2024
Let k>=1 and let D be a directed acyclic graph with vertices labeled on [n].  Then (-1)^n*R(n,-k) is the number of maps C:[n]->[k] such that for all vertices i,j in [n], if i is directed to j in D then C(i)>=C(j).  Cf A003024 (k=1), A339934 (k=2). - Geoffrey Critzer, May 15 2024

A339768 Square array read by descending antidiagonals. T(n,k) is the number of acyclic k-multidigraphs on n labeled vertices, n>=0,k>=0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 25, 1, 1, 1, 7, 109, 543, 1, 1, 1, 9, 289, 9449, 29281, 1, 1, 1, 11, 601, 63487, 3068281, 3781503, 1, 1, 1, 13, 1081, 267249, 69711361, 3586048685, 1138779265, 1

Offset: 0

Geoffrey Critzer, Feb 21 2021

Here, a k-multidigraph is a directed graph where up to k arcs (directed edges) are allowed to join vertex pairs. The arcs have no identity, i.e., they are indistinguishable except for the ordered pair of distinct vertices that they join.

			  1,     1,       1,        1,         1,          1, ...
  1,     1,       1,        1,         1,          1, ...
  1,     3,       5,        7,         9,         11, ...
  1,    25,     109,      289,       601,       1081, ...
  1,   543,    9449,    63487,    267249,     849311, ...
  1, 29281, 3068281, 69711361, 742650001, 5004309601, ...

Seiichi Manyama, Antidiagonals n = 0..50, flattened
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A003024 (column k=1), A188457 (column k=2), A137435 (column k=3).

Main diagonal gives A354962.

nn = 5; Table[g[n_] := q^Binomial[n, 2] n!; e[z_] := Sum[z^k/g[k], {k, 0, nn}];
   Table[g[n], {n, 0, nn}] CoefficientList[Series[1/e[-z], {z, 0, nn}], z], {q, 1, nn + 1}] //Transpose // Grid

Let E(x) = Sum_{n>=0} x^n/(n!*(k+1)^binomial(n,2)). Then 1/E(-x) = Sum_{n>=0} T(n,k)x^n/(n!*(k+1)^binomial(n,2)).

T(0,k) = 1 and T(n,k) = Sum_{j=1..n} (-1)^(j+1) * (k+1)^(j*(n-j)) * binomial(n,j) * T(n-j,k) for n > 0. - Seiichi Manyama, Jun 13 2022

A355612 Number of labeled digraphs on [n] such that for any pair C_1,C_2 of distinct strongly connected components, if x in C_1 is directed to y in C_2 then every vertex in C_1 is directed to every vertex in C_2.

Original entry on oeis.org

1, 1, 4, 52, 2524, 629296, 750098464, 3540134362192, 63605185617860464, 4402130837352016607296, 1190565802204629673473661504, 1270503156085666608161173288964992, 5381113705726490960372769906727545572224, 90765998703828737395601069325546106634460887296, 6109068274998388232409260496587163340177606642565219584

Offset: 0

Geoffrey Critzer, Jul 09 2022

nonn

Here a digraph can have both a directed edge from x to y and y to x but no self loops are allowed.

Cf. A003024, A003030.

nn = 14; d[x_] := Total[Cases[Import["https://oeis.org/A003024/b003024.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 41}]];
s[x_] := Total[ Prepend[Cases[Import["https://oeis.org/A003030/b003030.txt",
       "Table"], {, }][[All, 2]], 1]* Table[x^(i - 1)/(i - 1)!, {i, 1, 59}]];
Range[0, nn]! CoefficientList[Series[d[s[x] - 1], {x, 0, nn}], x]

E.g.f.: D(S(x)-1) where D(x),S(x) are the e.g.f.'s for A003024 and A003030 respectively.

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 4, 12, 0, 144, 168, 200, 0, 25696, 18768, 12384, 8688, 0, 18082560, 8697280, 3923040, 1914560, 936992, 0, 47025585664, 14670384000, 4512045120, 1622358720, 647087040, 242016192, 0, 450955726792704, 87781550054912, 17679638000640, 4496696041600, 1408276410240, 482302375296, 145763745920

Offset: 0

Geoffrey Critzer, Mar 06 2023

			  1;
  0,     2;
  0,     4,    12;
  0,   144,   168,   200;
  0, 25696, 18768, 12384, 8688;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
Wikipedia, Strongly connected component

Cf. A003030, A003024, A002416 (row sums).

nn =15; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]]; begf = Total[CoefficientList[ Series[1/(Total[CoefficientList[Series[ Exp[-u *s[x]], {x, 0, nn}], x]* Table[z^n/(2^Binomial[n, 2]), {n, 0, nn}]]), {z, 0, nn}],z]*Table[z^n 2^Binomial[n, 2], {n, 0, nn}]] /. z -> 2 z;
Range[0, nn]! CoefficientList[begf, {z, u}] // Grid (* Geoffrey Critzer, Mar 14 2023 after Andrew Howroyd *)

Z(p, f)={my(n=serprec(p, x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e, p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e, p)={Z(p, k->e^(k*(k-1)/2))}
RelEgf(n, e)={sum(k=0, n, e^(k^2)*x^k/k!, O(x*x^n) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, RelEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 06 2023

E.g.f. for column 1: A(2*x) where A(x) is the e.g.f. for A003030.

E.g.f. for main diagonal: B(2*x) where B(x) is the e.g.f. for A003024.

Terms a(15) and beyond from Andrew Howroyd, Mar 06 2023

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 18, 21, 25, 0, 1606, 1173, 774, 543, 0, 565080, 271790, 122595, 59830, 29281, 0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503, 0, 3523091615568, 685793359804, 138122171880, 35130437825, 11002159455, 3767987307, 1138779265

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,         1;
  0,         1,         3;
  0,        18,        21,       25;
  0,      1606,      1173,      774,      543;
  0,    565080,    271790,   122595,    59830,    29281;
  0, 734774776, 229224750, 70500705, 25349355, 10110735, 3781503;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50).

Column k=1 is A003030.
Main diagonal is A003024.
Row sums are A053763.
The unlabeled version is A361582.
Cf. A189898 (weak components), A361269 (loops allowed), A361591.

Z(p, f)={my(n=serprec(p, x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e, p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e, p)={Z(p, k->e^(k*(k-1)/2))}
DigraphEgf(n, e)={sum(k=0, n, e^(k*(k-1))*x^k/k!, O(x*x^n) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, DigraphEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) }

T(n,k) = A361269(n,k)/2^n.

A361592 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k strongly connected components of size 1, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 18, 21, 0, 25, 1699, 1080, 774, 0, 543, 587940, 267665, 103860, 59830, 0, 29281, 750744901, 225144360, 64169325, 19791000, 10110735, 0, 3781503, 3556390155318, 672637205149, 126726655860, 29445913175, 7939815030, 3767987307, 0, 1138779265

Offset: 0

Geoffrey Critzer, Mar 16 2023

			Triangle begins:
       1;
       0,      1;
       1,      0,      3;
      18,     21,      0,    25;
    1699,   1080,    774,     0, 543;
  587940, 267665, 103860, 59830,   0, 29281;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
Wikipedia, Strongly connected component

Cf. A086366 (column k=0), A003024 (main diagonal), A053763 (row sums), A361590 (unlabeled version).

nn = 7; B[n_] := n! 2^Binomial[n, 2]; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]];s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]]; ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggfz[Exp[-(s[x] - x + u x)]], {z, 0, nn}], {z,u}])[[i]], i], {i, 1, nn + 1}] // Grid

A361718 Triangular array read by rows. T(n,k) is the number of labeled directed acyclic graphs on [n] with exactly k nodes of indegree 0.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 15, 9, 1, 0, 316, 198, 28, 1, 0, 16885, 10710, 1610, 75, 1, 0, 2174586, 1384335, 211820, 10575, 186, 1, 0, 654313415, 416990763, 64144675, 3268125, 61845, 441, 1, 0, 450179768312, 286992935964, 44218682312, 2266772550, 43832264, 336924, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 02 2023

Also the number of sets of n nonempty subsets of {1..n}, k of which are singletons, such that there is only one way to choose a different element from each. For example, row n = 3 counts the following set-systems:
  {{1},{1,2},{1,3}}    {{1},{2},{1,3}}    {{1},{2},{3}}
  {{1},{1,2},{2,3}}    {{1},{2},{2,3}}
  {{1},{1,3},{2,3}}    {{1},{3},{1,2}}
  {{2},{1,2},{1,3}}    {{1},{3},{2,3}}
  {{2},{1,2},{2,3}}    {{2},{3},{1,2}}
  {{2},{1,3},{2,3}}    {{2},{3},{1,3}}
  {{3},{1,2},{1,3}}    {{1},{2},{1,2,3}}
  {{3},{1,2},{2,3}}    {{1},{3},{1,2,3}}
  {{3},{1,3},{2,3}}    {{2},{3},{1,2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{1,3},{1,2,3}}
  {{2},{1,2},{1,2,3}}
  {{2},{2,3},{1,2,3}}
  {{3},{1,3},{1,2,3}}
  {{3},{2,3},{1,2,3}}

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,    15,     9,    1;
  0,   316,   198,   28,  1;
  0, 16885, 10710, 1610, 75, 1;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Cf. A058876 (mirror), A361579, A224069.
Row-sums are A003024, unlabeled A003087.
Column k = 1 is A003025(n) = |n*A134531(n)|.
Column k = n-1 is A058877.
For fixed sinks we get A368602.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A000169, A059201, A082402, A088957, A133686, A334282, A350415, A367904, A367908, A368600, A368601.

nn = 8; B[n_] := n! 2^Binomial[n, 2] ;ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /. Table[z^i -> z^i/2^Binomial[i, 2], {i, 0, nn}];Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[ Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-z]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid
nv=4;Table[Length[Select[Subsets[Subsets[Range[n]],{n}], Count[#,{_}]==k&&Length[Select[Tuples[#], UnsameQ@@#&]]==1&]],{n,0,nv},{k,0,n}]

T(n,k) = A368602(n,k) * binomial(n,k). - Gus Wiseman, Jan 03 2024

cp's OEIS Frontend

A182161 Number of extensional acyclic digraphs on n labeled nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A207259 The number of 2 X 2 matrices with no real eigenvalues and whose entries are integers of absolute value at most n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

Extensions

A219736 The number of 2 X 2 matrices with all eigenvalues real and whose entries are integers with absolute value at most n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

Extensions

A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339768 Square array read by descending antidiagonals. T(n,k) is the number of acyclic k-multidigraphs on n labeled vertices, n>=0,k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A355612 Number of labeled digraphs on [n] such that for any pair C_1,C_2 of distinct strongly connected components, if x in C_1 is directed to y in C_2 then every vertex in C_1 is directed to every vertex in C_2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A361455 Triangle read by rows: T(n,k) is the number of simple digraphs on labeled n nodes with k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs