A121337 -id:A121337 - cp's OEIS frontend

A001035 Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).

1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023

Offset: 0

N. J. A. Sloane

From Altug Alkan, Dec 22 2015: (Start)
a(p^k) == 1 (mod p) and a(n + p) == a(n + 1) (mod p) for all primes p.
a(0+19) == a(0+1) (mod 19) or a(19^1) == 1 (mod 19), that is, a(19) mod 19 = 1.
a(2+17) == a(2+1) (mod 17). So a(19) == 19 (mod 17), that is, a(19) mod 17 = 2.
a(6+13) == a(6+1) (mod 13). So a(19) == 6129859 (mod 13), that is, a(19) mod 13 = 8.
a(8+11) == a(8+1) (mod 11). So a(19) == 44511042511 (mod 11), that is, a(19) mod 11 = 1.
a(12+7) == a(12+1) (mod 7). So a(19) == 171850728381587059351 (mod 7), that is, a(19) mod 7 = 1.
a(14+5) == a(14+1) (mod 5). So a(19) == 77567171020440688353049939 (mod 5), that is, a(19) mod 5 = 4.
a(16+3) == a(16+1) (mod 3). So a(19) == 122152541250295322862941281269151 (mod 3), that is, a(19) mod 3 = 1.
a(17+2) == a(17+1) (mod 2). So a(19) mod 2 = 1.
In conclusion, a(19) is a number of the form 2*3*5*7*11*13*17*19*n - 1615151, that is, 9699690*n - 1615151.
Additionally, for n > 0, note that the last digit of a(n) has the simple periodic pattern: 1,3,9,9,1,3,9,9,1,3,9,9,...
(End)
Number of rank n sublattices of the Boolean algebra B_n. - Kevin Long, Nov 20 2018
a(n) is the number of n X n idempotent Boolean relation matrices (A121337) that have rank n. - Geoffrey Critzer, Aug 16 2023
a(19) == 163279579 (mod 232792560). - Didier Garcia, Feb 06 2025

			R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 shows the unlabeled posets with <= 4 points.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of T_0 topologies with n points. For example, the a(0) = 1 through a(3) = 19 topologies are:
  {}  {}{1}  {}{1}{12}     {}{1}{12}{123}
             {}{2}{12}     {}{1}{13}{123}
             {}{1}{2}{12}  {}{2}{12}{123}
                           {}{2}{23}{123}
                           {}{3}{13}{123}
                           {}{3}{23}{123}
                           {}{1}{2}{12}{123}
                           {}{1}{3}{13}{123}
                           {}{2}{3}{23}{123}
                           {}{1}{12}{13}{123}
                           {}{2}{12}{23}{123}
                           {}{3}{13}{23}{123}
                           {}{1}{2}{12}{13}{123}
                           {}{1}{2}{12}{23}{123}
                           {}{1}{3}{12}{13}{123}
                           {}{1}{3}{13}{23}{123}
                           {}{2}{3}{12}{23}{123}
                           {}{2}{3}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}{123}
(End)

G. Birkhoff, Lattice Theory, Amer. Math. Soc., 1961, p. 4.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 427.
K. K.-H. Butler, A Moore-Penrose inverse for Boolean relation matrices, pp. 18-28 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
K. K. H. Butler and G. Markowsky. "The number of partially ordered sets. I." Journal of Korean Mathematical Society 11.1 (1974).
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 60, 229.
M. Erné, Struktur- und Anzahlformeln für Topologien auf endlichen Mengen, PhD dissertation, Westfälische Wilhelms-Universität zu Münster, 1972.
M. Erné and K. Stege, The number of labeled orders on fifteen elements, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. 2, Problem 5.39, p. 88.

Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.
Juliana Bowles and Marco B. Caminati, A Verified Algorithm Enumerating Event Structures, arXiv:1705.07228 [cs.LO], 2017.
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
J. I. Brown and S. Watson, The number of complements of a topology on n points is at least 2^n (except for some special cases), Discr. Math., 154 (1996), 27-39.
K. K.-H. Butler, The number of partially ordered sets, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
K. K.-H. Butler and G. Markowsky, The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966. [Annotated scanned copy]
Narendrakumar R. Dasre and Pritam Gujarathi, Approximating the Bounds for Number of Partially Ordered Sets with n Labeled Elements, Computing in Engineering and Technology, Advances in Intelligent Systems and Computing, Vol. 1025, Springer (Singapore 2019), 349-356.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.
J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.
J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]
S. R. Finch, Transitive relations, topologies and partial orders.
S. R. Finch, Transitive relations, topologies and partialorders, June 5, 2003. [Cached copy, with permission of the author]
Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
Didier Garcia, Proof of a(19) formula [in French].
Didier Garcia, Two conjectures concerning a(n) [in French].
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments.
J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.
Richard Kenyon, Maxim Kontsevich, Oleg Ogievetsky, Cosmin Pohoata, Will Sawin, and Senya Shlosman, The miracle of integer eigenvalues, arXiv:2401.05291 [math.CO], 2024. See p. 4.
Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012. - From _N. J. A. Sloane_, Nov 09 2012
M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359 [math.NT], 2015.
D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.
Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers.
Sami Lazaar, Houssem Sabri, and Randa Tahri, Structural and Numerical Studies of Some Topological Properties for Alexandroff Spaces, Bull. Iran. Math. Soc. (2021).
N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Bob Proctor, Chapel Hill Poset Atlas.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Ivo Rosenberg, The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7.
Ivo Rosenberg and N. J. A. Sloane, Correspondence, 1971.
D. Rusin, Further information and references. [Broken link]
D. Rusin, Further information and references. [Cached copy]
A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.
N. J. A. Sloane, List of sequences related to partial orders, circa 1972.
N. J. A. Sloane, List of sequences related to partial orders, circa 1972.
N. J. A. Sloane, Classic Sequences.
Gus Wiseman, Hasse diagrams of the a(4) = 219 posets.
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970. [Annotated scanned copy]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences.
Index entries for sequences related to posets

Cf. A000798 (labeled topologies), A001930 (unlabeled topologies), A000112 (unlabeled posets), A006057.
Sequences in the Erné (1974) paper: A000798, A001035, A006056, A006057, A001929, A001927, A006058, A006059, A000110.
Cf. A316978, A319564, A326876, A326906, A326939, A326943, A326944, A326947.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&MemberQ[#,Range[n]]&&UnsameQ@@dual[#]&&SubsetQ[#,Union@@@Tuples[#,2]]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}] (* Gus Wiseman, Aug 14 2019 *)

A000798(n) = Sum_{k=0..n} Stirling2(n,k)*a(k).
Related to A000112 by Erné's formulas: a(n+1) = -s(n, 1), a(n+2) = n*a(n+1) + s(n, 2), a(n+3) = binomial(n+4, 2)*a(n+2) - s(n, 3), where s(n, k) = sum(binomial(n+k-1-m, k-1)*binomial(n+k, m)*sum((m!)/(number of automorphisms of P)*(-(number of antichains of P))^k, P an unlabeled poset with m elements), m=0..n).
From Altug Alkan, Dec 22 2015: (Start)
a(p^k) == 1 (mod p) for all primes p and for all nonnegative integers k.
a(n + p) == a(n + 1) (mod p) for all primes p and for all nonnegative integers n.
If n = 1, then a(1 + p) == a(2) (mod p), that is, a(p + 1) == 3 (mod p).
If n = p, then a(p + p) == a(p + 1) (mod p), that is, a(2*p) == a(p + 1) (mod p).
In conclusion, a(2*p) == 3 (mod p) for all primes p.
(End)
a(n) = Sum_{k=0..n} Stirling1(n,k)*A000798(k). - Tian Vlasic, Feb 25 2022

a(15)-a(16) from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

a(17)-a(18) from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

A080108 a(n) = Sum_{k=1..n} k^(n-k)*binomial(n-1,k-1).

Original entry on oeis.org

1, 2, 6, 23, 104, 537, 3100, 19693, 136064, 1013345, 8076644, 68486013, 614797936, 5818490641, 57846681092, 602259154853, 6548439927680, 74180742421185, 873588590481988, 10674437936521069, 135097459659312176

Offset: 1

Vladeta Jovovic, Mar 15 2003

nonn

Row sums of triangle A154372. Example: a(3)=1+12+9+1=23. From A152818. - Paul Curtz, Jan 08 2009
Number of pointed set partitions of a pointed set k[1...k...n] with a prescribed point k. - Gus Wiseman, Sep 27 2015
With offset 0, a(n) is the number of partial functions (A000169) from [n]->[n] such that every element  in the domain of definition is mapped to a fixed point.  This implies a(n) is the number of idempotent partial functions Cf. A121337. - Geoffrey Critzer, Aug 07 2016

			G.f. = x + 2*x^2 + 6*x^3 + 23*x^4 + 104*x^5 + 537*x^6 + 3100*x^7 + 19693*x^8 + ...
The a(4) = 23 pointed set partitions of 1[1 2 3 4] are 1[1[1 2 3 4]], 1[1[1] 2[2 3 4]], 1[1[1] 3[2 3 4]], 1[1[1] 4[2 3 4]], 1[1[1 2] 3[3 4]], 1[1[1 2] 4[3 4]], 1[1[1 3] 2[2 4]], 1[1[1 3] 4[2 4]], 1[1[1 4] 2[2 3]], 1[1[1 4] 3[2 3]], 1[1[1 2 3] 4[4]], 1[1[1 2 4] 3[3]], 1[1[1 3 4] 2[2]], 1[1[1] 2[2] 3[3 4]], 1[1[1] 2[2] 4[3 4]], 1[1[1] 2[2 3] 4[4]], 1[1[1] 2[2 4] 3[3]], 1[1[1] 3[3] 4[2 4]], 1[1[1] 3[2 3] 4[4]], 1[1[1 2] 3[3] 4[4]], 1[1[1 3] 2[2] 4[4]], 1[1[1 4] 2[2] 3[3]], 1[1[1] 2[2] 3[3] 4[4]].

Vincenzo Librandi, Table of n, a(n) for n = 1..200

First column of array A098697.

Cf. A152818, A185298, A262671.

[(1/n)*(&+[Binomial(n,k)*k^(n-k+1): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 22 2023

Table[Sum[k^(n-k) Binomial[n-1,k-1],{k,n}],{n,30}] (* Harvey P. Dale, Aug 19 2012 *)
Table[SeriesCoefficient[Sum[x^k/(1-k*x)^k,{k,0,n}],{x,0,n}], {n,1,20}] (* Vaclav Kotesovec, Aug 06 2014 *)
CoefficientList[Series[E^(x*(1+E^x)), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Aug 06 2014 *)

a(n)=sum(k=1,n, k^(n-k)*binomial(n-1,k-1)) \\ Anders Hellström, Sep 27 2015

def A080108(n): return (1/n)*sum(binomial(n,k)*k^(n-k+1) for k in range(n+1))
[A080108(n) for n in range(1,31)] # G. C. Greubel, Jan 22 2023

G.f.: Sum_{k>0} x^k/(1-k*x)^k.
E.g.f. (for offset 0): exp(x*(1+exp(x))). - Vladeta Jovovic, Aug 25 2003
a(n) = A185298(n)/n.

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 6, 8, 0, 1, 11, 24, 16, 0, 1, 20, 70, 80, 32, 0, 1, 37, 195, 340, 240, 64, 0, 1, 70, 539, 1330, 1400, 672, 128, 0, 1, 135, 1498, 5033, 7280, 5152, 1792, 256, 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512

Offset: 0

Peter Luschny, Jan 08 2021

A006905(n) = Sum_{k=0..n} A001035(k) * T(n, k). - Michael Somos, Jul 18 2021

T(n, k) is the number of idempotent relations R on [n] containing exactly k strongly connected components such that the following conditional statement holds for all x, y in [n]: If x, y are in distinct strongly connected components of R then (x, y) is not in R. - Geoffrey Critzer, Jan 10 2024

			[0] 1;
[1] 0, 2;
[2] 0, 1,   4;
[3] 0, 1,   6,    8;
[4] 0, 1,  11,   24,    16;
[5] 0, 1,  20,   70,    80,    32;
[6] 0, 1,  37,  195,   340,   240,    64;
[7] 0, 1,  70,  539,  1330,  1400,   672,   128;
[8] 0, 1, 135, 1498,  5033,  7280,  5152,  1792,  256;
[9] 0, 1, 264, 4204, 18816, 35826, 34272, 17472, 4608, 512;

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Štefan Schwarz, On idempotent binary relations on a finite set, Czechoslovak Mathematical Journal, Vol. 20 (1970), No. 4, 696-702.
Eric Weisstein's World of Mathematics, Bell Polynomial.

Sum of row(n) is A000110(n+1).
Sum of row(n) - 2^n is A058681(n).
Alternating sum of row(n) is A109747(n).
Cf. A001035, A006905, A137375, A186081, A121337.

egf := exp(t*(exp(-x) - x - 1));
ser := series(egf, x, 22):
p := n -> coeff(ser, x, n);
seq(seq((-1)^n*n!*coeff(p(n), t, k), k=0..n), n = 0..10);
# Alternative:
T := (n, k) -> add(binomial(n, k - j)*Stirling2(n - k + j, j), j=0..k):
seq(seq(T(n, k), k = 0..n), n=0..9); # Peter Luschny, Feb 09 2021

T[ n_, k_] := Sum[ Binomial[n, k-j] StirlingS2[n-k+j, j], {j, 0 ,k}]; (* Michael Somos, Jul 18 2021 *)

T(n, k) = sum(j=0, k, binomial(n, j)*stirling(n-j, k-j, 2)); /* Michael Somos, Jul 18 2021 */

T(n, k) = (-1)^n * n! * [t^k] [x^n] exp(t*(exp(-x) - x - 1)).

n-th row polynomial R(n,x) = exp(-x)*Sum_{k >= 0} (x + k)^n * x^k/k! = Sum_{k = 0..n} binomial(n,k)*Bell(k,x)*x^(n-k), where Bell(n,x) denotes the n-th Bell polynomial. - Peter Bala, Jan 13 2022

New name from Peter Luschny, Feb 09 2021

A355730 Number of binary relations R on [n] such that R is contained in R^2.

Original entry on oeis.org

1, 2, 13, 333, 34924, 15339497, 28399641433

Offset: 0

Geoffrey Critzer, Jul 15 2022

Equivalently, a(n) is the number of binary relations R on [n] such that for all x,y in [n], if (x,y) is in R then there is a z in [n] such that (x,z) and (z,y) are both in R.  A relation having this property is sometimes called a dense relation.
Almost all relations are dense.
A relation is idempotent if and only if it is both transitive and dense.  A transitive relation R is dense (hence idempotent) if and only if there does not exist a pair (C_1,C_2) of edgeless components such that C_1 covers C_2 in the condensation of G(R).  Here, G(R) is the directed graph (with self loops allowed) associated to R.  The condensation of G(R) is the acyclic digraph obtained from G(R) 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.   See Schein reference.
If R is contained in R^2 then the maximal cyclic nets in R are primitive (A070322) so that R is convergent, i.e., the period of R is equal to 1. Moreover, R converges to its transitive closure so that the index of R is at most n.  See Rosenblatt reference. - Geoffrey Critzer, Sep 05 2023

			a(2) = 13 because all 16 binary relations on [2] are dense except for {{0,1},{0,0}}, {{0,0},{1,0}}, {{0,1},{1,0}}.

G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
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.
Wikipedia, Dense order.

Cf. A006905, A121337, A070322.

Table[B = Tuples[Tuples[{0, 1}, nn], nn]; subsetQ[matrix1_, matrix2_] :=
  Apply[And, Map[! MemberQ[#, 1] &, matrix1 - matrix2]];Select[B, subsetQ[#, Clip[#.#]] &] // Length, {nn, 0, 4}]

Limit_{n->oo} a(n)/2^(n^2) = 1.

a(5)-a(6) from Pontus von Brömssen, Jul 19 2022

Comments clarified by Geoffrey Critzer, Oct 16 2023

A360743 Number of idempotent binary relation matrices E on [n] such that E contains an identity matrix of order n-1 and (E - I_n)^2 = 0.

Original entry on oeis.org

1, 2, 9, 52, 435, 5046, 81501, 1823144, 56572263, 2435930410, 145888123953, 12173595399516, 1418664206897691, 231298954644947294, 52860840028599821445, 16957903154151836822608, 7647128139328190245443279, 4852236755345544324027858258

Offset: 0

Geoffrey Critzer, Feb 18 2023

nonn

A Boolean relation matrix R is said to be convergent in its powers if in the sequence {R,R^2,R^3, ...} there is an m such that R^m = R^(m+1).
An idempotent Boolean relation matrix E is said to have a proper power primitive iff there is a convergent relation R with limit matrix E where R is not equal to E.
If an idempotent Boolean relation matrix E contains an identity matrix of order  n-1 and (E-I_n)^2 = 0 then E has no proper power primitive.  The converse is not true for n>=4. Consider {{1,0,1,0}, {0,1,0,1}, {0,0,0,0}, {0,0,0,0}}.  The converse is erroneously stated and proved in Rosenblatt, Theorem 4.

Alois P. Heinz, Table of n, a(n) for n = 0..113
David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A001831, A121337.

a:= n-> (n+1)*add(binomial(n, k)*(2^k-1)^(n-k), k=0..n):
seq(a(n), n=0..18);  # Alois P. Heinz, Feb 18 2023

nn = 16; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[A[x] + x D[A[x], x], {x, 0, nn}], x]

a(n) = (n + 1)*A001831(n).

E.g.f.: x*A'(x) + A(x) where A(x) = Sum_{n>=0} x^n/n! exp((2^n-1)*x) is the e.g.f. for A001831.

Corrected by Geoffrey Critzer, Feb 24 2023

A261194 Encoded square binary matrices representing an idempotent relation.

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 16, 17, 18, 19, 20, 21, 23, 25, 27, 33, 37, 49, 53, 65, 67, 73, 75, 81, 83, 89, 91, 141, 144, 145, 148, 149, 153, 154, 155, 157, 159, 181, 209, 217, 219, 272, 273, 274, 275, 283, 291, 305, 307, 308, 309, 311, 337, 339, 347, 513, 517, 529

Offset: 0

Philippe Beaudoin, Aug 11 2015

nonn

We encode an n X n binary matrix reading it antidiagonal by antidiagonal, starting from the least significant bit. A given entry in the sequence therefore represents the infinite family of n X n matrices that can be obtained by adding zero antidiagonals. All of these matrices represent idempotent relations. This encoding makes it possible to obtain a sequence rather than a table.

			For example, 148 = 0b10010100 encodes all square matrices with the first four antidiagonals equal to ((0), (0, 1), (0, 1, 0), (0, 1, 0, 0)). For example the 3 X 3 matrix:
  0 1 0
  0 1 0
  0 1 0
and the 4 X 4 matrix:
  0 1 0 0
  0 1 0 0
  0 1 0 0
  0 0 0 0
and all larger square matrices constructed in the same way. Since 148 is in the sequence, all these matrices are idempotent.

Philippe Beaudoin, Table of n, a(n) for n = 0..6672

Cf. A121337, A231428, A261195.

def getBitIndex(i, j):
  return (i+j)*(i+j+1)//2 + j
def getBit(mat, i, j):
  return (mat >> getBitIndex(i, j)) & 1
def setBit(mat, i, j):
  return mat | (1 << getBitIndex(i, j))
def noBitLeft(mat, i, j):
  return mat >> getBitIndex(i, j) == 0
def squarematrix(mat):
  result = 0;
  i = 0
  while True:
    if noBitLeft(mat, i, 0):
      return result
    j = 0;
    while True:
      if noBitLeft(mat, 0, j):
        break
      k = 0
      while True:
        if noBitLeft(mat, i, k):
          break
        if getBit(mat, i, k) & getBit(mat, k, j):
          result = setBit(result, i, j)
          break
        k += 1
      j += 1
    i += 1
  return result
index = 0
mat = 0
while True:
  if mat == squarematrix(mat):
    print(index, mat)
    index += 1
  mat += 1

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.

A366722 Number of limit dominated binary relations on [n].

Original entry on oeis.org

1, 2, 13, 399, 55894

Offset: 0

Geoffrey Critzer, Oct 17 2023

A relation R is limit dominated iff R converges to a single limit L (A365534) and R is contained in L.
A convergent relation R is limit dominated iff the following implication holds for all x,y in [n].  If (x,y) is in R then there is a cyclic traverse from x to y in G(R), where G(R) is the directed graph with loops associated to R.
A relation R is limit dominated iff it converges to L, the smallest transitive relation (A006905) containing R. In which case, L is the union of R^i for all i >= 1. - Geoffrey Critzer, Dec 03 2023

			Every idempotent relation (A121337) is limit dominated.
Every dense relation (A355730) is limit dominated.
Every primitive relation (A070322) is limit dominated.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, pp. 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, A366194, A355730, A070322.

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

Original entry on oeis.org

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).

A360718 Number of idempotent Boolean relation matrices on [n] that have no proper power primitive.

Original entry on oeis.org

1, 2, 9, 52, 459, 5526, 91161, 2039024, 62264215, 2618031658, 153147765333, 12544274587956, 1443661355799075, 233590364506712318, 53152637809972391281, 17010099259539378971368, 7660283773351147860024879, 4856904906875123474086041426

Offset: 0

Geoffrey Critzer, Feb 24 2023

nonn

A Boolean relation matrix R is said to be convergent in its powers if in the sequence {R, R^2, R^3, ...} there is an m such that R^m = R^(m+1).
An idempotent Boolean relation matrix E is said to have a proper power primitive iff there is a convergent relation R with limit matrix E where R is not equal to E.
Let P = C_1 + C_2 + ... + C_k + S be a poset with rank(P) <= 1 (A001831) where each C_i is a weakly connected component of size 2 or more and S is a set of isolated points. Let A be a subset of [n] and let E = P - {(x, x): x in A}. Then E is an idempotent relation with no proper power primitive iff A satisfies exactly one of the following conditions:
  i) A is a nonempty subset of domain(E) and A contains at most one point in domain(C_i) for 1 <= i <= k.
  ii) A is a nonempty subset of image(E) and A contains at most one point in image(C_i) for 1 <= i <= k.
  iii) A contains at most one point in S.
The first term in the e.g.f. below counts the number of such relations for which condition i) or ii) is satisfied.  The second term in the e.g.f. counts the number of such relations for which condition iii) is satisfied. - Geoffrey Critzer, Feb 11 2024

David Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research, National Bureau of Standards, Vol 67B No. 4 Oct-Dec 1963.

Cf. A360743, A001831, A121337, A002031.

nn = 17; A[x_] := Sum[x^n/n! Exp[(2^n - 1) x], {n, 0, nn}]; c[x_] := Log[A[x]] - x; Range[0, nn]! CoefficientList[Series[2 (Exp[x D[c[x], x]/2] - 1) Exp[c[x]] Exp[x] + Exp[c[x]] D[x Exp[x], x], {x, 0, nn}], x]

E.g.f.: 2(exp(x * c'(x)/2) - 1) exp(c(x)) exp(x) + exp(c(x))*(x exp(x))' where c(x) is the e.g.f. for A002031.

cp's OEIS Frontend

A001035 Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A080108 a(n) = Sum_{k=1..n} k^(n-k)*binomial(n-1,k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A340264 T(n, k) = Sum_{j=0..k} binomial(n, k - j)*Stirling2(n - k + j, j). Triangle read by rows, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A355730 Number of binary relations R on [n] such that R is contained in R^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A360743 Number of idempotent binary relation matrices E on [n] such that E contains an identity matrix of order n-1 and (E - I_n)^2 = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A261194 Encoded square binary matrices representing an idempotent relation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

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

Views

Author

Keywords