A003024 -id:A003024 - cp's OEIS frontend

A082403 E.g.f.: 1-1/B(x) where B(x) is e.g.f. for A003024.

0, 1, 1, 13, 373, 24061, 3430021, 1085594413, 765444156373, 1199327541421981, 4150826776751106181, 31511604323119334675053, 521181162682913685911315413, 18663030289006900328937074926621

Offset: 0

Vladeta Jovovic, Apr 15 2003

nonn

R. W. Robinson, Counting labeled acyclic digraphs, p. 264 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973

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

Cf. A003024.

m = 20; b[0] = b[1] = 1;
b[n_] := b[n] = Sum[-(-1)^k Binomial[n, k] 2^(k (n-k)) b[n-k], {k, 1, n}];
B[x_] = Sum[b[n] x^n/n!, {n, 0, m}];
CoefficientList[1 - 1/B[x] + O[x]^(m+1), x] Range[0, m]! (* Jean-François Alcover, Jan 24 2020 *)

\\ here G(n) gives A003024 as e.g.f.
G(n)={my(v=vector(n+1)); v[1]=1; for(n=1, n, v[n+1]=sum(k=1, n, -(-1)^k*2^(k*(n-k))*v[n-k+1]/k!))/n!; Ser(v)}
{ concat([0], Vec(serlaplace(1-1/G(15)))) } \\ Andrew Howroyd, Sep 10 2018

A188490 Exponential transform of A003024, number of acyclic digraphs with n labeled nodes.

Original entry on oeis.org

1, 1, 2, 10, 146, 6010, 636428, 163326124, 98126803670, 134925234752998, 417644922244986812, 2873459543869519132876, 43497844823465975411261876, 1436705096446765490152625035300, 102817732537500055044863771641124696

Offset: 0

Paul D. Hanna, Apr 01 2011

nonn

			G.f.: A(x) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 +...
log(A(x)) = x + 3*x^2/2 + 25*x^3/3 + 543*x^4/4 + 29281*x^5/5 + 3781503*x^6/6 +...+ A003024(n)*x^n/n +...

Cf. A003024 (log).

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

G.f.: A(x) = exp( Sum_{n>=1} A003024(n)*x^n/n ) where A003024(n) is the number of acyclic digraphs with n labeled nodes.

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

Original entry on oeis.org

1, 2, 6, 38, 666, 32282, 3965886, 1165884638, 792920124786, 1220537093266802, 4187268805038970806, 31649452354183112810198, 522319168680465054600480906, 18683388426164284818805590810122, 1439689660962836496648920949576152046, 237746858936806624825195458794266076911118

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

			The set-system Y = {{1},{1,2},{2,3}} has choices (1,1,2), (1,1,3), (1,2,2), (1,2,3), of which only (1,2,3) has all different elements, so Y is counted under a(3).
The a(0) = 1 through a(2) = 6 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

Christian Sievers, Table of n, a(n) for n = 0..77

The maximal case (n subsets) is A003024.
The version for at least one choice is A367902.
The version for no choices is A367903, no singletons A367769, ranks A367907.
These set-systems have ranks A367908, nonzero A367906.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A102896, A133686, A283877, A306445, A355741, A367770, A367862, A367869, A367901, A367905.

Table[Length[Select[Subsets[Subsets[Range[n]]], Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,3}]

a(n) = A367902(n) - A367772(n). - Christian Sievers, Jul 26 2024

Binomial transform of A003024. - Christian Sievers, Aug 12 2024

a(5)-a(8) from Christian Sievers, Jul 26 2024

More terms from Christian Sievers, Aug 12 2024

A003087 Number of acyclic digraphs with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, 1165948612902, 797561675349580, 1094026876269892596, 3005847365735456265830, 16530851611091131512031070, 181908117707763484218885361402

Offset: 0

N. J. A. Sloane

Also the number of equivalence classes of n X n real (0,1)-matrices with all eigenvalues positive, up to conjugation by permutations.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 194.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..18 were computed by R. W. Robinson; terms 19..36 by Sean A. Irvine, Jan 22 2014)
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - _N. J. A. Sloane_, Sep 14 2012
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], 2003.
Lawrence Ong, Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers, arXiv preprint arXiv:1606.05982 [cs.IT], 2016.
R. W. Robinson, Counting unlabeled acyclic digraphs, in Little C.H.C. (Ed.), "Combinatorial Mathematics V (Melbourne 1976)", Lect. Notes Math. 622 (1976), pp. 28-43. DOI:10.1007/BFb0069178.
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
Eric Weisstein's World of Mathematics, Acyclic Digraph.
Index entries for sequences related to binary matrices

Cf. A003024 (the labeled case), A082402, A101228 (weakly connected, inverse Euler Trans).

Rows sums of A122078, A350447, A350448.

A055165 Number of invertible n X n matrices with entries equal to 0 or 1.

Original entry on oeis.org

1, 1, 6, 174, 22560, 12514320, 28836612000, 270345669985440, 10160459763342013440

Offset: 0

Ulrich Hermisson (uhermiss(AT)server1.rz.uni-leipzig.de), Jun 18 2000

All eigenvalues are nonzero.

			For n=2 the 6 matrices are {{{0, 1}, {1, 0}}, {{0, 1}, {1, 1}}, {{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}, {{1, 1}, {1, 0}}}.

Eric Weisstein's World of Mathematics, Nonsingular Matrix.
Chai Wah Wu, Can machine learning identify interesting mathematics? An exploration using empirically observed laws, arXiv:1805.07431 [cs.LG], 2018.
Miodrag Zivkovic, Classification of small (0,1) matrices, arXiv:math/0511636 [math.CO], 2005; Linear Algebra and its Applications, 414 (2006), 310-346.
Miodrag Zivkovic, Classification of (0,1) matrices of order not exceeding 8.
Index entries for sequences related to binary matrices

Cf. A056990, A056989, A046747, A055165, A002416, A003024 (positive definite matrices).
A046747(n) + a(n) = 2^(n^2) = total number of n X n (0, 1) matrices = sequence A002416.
Main diagonal of A064230.

a(n)=sum(t=0,2^n^2-1,!!matdet(matrix(n,n,i,j,(t>>(i*n+j-n-1))%2))) \\ Charles R Greathouse IV, Feb 09 2016

from itertools import product
from sympy import Matrix
def A055165(n): return sum(1 for s in product([0,1],repeat=n**2) if Matrix(n,n,s).det() != 0) # Chai Wah Wu, Sep 24 2021

For an asymptotic estimate see A046747. A002884 is a lower bound. A002416 is an upper bound.

a(n) = n! * A088389(n). - Gerald McGarvey, Oct 20 2007

More terms from Miodrag Zivkovic (ezivkovm(AT)matf.bg.ac.rs), Feb 28 2006
Description improved by Jeffrey Shallit, Feb 17 2016
a(0)=1 prepended by Alois P. Heinz, Jun 18 2022

A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 2, 1, 6, 12, 6, 1, 12, 60, 152, 186, 108, 24, 1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120, 1, 30, 420, 3600, 20790, 83952, 240480, 496680, 750810, 838130, 691020, 416160, 178230, 51480, 9000, 720, 1, 42, 840, 10570, 93030, 601944

Offset: 0

Vladeta Jovovic, Apr 15 2003

			Array T(n,k) (with n >= 0 and 0 <= k <= n*(n-1)/2) begins as follows:
  1;
  1;
  1,  2;
  1,  6,  12,   6;
  1, 12,  60, 152,  186,  108,   24;
  1, 20, 180, 940, 3050, 6180, 7960, 6540, 3330, 960, 120;
  ...
From _Petros Hadjicostas_, Apr 10 2020: (Start)
For n=2 and k=2, we have T(2,2) = 2 labeled directed acyclic graphs with 2 nodes and 2 arcs: [A (double ->) B] and [B (double ->) A].
For n=3 and k=4, we have T(3,4) = 6 labeled directed acyclic graphs with 3 nodes and 4 arcs: [X (double ->) Y (single ->) Z (single <-) X] with (X,Y,Z) a permutation of {A,B,C}. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)
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.
V. I. Rodionov, On the number of labeled acyclic digraphs, Discr. Math. 105 (1-3) (1992), 319-321.

Cf. A003024 (row sums), A055533 (subdiagonal).

Columns: A147796 (k = 3), A147817 (k = 4), A147821 (k = 5), A147860 (k = 6), A147872 (k = 7), A147881 (k = 8), A147883 (k = 9), A147964 (k = 10).

A081064gf := proc(n,x)
    local m,a ;
    option remember;
    if n = 0 then
        1;
    else
        a := 0 ;
        for m from 1 to n do
            a := a+(-1)^(m-1)*binomial(n,m)*(1+x)^(m*(n-m)) *procname(n-m,x) ;
        end do:
        expand(a) ;
    end if;
end proc:
A081064 := proc(n,k)
    coeff(A081064gf(n,x),x,k) ;
end proc:
for n from 0 to 8 do
    for k from 0 do
        tnk := A081064(n,k) ;
        if tnk =0 then
            break;
        end if;
        printf("%d ",tnk) ;
    end do:
    printf("\n") ;
end do: # R. J. Mathar, Mar 21 2019

nn = 6; a[n_] := a[n] = Sum[(-1)^(k + 1) Binomial[n, k] (1 + x)^(k (n - k)) a[   n - k], {k, 1, n}]; a[0] = 1; Table[CoefficientList[a[n], x], {n, 0, nn}] // Grid (* Geoffrey Critzer, Mar 11 2023 *)

B(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, (1+'y)^(i*(#u-j))*((1+'y)^i-1)^j * binomial(n,i) * u[j])))); v}
T(n)={my(v=B(n)); vector(#v+1, n, if(n==1, [1], Vecrev(vecsum(v[n-1]))))}
{ my(A=T(5)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Dec 27 2021

1 = 1*exp(-x) + 1*exp(-(1+y)*x)*x/1! + (2*y+1)*exp(-(1+y)^2*x)*x^2/2! + (6*y^3 + 12*y^2 + 6*y + 1)*exp(-(1+y)^3*x)*x^3/3! + (24*y^6 + 108*y^5 + 186*y^4 + 152*y^3 + 60*y^2 + 12*y + 1)*exp(-(1+y)^4*x)*x^4/4! + (120*y^10 + 960*y^9 + 3330*y^8 + 6540*y^7 + 7960*y^6 + 6180*y^5 + 3050*y^4 + 940*y^3 + 180*y^2 + 20*y + 1)*exp(-(1+y)^5*x)*x^5/5! + ... - Vladeta Jovovic, Jun 07 2005
We explain Vladeta Jovovic's functional equation above. If F_n(y) = Sum_{k = 0..n*(n-1)/2) T(n,k) * y^k for n >= 0, then Sum_{n >= 0} F_n(y) * exp(-(1 + y)^n * x) * x^n/n! = 1. - Petros Hadjicostas, Apr 11 2020
From Petros Hadjicostas, Apr 10 2020: (Start)
If A_n(x) = Sum_{k >= 0} T(n,k)*x^k (with T(n,k) = 0 for k > n*(n-1)/2)), then Sum_{m=1..n} (-1)^(m-1) * binomial(n,m) * (1 + x)^(m*(n-m)) * A_m(x) = 1.
T(n,0) = 1, T(n,1) = n*(n-1), T(n,2) = 12*binomial(n+1,4), and T(n,3) = binomial(n,3)*(n^3 - 5*n - 6).
Also, T(n, n*(n-1)/2 - 1) = A055533(n) = n!*(n-1)^2/2 for n > 1. (End)

T(0,0) = 1 prepended by Petros Hadjicostas, Apr 11 2020

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Original entry on oeis.org

1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421

Offset: 1

N. J. A. Sloane

nonn

From Gus Wiseman, Jan 02 2024: (Start)
Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:
  .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
            {{2},{1,2}}  {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{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}}
These set-systems are all connected.
The case of labeled graphs is A000169.
(End)

			a(2) = 2: o-->--o (2 ways)
a(3) = 15: o-->--o-->--o (6 ways) and
o ... o o-->--o
.\ . / . \ . /
. v v ... v v
.. o ..... o
(3 ways) (6 ways)

R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

A diagonal of A058876.
Row sums of A350487.
The unlabeled version is A350415.
Column k=1 of A361718.
Cf. A003026, A003028, A345258.
For any number of sinks we have A003024, unlabeled A003087.
For n-1 sinks we have A058877.
For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman, Jan 02 2024 *)

\\ requires A058876.
my(T=A058876(20)); vector(#T, n, T[n][1]) \\ Andrew Howroyd, Dec 27 2021

\\ see Marcel et al. link (formula for a').
seq(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * (2^(n-k)-1)^k * a[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(n) = (-1)^(n-1) * n * A134531(n). - Gus Wiseman, Jan 02 2024

More terms from Vladeta Jovovic, Apr 10 2001

A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 164, 18625, 5491851, 4649088885, 12219849683346

Offset: 0

Gus Wiseman, Jan 01 2024

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367903, ranks A367907, no singletons A367769.
The complement is A368601, any length A367902 (see also A367770, A367906).
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367868, A367901, A368094, A368097.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]==0&]],{n,0,3}]

from itertools import combinations, product, chain
from scipy.special import comb
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(int(comb(2**n-1,n) - a(n))) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) = A136556(n) - A368601(n).

a(6) from Robert P. P. McKone, Jan 02 2024

a(7)-a(8) from Christian Sievers, Jul 25 2024

A368601 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.

Original entry on oeis.org

1, 1, 3, 32, 1201, 151286, 62453670, 84707326890, 384641855115279

Offset: 0

Gus Wiseman, Jan 01 2024

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(2) = 3 set-systems:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
Non-isomorphic representatives of the a(3) = 32 set-systems:
  {{1},{2},{3}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367902, ranks A367906, no singletons A367770.
The complement is A368600, any length A367903 (see also A367907, A367769).
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367901, A367905, A368094, A368097.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]>0&]],{n,0,3}]

from itertools import combinations, product, chain
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in
range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(a(n)) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) + A368600(n) = A136556(n).

a(6) from Robert P. P. McKone, Jan 02 2024

a(7)-a(8) from Christian Sievers, Jul 25 2024

A121337 Number of idempotent relations on n labeled elements.

Original entry on oeis.org

1, 2, 11, 123, 2360, 73023, 3465357

Offset: 0

Florian Kammüller (flokam(AT)cs.tu-berlin.de), Aug 28 2006

A relation r is idempotent if r ; r = r, where ; denotes sequential composition.
From Geoffrey Critzer, Oct 18 2023 : (Start)
a(n) is also the number of maximal subgroups in the semigroup of binary relations on [n].  See Butler and Markowski link.
A binary relation is idempotent iff it is both dense (A355730) and transitive (A006905).
A binary relation is idempotent iff it is both limit dominating (A366194) and limit dominated (A366722).  See Gregory, Kirkland, and Pullman link.
A binary relation R on [n] is idempotent iff the following biconditional statement holds for all x,y in [n]:  There is a cyclic traverse from x to y in G(R) iff (x,y) is in R.  Here, G(R) is the directed graph with self loops allowed (A002416) corresponding to R.  See Rosenblatt link.
Let Q be a quasi-order (A000798) on [n].  Let D(X) be the relation {(x,x):x is in X}.  Let S be a subset of [n] such that: (i) For all x in S, the class in the equivalence relation Q intersect Q^(-1) containing (x,x) is a singleton and (ii) for all x,y in S, the component containing x is not covered by the component containing y in the condensation of G(Q) .  Here, the condensation of G(Q) is the acyclic digraph (A003024) obtained from G(Q) by replacing every strongly connected component (SCC) by a single vertex and all directed edges from one SCC to another with a single directed edge.  Then a relation is idempotent iff it is of the form Q-D(S).  See Schein link.  (End)

			a(2) = 11 because given a set {a,b} of two elements, of the 2^(2*2) = 16 relations on the set, only 5 are not idempotent. - _Michael Somos_, Jul 28 2013
These 5 relations that are not idempotent are: {(a,b)}, {(b,a)}, {(a,b),(b,a)}, {(a,b),(b,a),(b,b)}, {(a,a),(a,b),(b,a)}. - _Geoffrey Critzer_, Aug 07 2016

F. Kammüller, Interactive Theorem Proving in Software Engineering, Habilitationsschrift, Technische Universitaet Berlin (2006).
Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Decker, 1982.

G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
K. K.-H. Butler and G. Markowsky, The Number of Maximal Subgroups of the Semigroup of Binary Relations, Kyungpook Math. J. Vol 12, June 1972.
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.
F. Kammüller, Counting idempotent relations.
F. Kammüller and J. W. Sanders, Idempotent relations in Isabelle/HOL, International Colloquium on Theoretical Aspects of Computing, ICTAC'04. Volume 3407 of Lecture Notes in Computer Science, Springer-Verlag (2005).
G. Pfeiffer, Counting transitive relations, J. Integer Sequences, Volume 7, 2004, #3.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.

Cf. A000798 (labeled quasi-orders (or topologies)), A001930 (unlabeled quasi-orders), A001035 (labeled partial orders), A000112 (unlabeled partial orders), A002416, A003024, A366722, A366194, A355730, A006905.

Row sums of A360984.

Prepend[Table[Length[Select[Tuples[Tuples[{0, 1}, n], n], (MatrixPower[#, 2] /. x_ /; x > 0 -> 1) == # &]], {n, 1, 4}], 1] (* Geoffrey Critzer, Aug 07 2016 *)

Offset corrected by James Mitchell, Jul 28 2013

a(1) corrected by Philippe Beaudoin, Aug 11 2015

cp's OEIS Frontend

A082403 E.g.f.: 1-1/B(x) where B(x) is e.g.f. for A003024.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

A188490 Exponential transform of A003024, number of acyclic digraphs with n labeled nodes.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A003087 Number of acyclic digraphs with n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A055165 Number of invertible n X n matrices with entries equal to 0 or 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A081064 Irregular array, read by rows: T(n,k) is the number of labeled acyclic digraphs with n nodes and k arcs (n >= 0, 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions