A001035 -id:A001035 - cp's OEIS frontend

A354847 Number of binary relations on [n] that are idempotent and reduced.

1, 2, 6, 32, 318, 5552, 159126, 7137272, 484656318, 48628712192, 7076367228486, 1471524821492552, 432066672598422318, 177354805872559516112, 100928502119652298356726, 79062670900333522721886872, 84733519638342583432646258718, 123582326772837258238596562116512, 244150974458417420635453430918487846

Offset: 0

Geoffrey Critzer, Jun 08 2022

nonn

The Boolean matrix representing a binary relation on [n] is row (column) reduced if no nonzero row (column) is the sum of other rows (columns). It is reduced if it is both row reduced and column reduced.

a(n) is the number of partial order relations on Y, where Y is some subset of [n].

R. J. Plemmons and M. T. West, On the semigroup of binary relations, Pacific Journal of Mathematics, vol 35, No. 3, 1970. Theorem 2.4

Cf. A001035, A121337.

nn = 18; A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt",
    "Table"], {, }][[All, 2]];A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, nn}];
Range[0, nn]! CoefficientList[Series[A[x] Exp[x], {x, 0, nn}], x]

E.g.f.: A(x)*exp(x) where A(x) is the e.g.f. for A001035.

a(n) = Sum_{k=0..n} binomial(n,k)*A001035(n-k).

A008285 Erroneous version of A342587.

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 108, 24, 1, 840, 2310, 960, 120, 1, 11642, 65700, 42960, 9000, 720, 1, 227892, 2583126, 2510760, 712320, 90720, 5040, 1, 6285806, 142259628, 199424904, 71243760, 11481120, 987840, 40320

Offset: 1

N. J. A. Sloane

dead

			Triangle T(n,k) (with n >= 1 and 1 <= k <= n) begins as follows:
  1;
  1,      2;
  1,     12,       6;
  1,     86,     108,      24;
  1,    840,    2310,     960,    120;
  1,  11642,   65700,   42960,   9000,   720;
  1, 227892, 2583126, 2510760, 712320, 90720, 5040;
  ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.

Cf. A000142 (diagonal), A001035 (row sums), A055531 (k=2), A055532 (k=3), A055533 (subdiagonal), A081064, A342501 (connected).

A101620 Decimal encoding of digraph topologies.

Original entry on oeis.org

1, 3, 9, 11, 13, 15, 129, 131, 133, 137, 139, 141, 143, 145, 153, 161, 163, 165, 171, 175, 177, 179, 187, 193, 195, 197, 205, 207, 209, 213, 221, 241, 243, 245, 255

Offset: 1

Alford Arnold, Dec 10 2004

The sequence encodes labeled digraph topologies as described by and counted in A000798.

			Let a = 2, b = 4, c = 16, d = 256, ...
a(19) = 171 because we can map { }, a, ab, ac, abc to 1 + 2 + 8 + 32 + 128
Viewed as an array the table begins
1
3
9 11 13 15
129 131 133 137 139 141 143 145 153 161 163 165 171 175 177 ...
with respectively 1 1 4 29 355 ... (A000798) entries on each row.

Cf. A000798, A001035, A001930, A074486.

A173399 Partial sums of A000798.

Original entry on oeis.org

1, 2, 6, 35, 390, 7332, 216859, 9752100, 652531454, 63912820877, 9040966693920, 1825887005430112, 521181458071204133, 208402575114740157174, 115825454552169007964634, 88852094573138413500449755, 93499965506283177978710943850, 134231450058844163850300579669696, 261626767193693218968916427480786899

Offset: 0

Jonathan Vos Post, Feb 17 2010

nonn

Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.

The subsequence of primes in this partial sum begins: 2, 216859.

Cf. A000798, A001035 (labeled posets), A001930 (unlabeled topologies), A000112 (unlabeled posets), A006057.

Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {, }][[All, 2]] // Accumulate (* Jean-François Alcover, Dec 30 2019 *)

a(n) = Sum_{i=0..n} A000798(i).

Missing term 7332 added and extended by Jean-François Alcover, Dec 30 2019

A173488 Partial sums of A055512.

Original entry on oeis.org

1, 2, 4, 10, 46, 426, 6816, 164778, 5561666, 248740730, 14187451940, 1002045820690, 85615117761142, 8682866612715706, 1029036311254555560, 140656568448867136650, 21929110364021381812410, 3862525357012048643891882, 762298016068721625860646524

Offset: 0

Jonathan Vos Post, Feb 19 2010

Partial sums of the number of lattices with n labeled elements. After a(0) = 1, always even, hence the only prime in the partial sum is 2. The subsequence of semiprimes begins 4, 10, 46.

Cf. A055512, A006966, A001035, Main diagonal of A058159.

Cases[Import["https://oeis.org/A055512/b055512.txt", "Table"], {, }][[All, 2]] // Accumulate (* Jean-François Alcover, Jan 02 2020 *)

a(n) = Sum_{i=0..n} A055512(i).

a(17)-a(18) from Jean-François Alcover, Jan 02 2020

A266875 Number of partially ordered sets ("posets") with n labeled elements, modulo n.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 4, 3, 1, 9, 1

Offset: 1

Altug Alkan, Jan 05 2016

If n is a prime number, a(n) = 1 because of the fact that A001035(p^k) == 1 mod p for all primes p.

If n is an even number, a(n) is a number of the form 3^k for n <= 19. How is the distribution of terms of the form 3^k in this sequence?

			a(4) = A001035(4) mod 4 = 219 mod 4 = 3.
a(5) = A001035(5) mod 5 = 4231 mod 5 = 1.
a(6) = A001035(6) mod 6 = 130023 mod 6 = 3.
a(7) = A001035(7) mod 7 = 6129859 mod 7 = 1.

Cf. A001035, A265847.

a(n) = A001035(n) mod n, for n > 0.

a(A000040(n)) = A265847(A000040(n)) - 1, for n > 1.

A284276 Number of event structures with n labeled elements.

Original entry on oeis.org

1, 4, 41, 916, 41099, 3528258, 561658287

Offset: 1

Marco B. Caminati, Mar 24 2017

Little is known about event structures enumeration. The entries were obtained by a dedicated algorithm recursively constructing all possible event structures. This algorithm has been formally verified to be correct by construction using the theorem prover Isabelle/HOL (see the Links section). The formal proof also formally certifies the correctness of other sequences already in the OEIS (quasi-orders, partial orders). Note that we count what are called "event structures" in the given References. Other sources, however, refer to the same objects as "prime event structures".

			An event structure is given by a poset and a conflict relation (denoted #) on it. The conflict relation is irreflexive and symmetric, and must propagate over the order: a<=b and a#c imply b#c.
For n=2, (i.e., two elements a and b), there are three possible posets: a<=b, b<=a, and neither of the two. For the first two cases, only the empty conflict is possible. For the third case, you can have either the empty conflict relation, or a#b. Hence the total number of event structures is 4.

Juliana Bowles and Marco B. Caminati, A Verified Algorithm Enumerating Event Structures, arXiv:1705.07228 [cs.LO], 2017.
Marco B. Caminati, Isabelle/HOL code
Marco B. Caminati and Juliana K. F. Bowles, Representation Theorems Obtained by Mining across Web Sources for Hints, Lancaster Univ. (UK, 2022).
M. Nielsen, G. Plotkin, and G. Winskel, Petri nets, event structures and domains, part I, Theoretical Computer Science 13, no. 1 (1981): 85-108.
G. Winskel and M. Nielsen, Models for concurrency, DAIMI Report Series 21, no. 429 (1992) (revised version).

Cf. A001035 (generating all the event structures entails generating all the posets), A000798 (to generate all the posets we preemptively generated all the quasi-orders).

a(7) from Marco B. Caminati, Aug 01 2017

A284762 Total number of subsets of X that are open and closed and connected summed over all distinct topological spaces X that can be placed on an n-set.

Original entry on oeis.org

1, 2, 9, 69, 852, 16363, 479435, 21150888, 1388124543, 133822887673, 18707633394606, 3745998552621317, 1062675319801676431, 423005074717335908762, 234301896939296139079453, 179277553685814268284430793, 188286118651948743843774496644, 269901723843412313246289232355847, 525443899393186663528068248469425039

Offset: 0

Geoffrey Critzer, Apr 02 2017

nonn

			a(2) = 9.  Let X = {a,b}.  There are four distinct topologies (A000798) that can be placed on X: {{},X}  {{},{a},X}  {{}, {b},X}  {{},{a},{b},X}.  These topologies have 2 + 2 + 2 + 3 sets respectively that are open and closed and connected.

Cf. A281547.

E.g.f.: (log(A(exp(x)-1))+1)*A(exp(x)-1) where A(x) is the e.g.f. for A001035.

A340318 Minimum size of a partial order that contains all partial orders of size n.

Original entry on oeis.org

0, 1, 3, 5, 8, 11, 16

Offset: 0

Caleb Stanford, Jan 04 2021

a(n) is the minimum number of elements in a poset P such that every poset of size n is isomorphic to a subset of P, where the subset inherits the order from P.
Elementary bounds are a(n) >= 2n-1 because it must contain a chain and an antichain, and a(n) <= 2^n-1 because every partial order embeds into the powerset partial order on n elements. It is shown in the MathOverflow link that a(n) has no polynomial upper bound. This is in particular derived from binomial(a(n),n) >= A000112(n).
a(4) = 8 verified using a computer-assisted proof with a SAT solver.
a(5) = 11 proven on MathOverflow.
a(6) = 16 and 16 <= a(7) <= 25 proven on MathOverflow. - Jukka Kohonen, Jan 15 2021

			a(2) = 3 because there are 2 nonisomorphic posets on two elements, and both embed into the poset of three elements {a, b, c} with ordering a < b (and other pairs are incomparable).
a(3) = 5 because all posets on three elements can be embedded into {a, b, c, d, e} with ordering a < d, b < c < d, and b < e.

Joel David Hamkins and Fedor Petrov, What is the minimal size of a partial order that is universal for all partial orders of size n?, MathOverflow.
Jukka Kohonen, What is the minimum size of a partial order containing all partial orders of size 5? (proofs of a(5)=11, a(6)=16 and 16 <= a(7) <= 25), MathOverflow.
Caleb Stanford, Alloy program to verify a(n) for small n, GitHub.

Cf. A000112, A001035, A004401, A097911.

# Find an u-poset that contains all n-posets as induced posets.
def find_universal_poset(n,u):
    PP = list(Posets(n))
    for U in Posets(u):
        ok = True
        for P in PP:
            if not U.has_isomorphic_subposet(P):
                ok = False
                break
        if ok:
            return U
    return None

a(6) from Jukka Kohonen, Jan 15 2021

A355783 Triangular array read by rows. T(n,k) is the number of labeled transitive relations on [n] that have exactly k symmetric points.

Original entry on oeis.org

1, 2, 0, 12, 0, 1, 152, 0, 18, 1, 3504, 0, 456, 24, 10, 135392, 0, 17520, 760, 600, 31, 8321472, 0, 1015440, 35040, 40560, 2316, 361, 784621952, 0, 87375456, 2369360, 3615360, 185556, 52682, 2164, 110521185024, 0, 10984707328, 233001216, 441616000, 19052992, 7723408, 384992, 32663

Offset: 0

Geoffrey Critzer, Jul 16 2022

Let R be a binary relation on [n]. Then x in [n] is a symmetric point of R if there is a y in [n] with x != y and both (x,y),(y,x) in R.

			       1,
       2, 0,
      12, 0,     1,
     152, 0,    18,   1,
    3504, 0,   456,  24,  10,
  135392, 0, 17520, 760, 600, 31

Cf. A280202 (main diagonal), A085628 (column k=0), A006905 (row sums).

nn = 18; A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt",
    "Table"], {, }][[All, 2]]; A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, nn}];
Table[Take[(Range[0, nn]! CoefficientList[Series[A[Exp[y x] - 1 - y x + x + x], {x, 0, nn}], {x,y}])[[i]], i], {i, 1, nn}] // Grid

E.g.f.: A(exp(y*x) - 1 - y*x + 2*x) where A(x) is the e.g.f. for A001035.

cp's OEIS Frontend

A354847 Number of binary relations on [n] that are idempotent and reduced.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A008285 Erroneous version of A342587.

Views

Author

Keywords

Examples

Links

Crossrefs

A101620 Decimal encoding of digraph topologies.

Views

Author

Keywords

Comments

Examples

Crossrefs

A173399 Partial sums of A000798.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A173488 Partial sums of A055512.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A266875 Number of partially ordered sets ("posets") with n labeled elements, modulo n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A284276 Number of event structures with n labeled elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A284762 Total number of subsets of X that are open and closed and connected summed over all distinct topological spaces X that can be placed on an n-set.

Views

Author

Keywords

Examples

Crossrefs

Formula

A340318 Minimum size of a partial order that contains all partial orders of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Extensions