A003024 -id:A003024 - cp's OEIS frontend

A365593 Number of n X n Boolean relation matrices such that every block of its Frobenius normal form is either a 0 block or a 1 block.

1, 2, 13, 219, 9322, 982243, 249233239, 148346645212, 202688186994599, 624913864623500599, 4289324010827093793808, 64841661094150427710360745, 2140002760057211517052090865983, 153082134018816602622335941790247946, 23590554099141037133024176892280338280237

Offset: 0

Geoffrey Critzer, Sep 10 2023

nonn

A 1(0) block is such that every entry in the block is 1(0). If a Boolean relation matrix R is limit dominating then it must be that every block of R is either a 0 block or a 1 block. See Theorem 1.2 in Gregory, Kirkland, and Pullman.

Conjecture: lim_n->inf a(n)/(A003024(n)*2^n) = 1. In other words, almost all of the relations counted by this sequence have n strongly connected components. - Geoffrey Critzer, Sep 30 2023

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.

Cf. A003024, A355612, A365534, A365590, A366141.

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

E.g.f.: D(exp(x)-1+x) where D(x) is the e.g.f. for A003024.

A087613 Number of labeled acyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

1, 4, 62, 3608, 765664, 577696816

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087614 for the unlabeled analog, A003024, A087615.

A087615 Number of labeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Original entry on oeis.org

0, 0, 2, 488, 282912, 496045008

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Sep 12 2003

Jobst Heitzig, Social Choice Under Incomplete, Cyclic Preferences, arXiv:math/0201285 [math.CO], 2002.

Cf. A087616 for the unlabeled analog, A003024, A087613, A053763.

a(n) = A053763(n) - A087613(n).

A098148 Number of real (0,1) n X n matrices such that some eigenvalues are strictly complex.

Original entry on oeis.org

0, 0, 52, 22196, 21005094

Offset: 1

Hugo Pfoertner, Sep 07 2004

			The 3 X 3 matrix ((0,1,0),(0,0,1),(1,1,1)) has real eigenvalue 1.83929 and the complex pair -0.41964+-0.60629*i. There are 12 (0,1) 3 X 3 matrices with these eigenvalues. There are 6 groups of 6 matrices having eigenvalues (1.3472,-0.66236+-0.56228*i), (1.46557,-0.23279+-0.79255*i),..., (2.32472,0.33764+-0.56228*i). Two matrices (e.g. ((0,0,1),(1,0,0),(0,1,0)) ) have eigenvalues (1,-0.5+-0.5*sqrt(3)*i). Two matrices (e.g. ((1,1,0),(0,1,1),(1,0,1)) ) have eigenvalues (2,0.5+-0.5*sqrt(3)*i). Total: 12+6*6+2+2=52=a(3).

Index entries for sequences related to binary matrices

Cf. other counts for (0, 1) matrices: A003024 (positive eigenvalues), A055165 (nonsingular), A085656 (positive definite), A086510 (nonnegative eigenvalues).

a[n_] := Module[{M, iter, cnt=0}, M = Table[a[i, j], {i, 1, n}, {j, 1, n}]; iter = Thread[{Flatten[M], 0, 1}]; Do[If[AnyTrue[Eigenvalues[M], Im[#] != 0&], cnt++], Evaluate[Sequence @@ iter]]; cnt];
Do[Print[n, " ", a[n]], {n, 1, 4}] (* Jean-François Alcover, Dec 09 2018 *)

a(5) corrected by Hugo Pfoertner, Sep 26 2017

A188455 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 2^nx)^(2n+1).

Original entry on oeis.org

1, 1, 5, 77, 3191, 332481, 83495679, 49089025473, 66142622730623, 200954040909283841, 1359156203343916471295, 20253823024219712679748609, 659335186924510858208484730879, 46554554840488755704034417937268737

Offset: 0

Paul D. Hanna, Mar 31 2011

nonn

G.f. satisfies a variant of an identity of the Catalan numbers (A000108):
1 = Sum_{n>=0} A000108(n)*x^n/(1 + x)^(2n+1).
Also, g.f. satisfies a variant of an identity involving A003024:
1 = Sum_{n>=0} A003024(n)*x^n/(1 + 2^n*x)^(n+1),
where A003024(n) is the number of acyclic digraphs with n labeled nodes.

			G.f.: 1 = 1/(1+x) + x/(1+2*x)^3 + 5*x^2/(1+4*x)^5 + 77*x^3/(1+8*x)^7 + 3191*x^4/(1+16*x)^9 + 332481*x^5/(1+32*x)^11 +...

Cf. A188456, A188457, A003024.

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(2*k+1)), n)}

A243014 Number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1.

Original entry on oeis.org

1, 1, 3, 13, 61, 321, 1951, 13693, 109593, 986401, 9864091, 108505101, 1302061333, 16926797473, 236975164791, 3554627472061, 56874039553201, 966858672404673, 17403456103284403, 330665665962403981, 6613313319248079981, 138879579704209680001

Offset: 0

Shuaib Ahmed S, May 29 2014

nonn

a(n) is the number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1. For example, with vertex set {A,B,C} the possible ways are: one 3-component graph {A,B,C}, six 2-component graph {{A->B,C},{B->A,C},{A->C,B},{C->A,B},{C->B,A},{B->C,A}}, and six 1-component graph {{A->B->C},{B->A->C},{A->C->B},{C->A->B},{C->B->A},{B->C->A}}.

Alois P. Heinz, Table of n, a(n) for n = 0..449
Eric Weisstein's World of Mathematics, Acyclic Digraph.
Index entries for sequences related to digraphs (or directed graphs)

Cf. A003024, A038154.

@(n)(factorial(n)*sum(1./(factorial(0:n-2)))+1)

a(n) = (n!*Sum(1/k!))+1, k=0..n-2.
a(n) = (n*(a(n-1)+n-2))+1,  for n>1, a(1)=1.
a(n) = A038154(n)+1.
E.g.f.: exp(x)*(x^2-x+1)/(1-x). - Alois P. Heinz, Aug 21 2017

a(0)=1 prepended, one term corrected, more terms added by Alois P. Heinz, Aug 21 2017

A307049 Irregular table read by rows: The number of acyclic digraphs on n labeled nodes with k descents.

Original entry on oeis.org

1, 2, 1, 8, 11, 5, 1, 64, 161, 167, 102, 39, 9, 1, 1024, 3927, 6698, 7185, 5477, 3107, 1329, 423, 96, 14, 1, 32768, 172665, 419364, 656733, 757939, 686425, 504084, 305207, 153333, 63789, 21752, 5959, 1267, 197, 20, 1, 2097152, 14208231, 45263175, 94040848, 145990526, 181444276, 187742937, 165596535

Offset: 1

R. J. Mathar, Mar 21 2019

			     1;
     2    1;
     8   11    5    1;
    64  161  167  102   39    9    1;
  1024 3927 6698 7185 5477 3107 1329 423 96 14 1;
...

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 3

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 3.
K. Archer, C. Graves, Enumerating acyclic digraphs by descents, arXiv:1709.00601 [math.CO], 2017.

Cf. A003024 (row sums), A006125, A057273, A339590, A339807.

A361560 Number of labeled digraphs on [n] all of whose strongly connected components are complete digraphs.

Original entry on oeis.org

1, 1, 4, 47, 1471, 115042, 21591817, 9455689609, 9464951556046, 21316993121024757, 106689322228222150243, 1174731578884501228621956, 28221161668500867009724237123, 1468937207982284446757761131062629, 164682046577167683717133576752582349216, 39562388056404531283767850863430043742371123

Offset: 0

Geoffrey Critzer, Mar 15 2023

nonn

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. A011266 (all strong components are cycles), A361527, A003024 (all strong components are singletons).

nn = 15; B[n_] := n! 2^Binomial[n, 2]; a[x_] := Exp[x] - 1; Table[B[n], {n, 0, nn}] CoefficientList[Series[1/Normal[Series[Exp[-(Exp[x] - 1)], {x, 0, nn}]] /.
    Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}], {z, 0, nn}], z]

A366194 Number of limit dominating binary relations on [n].

Original entry on oeis.org

1, 2, 13, 177, 4486

Offset: 0

Geoffrey Critzer, Oct 03 2023

A relation R is limit dominating iff R converges to a single limit L (A365534) and R contains L.  See Gregory, Kirkland, and Pullman.
A convergent relation R is limit dominating iff the following implication holds for all x,y in [n].  If there is a cyclic traverse from x to y in G(R) then (x,y) is in R, where G(R) is the directed graph with loops associated to R.
A relation R is limit dominating iff it converges to L, the biggest dense relation (A355730) contained in R.  In which case L is the intersection of R^i for all i>=1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominating.
Every transitive relation (A006905) is limit dominating.
Every nilpotent relation (A003024) is limit dominating.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A365534, A121337, A006905, A003024, A366722.

A367052 Number of n X n matrices with elements {0, 1} whose characteristic polynomial has non-leading coefficients in {-1,0}.

Original entry on oeis.org

1, 2, 12, 195, 7971, 754610, 157474968, 70513430631

Offset: 0

Peter Kagey, Nov 03 2023

All of these matrices have the property that for m >= n, A^m = A^{m-i_1} + A^{m-i_2} + ... + A^{m-i_k} for some positive increasing sequence 0 < i_1 < i_2 < ... < i_k <= n.
Because A003024(n) gives the number of such matrices with characteristic polynomial equal to x^n, a(n) >= A003024(n).
Conjecture: The number of matrices with characteristic polynomial x^n - x^(n-1) is exactly n*A003024(n). (If so, (n+1)*A003024(n) is a lower bound for this sequence.)

			For n = 3, there are a(3) = 195 3 X 3 matrices whose non-leading coefficients are in {-1,0}, eight of which are shown below.
  [0 0 1]  [0 0 1]  [0 0 0]  [0 1 0]
  [0 0 0]  [1 0 0]  [1 0 1]  [1 0 1]
  [0 1 0], [0 1 0], [1 1 0], [1 0 0],
.
  [1 0 0]  [1 1 0]  [1 1 0]      [1 1 0]
  [1 0 0]  [0 0 1]  [1 0 0]      [1 0 1]
  [1 1 0], [1 0 0], [1 1 0], and [1 0 0].
These have characteristic polynomials x^3, x^3 - 1, x^3 - x, x^3 - x - 1, x^3 - x^2, x^3 - x^2 - 1, x^3 - x^2 - x, and x^3 - x^2 - x - 1 respectively.
There are 25, 2, 21, 6, 75, 6, 48, and 12 matrices with each of these characteristic polynomials respectively.

Wikipedia, Faddeev-LeVerrier algorithm
Wikipedia, Intrinsic Function

Cf. A003024, A272661, A367051.

IsValid[matrix_, n_] := AllTrue[
  CoefficientList[(-1)^n*CharacteristicPolynomial[matrix, x], x][[;;-2]],
  -1 <= # <= 0 &
]
a[0] := 1
a[n_] := Length[Select[Tuples[{0, 1}, {n, n}], IsValid[#, n] &]]

from itertools import product
from sympy import Matrix
def A367052(n): return sum(1 for p in product((0,1),repeat=n**2) if all(d==0 or d==-1 for d in Matrix(n,n,p).charpoly().as_list()[1:])) if n else 1 # Chai Wah Wu, Nov 05 2023

a(5)-a(6), using the Faddeev-LeVerrier algorithm, from Martin Ehrenstein, Nov 06 2023

a(7), using AVX2 Intrinsics, from Martin Ehrenstein, Nov 18 2023

cp's OEIS Frontend

A365593 Number of n X n Boolean relation matrices such that every block of its Frobenius normal form is either a 0 block or a 1 block.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A087613 Number of labeled acyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author

Keywords

Links

Crossrefs

A087615 Number of labeled cyclic preferences/voting outcomes, indifference and undecidedness/incompleteness permitted (Social Choice Theory).

Views

Author

Keywords

Links

Crossrefs

Formula

A098148 Number of real (0,1) n X n matrices such that some eigenvalues are strictly complex.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A188455 G.f.: 1 = Sum_{n>=0} a(n)*x^n/(1 + 2^n*x)^(2n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A243014 Number of acyclic digraphs (DAGS) on n labeled nodes, where the indegree and outdegree of each node is at most 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A307049 Irregular table read by rows: The number of acyclic digraphs on n labeled nodes with k descents.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A361560 Number of labeled digraphs on [n] all of whose strongly connected components are complete digraphs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A366194 Number of limit dominating binary relations on [n].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A367052 Number of n X n matrices with elements {0, 1} whose characteristic polynomial has non-leading coefficients in {-1,0}.

Views

A188455 G.f.: 1 = Sum_{n>=0} a(n)x^n/(1 + 2^nx)^(2n+1).