A070322 -id:A070322 - cp's OEIS frontend

A002522 a(n) = n^2 + 1.

1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, 122, 145, 170, 197, 226, 257, 290, 325, 362, 401, 442, 485, 530, 577, 626, 677, 730, 785, 842, 901, 962, 1025, 1090, 1157, 1226, 1297, 1370, 1445, 1522, 1601, 1682, 1765, 1850, 1937, 2026, 2117, 2210, 2305, 2402, 2501

Offset: 0

N. J. A. Sloane

An n X n nonnegative matrix A is primitive (see A070322) iff every element of A^k is > 0 for some power k. If A is primitive then the power which should have all positive entries is <= n^2 - 2n + 2 (Wielandt).
a(n) = Phi_4(n), where Phi_k is the k-th cyclotomic polynomial.
As the positive solution to x=2n+1/x is x=n+sqrt(a(n)), the continued fraction expansion of sqrt(a(n)) is {n; 2n, 2n, 2n, 2n, ...}. - Benoit Cloitre, Dec 07 2001
a(n) is one less than the arithmetic mean of its neighbors: a(n) = (a(n-1) + a(n+1))/2 - 1. E.g., 2 = (1+5)/2 - 1, 5 = (2+10)/2 - 1. - Amarnath Murthy, Jul 29 2003
Equivalently, the continued fraction expansion of sqrt(a(n)) is (n;2n,2n,2n,...). - Franz Vrabec, Jan 23 2006
Number of {12,1*2*,21}-avoiding signed permutations in the hyperoctahedral group.
The number of squares of side 1 which can be drawn without lifting the pencil, starting at one corner of an n X n grid and never visiting an edge twice is n^2-2n+2. - Sébastien Dumortier, Jun 16 2005
Also, numbers m such that m^3 - m^2 is a square, (n*(1 + n^2))^2. - Zak Seidov
1 + 2/2 + 2/5 + 2/10 + ... = Pi*coth Pi [Jolley], see A113319. - Gary W. Adamson, Dec 21 2006
For n >= 1, a(n-1) is the minimal number of choices from an n-set such that at least one particular element has been chosen at least n times or each of the n elements has been chosen at least once. Some games define "matches" this way; e.g., in the classic Parker Brothers, now Hasbro, board game Risk, a(2)=5 is the number of cards of three available types (suits) required to guarantee at least one match of three different types or of three of the same type (ignoring any jokers or wildcards). - Rick L. Shepherd, Nov 18 2007
Positive X values of solutions to the equation X^3 + (X - 1)^2 + X - 2 = Y^2. To prove that X = n^2 + 1: Y^2 = X^3 + (X - 1)^2 + X - 2 = X^3 + X^2 - X - 1 = (X - 1)(X^2 + 2X + 1) = (X - 1)*(X + 1)^2 it means: (X - 1) must be a perfect square, so X = n^2 + 1 and Y = n(n^2 + 2). - Mohamed Bouhamida, Nov 29 2007
{a(k): 0 <= k < 4} = divisors of 10. - Reinhard Zumkeller, Jun 17 2009
Appears in A054413 and A086902 in relation to sequences related to the numerators and denominators of continued fractions convergents to sqrt((2*n)^2/4 + 1), n=1, 2, 3, ... . - Johannes W. Meijer, Jun 12 2010
For n > 0, continued fraction [n,n] = n/a(n); e.g., [5,5] = 5/26. - Gary W. Adamson, Jul 15 2010
The only real solution of the form f(x) = A*x^p with negative p which satisfies f^(m)(x) = f^[-1](x), x >= 0, m >= 1, with f^(m) the m-th derivative and f^[-1] the compositional inverse of f, is obtained for m=2*n, p=p(n)= -(sqrt(a(n))-n) and A=A(n)=(fallfac(p(n),2*n))^(-p(n)/(p(n)+1)), with fallfac(x,k):=Product_{j=0..k-1} (x-j) (falling factorials). See the T. Koshy reference, pp. 263-4 (there are also two solutions for positive p, see the corresponding comment in A087475). - Wolfdieter Lang, Oct 21 2010
n + sqrt(a(n)) = [2*n;2*n,2*n,...] with the regular continued fraction with period 1. This is the even case. For the general case see A087475 with the Schroeder reference and comments. For the odd case see A078370.
a(n-1) counts configurations of non-attacking bishops on a 2 X n strip [Chaiken et al., Ann. Combin. 14 (2010) 419]. - R. J. Mathar, Jun 16 2011
Also numbers k such that 4*k-4 is a square. Hence this sequence is the union of A053755 and A069894. - Arkadiusz Wesolowski, Aug 02 2011
a(n) is also the Moore lower bound on the order, A191595(n), of an (n,5)-cage. - Jason Kimberley, Oct 17 2011
Left edge of the triangle in A195437: a(n+1) = A195437(n,0). - Reinhard Zumkeller, Nov 23 2011
If h (5,17,37,65,101,...) is prime is relatively prime to 6, then h^2-1 is divisible by 24. - Vincenzo Librandi, Apr 14 2014
The identity (4*n^2+2)^2 - (n^2+1)*(4*n)^2 = 4 can be written as A005899(n)^2 - a(n)*A008586(n)^2 = 4. - Vincenzo Librandi, Jun 15 2014
a(n) is also the number of permutations simultaneously avoiding 213 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014
a(n-1) is the maximum number of stages in the Gale-Shapley algorithm for finding a stable matching between two sets of n elements given an ordering of preferences for each element (see Gura et al.). - Melvin Peralta, Feb 07 2016
Because of Fermat's little theorem, a(n) is never divisible by 3. - Altug Alkan, Apr 08 2016
For n > 0, if a(n) points are placed inside an n X n square, it will always be the case that at least two of the points will be a distance of sqrt(2) units apart or less. - Melvin Peralta, Jan 21 2017
Also the limit as q->1^- of the unimodal polynomial (1-q^(n*k+1))/(1-q) after making the simplification k=n. The unimodal polynomial is from O'Hara's proof of unimodality of q-binomials after making the restriction to partitions of size <= 1. See G_1(n,k) from arXiv:1711.11252. As the size restriction s increases, G_s->G_infinity=G: the q-binomials. Then substituting k=n and q=1 yields the central binomial coefficients: A000984. - Bryan T. Ek, Apr 11 2018
a(n) is the smallest number congruent to both 1 (mod n) and 2 (mod n+1). - David James Sycamore, Apr 04 2019
a(n) is the number of permutations of 1,2,...,n+1 with exactly one reduced decomposition. - Richard Stanley, Dec 22 2022
From Klaus Purath, Apr 03 2025: (Start)
The odd prime factors of these terms are always of the form 4*k + 1.
All a(n) = D satisfy the Pell equation (k*x)^2 - D*y^2 = -1. The values for k and the solutions x, y can be calculated using the following algorithm: k = n, x(0) = 1, x(1) = 4*D - 1, y(0) = 1, y(1) = 4*D - 3. The two recurrences are of the form (4*D - 2, -1). The solutions x, y of the Pell equations for n = {1 ... 14} are in OEIS.
It follows from the above that this sequence is a subsequence of A031396. (End)

			G.f. = 1 + 2*x + 5*x^2 + 10*x^3 + 17*x^4 + 26*x^5 + 37*x^6 + 50*x^7 + 65*x^8 + ...

S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 120).
E. Gura and M. Maschler, Insights into Game Theory: An Alternative Mathematical Experience, Cambridge, 2008; p. 26.
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley and Sons, New York, 2001.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000. Format corrected by _Peter Kagey_, Jan 25 2016
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, On the Salient Regularities of Strings of Assembly Theory, Preprints (2024). See p. 19.
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints.org (2025). See p. 28.
R. P. Boas and N. J. A. Sloane, Correspondence, 1974
Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 44, 56.
Giulio Cerbai and Luca Ferrari, Permutation patterns in genome rearrangement problems: the reversal model, arXiv:1903.08774 [math.CO], 2019. See p. 19.
S. Chaiken et al., Nonattacking Queens in a Rectangular Strip, arXiv:1105.5087 [math.CO], 2011.
Bryan Ek, Unimodal Polynomials and Lattice Walk Enumeration with Experimental Mathematics, arXiv:1804.05933 [math.CO], 2018.
R. M. Green and Tianyuan Xu, 2-roots for simply laced Weyl groups, arXiv:2204.09765 [math.RT], 2022.
Guo-Niu Han, Enumeration of Standard Puzzles
Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv:1410.2657 [math.CO], 2014.
C. Homberger and V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.
L. B. W. Jolley, Summation of Series, Dover, 1961, p. 176.
S. J. Leon, Linear Algebra with Applications: the Perron-Frobenius Theorem [Cached copy at the Wayback Machine]
T. Mansour and J. West, Avoiding 2-letter signed patterns, arXiv:math/0207204 [math.CO], 2002.
Michelle Rudolph-Lilith, On the Product Representation of Number Sequences, with Application to the Fibonacci Family, arXiv:1508.07894 [math.NT], 2015.
Eric Weisstein's World of Mathematics, Number Picking
Eric Weisstein's World of Mathematics, Near-Square Prime
Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-648. volume 52
Reinhard Zumkeller, Enumerations of Divisors
Index to values of cyclotomic polynomials of integer argument
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Left edge of A055096.
Cf. A059100, A117950, A087475, A117951, A114949, A117619 (sequences of form n^2 + K).
a(n+1) = A101220(n, n+1, 3).
Cf. A059592, A124808, A132411, A132414, A028872, A005408, A000124, A016813, A086514, A000125, A058331, A080856, A000127, A161701-A161704, A161706, A161707, A161708, A161710-A161713, A161715, A006261.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), this sequence (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A002496 (primes).
Cf. A254858.
Cf. A302612, A302644, A302645, A302646.
Subsequence of A031396.

a002522 = (+ 1) . (^ 2)
a002522_list = scanl (+) 1 [1,3..]
-- Reinhard Zumkeller, Apr 06 2012

[n^2 + 1: n in [0..50]]; // Vincenzo Librandi, May 01 2011

A002522 := proc(n)
        numtheory[cyclotomic](4,n) ;
end proc:
seq(A002522(n),n=0..20) ; # R. J. Mathar, Feb 07 2014

Table[n^2 + 1, {n, 0, 50}]; (* Vladimir Joseph Stephan Orlovsky, Dec 15 2008 *)

A002522(n):=n^2+1$ makelist(A002522(n),n,0,30); /* Martin Ettl, Nov 07 2012 */

a(n)=n^2+1 \\ Charles R Greathouse IV, Jun 10 2011

O.g.f.: (1-x+2*x^2)/((1-x)^3). - Eric Werley, Jun 27 2011
Sequences of the form a(n) = n^2 + K with offset 0 have o.g.f. (K - 2*K*x + K*x^2 + x + x^2)/(1-x)^3 and recurrence a(n) = 3*a(n-1) - 3*a(n-2) + a*(n-3). - R. J. Mathar, Apr 28 2008
For n > 0: a(n-1) = A143053(A000290(n)) - 1. - Reinhard Zumkeller, Jul 20 2008
A143053(a(n)) = A000290(n+1). - Reinhard Zumkeller, Jul 20 2008
a(n)*a(n-2) = (n-1)^4 + 4. - Reinhard Zumkeller, Feb 12 2009
a(n) = A156798(n)/A087475(n). - Reinhard Zumkeller, Feb 16 2009
From Reinhard Zumkeller, Mar 08 2010: (Start)
a(n) = A170949(A002061(n+1));
A170949(a(n)) = A132411(n+1);
A170950(a(n)) = A002061(n+1). (End)
For n > 1, a(n)^2 + (a(n) + 1)^2 + ... + (a(n) + n - 2)^2 + (a(n) + n - 1 + a(n) + n)^2 = (n+1) *(6*n^4 + 18*n^3 + 26*n^2 + 19*n + 6) / 6 = (a(n) + n)^2 + ... + (a(n) + 2*n)^2. - Charlie Marion, Jan 10 2011
From Eric Werley, Jun 27 2011: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2.
a(n) = a(n-1) + 2*n - 1. (End)
a(n) = (n-1)^2 + 2(n-1) + 2 = 122 read in base n-1 (for n > 3). - Jason Kimberley, Oct 20 2011
a(n)*a(n+1) = a(n*(n+1) + 1) so a(1)*a(2) = a(3). More generally, a(n)*a(n+k) = a(n*(n+k) + 1) + k^2 - 1. - Jon Perry, Aug 01 2012
a(n) = (n!)^2* [x^n] BesselI(0, 2*sqrt(x))*(1+x). - Peter Luschny, Aug 25 2012
a(n) = A070216(n,1) for n > 0. - Reinhard Zumkeller, Nov 11 2012
E.g.f.: exp(x)*(1 + x + x^2). - Geoffrey Critzer, Aug 30 2013
a(n) = A254858(n-2,3) for n > 2. - Reinhard Zumkeller, Feb 09 2015
Sum_{n>=0} (-1)^n / a(n) = (1+Pi/sinh(Pi))/2 = 0.636014527491... = A367976 . - Vaclav Kotesovec, Feb 14 2015
Sum_{n>=0} 1/a(n) = (1 + Pi*coth(Pi))/2 = 2.076674... = A113319. - Vaclav Kotesovec, Apr 10 2016
4*a(n) = A001105(n-1) + A001105(n+1). - Bruno Berselli, Jul 03 2017
From Amiram Eldar, Jan 20 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = sqrt(2)*csch(Pi)*sinh(sqrt(2)*Pi).
Product_{n>=1} (1 - 1/a(n)) = Pi*csch(Pi). (End)
Sum_{n>=0} a(n)/n! = 3*e. - Davide Rotondo, Feb 16 2025

Partially edited by Joerg Arndt, Mar 11 2010

A365534 Number of convergent Boolean relation matrices on [n].

Original entry on oeis.org

1, 2, 15, 465, 61068, 32453533, 67904955351

Offset: 0

Geoffrey Critzer, Sep 08 2023

A Boolean relation matrix R is convergent iff R^k = R^(k+1) for all sufficiently large k. In other words, iff the period of R is equal to 1. The digraph of R is such that all its maximal cyclic nets are primitive (A070322) iff R is convergent. Cf. Rosenblatt link. Also, R is convergent iff every diagonal block in its Frobenius normal form is either primitive or a 1 X 1 zero matrix, Theorem 1.1 in Gregory, Kirkland and Pullman.

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.
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
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.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A070322, A002416.

Sum_{n>=0} a_n*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(p(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), p(x) = Sum_{n>=0} A070322(n)x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A070322(n) <= a(n) <= 2^(n^2) = A002416(n).

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

A367948 Triangular array read by rows. T(n,k) is the number of strongly connected binary relations on [n] (A186081) with period k, n >= 1, 1<=k<=n.

Original entry on oeis.org

1, 3, 1, 139, 3, 2, 25575, 103, 12, 6, 18077431, 4815, 230, 60, 24

Offset: 1

Geoffrey Critzer, Dec 05 2023

Let A be a strongly connected binary relation on [n] with period k. Then k is equal to the greatest common divisor (GCD) of the lengths of the cycles in G(A) the directed graph (self loops allowed) associated to A. See section 5.2 in Ki Hang Kim reference. Also, k is equal to the GCD of all the integers e >=1 such that G(A^e) has at least one self loop. See Theorem 6.6 in Schwarz link. Also, for each pair of vertices x,y in G(A) the lengths of the directed walks from x to y are congruent modulo k. See Lemma 3.4.1 in Brualdi and Ryser reference. Finally, the idempotent in {A^i:i>=1} is the equivalence relation ~ defined by: For all x,y in [n], x ~ y iff the lengths of the xy-walks in G(A) are congruent to 0 modulo k. The equivalence relation ~ partitions [n] into exactly k blocks. See Theorem 7.3 in Schwarz link.

			Triangle begins ...
        1;
        3,    1;
      139,    3,   2;
    25575,  103,  12,  6;
 18077431, 4815, 230, 60, 24;
 ...
T(4,3) = 12.  Let A be the strongly connected relation on [4] whose adjacency matrix is {{0,0,0,1},{0,0,0,1},{1,1,0,0},{0,0,1,0}}. It is easy to check that the period of A is 3.  Also, G(A) contains two cycles of length 3 so that the GCD of its cycle length is 3.  Also {A^i:i>=1} contains the equivalence relation corresponding to the set partition {1,2}{3}{4}.  There are 12 relations in the same isomorphism class as A so that T(4,3) = 12.

R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1991, pages 53-96.
Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Dekker, 1982, pages 177-226.

S. Schwarz, On the semigroup of binary relations on a finite set, Czechoslovak Mathematical Journal, 1970.

Cf. A186081 (row sums), A070322 (column k=1).

T(n,1) = A070322(n).
T(n,n) = (n-1)! counts relations that are simple cycles.
Sum_{k=1..n} T(n,k) = A186081(n).

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

Original entry on oeis.org

1, 1, 4, 144, 25696, 18082560, 47025585664, 450955726792704, 16260917603754029056, 2253010420928564535951360, 1219004114245442237742488879104, 2601909995433633381004133738019815424, 22040854392120341022554569447470527813779456

Offset: 0

Geoffrey Critzer, Feb 12 2011

For n >= 2, a(n) is the number of strongly connected binary relations on [n]. - Geoffrey Critzer, Dec 04 2023

			a(2)=4 because there are four relations on {1,2} whose transitive closure is {(1,1), (1,2), (2,1), (2,2)}. They are the three nontransitive relations,{(1,2), (2,1)}, {(1,2), (2,1), (2,2)}, {(1,1), (1,2), (2,1)} and the trivial relation itself.

Cf. A002416, A003030, A070322, A361269.

Needs["Combinatorica`"];
f[list_] := Apply[Plus, Table[MatrixPower[list,n], {n,1,Length[list]}]];
Join[{1}, Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 1, 4}]]
(* Second program: *)
a[ n_] := If[ n < 1, Boole[n == 0], With[{triv = matnk[n, 2^n^2 - 1]}, Sum[ Boole[triv === transitiveClosure[ matnk[n, k]]], {k, 0, 2^n^2 - 1}]]]; matnk[n_, k_] := Partition[ IntegerDigits[ k, 2, n^2], n]; transitiveClosure[x_] := FixedPoint[ Sign@(# + Dot[#, x]) &, x, Length@x]; (* Michael Somos, Mar 08 2012 *)

From Geoffrey Critzer, Dec 04 2023: (Start)
For n >= 2, a(n) = A003030(n)*2^n = A361269(n,1).
E.g.f.: 1 + s(2*x) - x where s(x) is the e.g.f. for A003030. (End)

a(0)=1 prepended by Alois P. Heinz, Aug 31 2015
a(6) from Bert Dobbelaere, Feb 16 2019
a(7)-a(12) from Geoffrey Critzer, Dec 04 2023

A366218 Number of convergent binary relations on [n] (A365534) that converge to an equivalence relation (A000110).

Original entry on oeis.org

1, 1, 4, 149, 26177, 18211032, 47135163595

Offset: 0

Geoffrey Critzer, Oct 04 2023

Equivalently, a(n) is the number of Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322) and all the off diagonal blocks are 0-blocks. See Gregory, Kirkland, Pullman.

The limit of a convergent binary relation R is an equivalence relation iff every vertex and every edge in G(R) is on a cycle, where G(R) is the directed graph with loops associated to R. See Corollary to Theorem 1 in Rosenblatt.

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. A070322, A365534, A000110.

nn = 13; B[n_] := 2^Binomial[n, 2] n!; primitive = Select[Import["https://oeis.org/A070322/b070322.txt", "Table"],
Length@# == 2 &][[All, 2]];pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];Table[n!, {n, 0, nn}] CoefficientList[Series[Exp[pr[x] - 1], {x, 0, nn}], x]

E.g.f.: exp(p(x)-1) where p(x) is the e.g.f. for A070322.

A366252 Number of convergent binary relations on [n] (A365534) that converge to a quasi-order relation (A000798).

Original entry on oeis.org

1, 1, 6, 227, 37617, 23750562, 56091061929

Offset: 0

Geoffrey Critzer, Oct 05 2023

Equivalently, a(n) is the number of convergent Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322).

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.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Cf. A070322, A365534, A000798, A366218.

nn = 6; B[n_] := 2^Binomial[n, 2] n!; pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.
 Table[x^i ->x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[- (pr[x] - 1)]], {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(2^n*binomial(n,2)) = 1/(E(x) @ exp(-(p(x)-1))) where E(x) = Sum_{n>=0} x^n/(2^n*binomial(n,2)), p(x) is the e.g.f. for A070322, and @ is the exponential Hadamard product (see Panafieu and Dovgal).

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.

A370385 Triangular array read by rows. T(n,k) is the number of binary relations R on [n] such that the unique idempotent relation in {R^i:i>=1} is a quasi-order containing exactly k strongly connected components.

Original entry on oeis.org

1, 1, 3, 4, 139, 66, 48, 25575, 9280, 3072, 1536, 18077431, 4498530, 1174800, 322560, 122880

Offset: 1

Geoffrey Critzer, Feb 18 2024

			Triangle begins:
        1;
        1;
        3,       4;
      139,      66,      48;
    25575,    9280,    3072,   1536;
 18077431, 4498530, 1174800, 322560, 122880;
 ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A366866 (row sums), A070322 (column k=1), A011266 (main diagonal), A367948, A247231, A370464.

nn = 5; B[n_] := n! 2^Binomial[n, 2]; s[x_, y_] := y x + (3 y + y^2) x^2/2! + (139 y + 3 y^2 + 2 y^3) x^3/3! + (25575 y + 103 y^2 + 12 y^3 + 6 y^4) x^4/
    4! + (18077431 y + 4815 y^2 + 230 y^3 + 60 y^4 + 24 y^5) x^5/5! ;
ggf[egf_] :=Normal[Series[egf, {x, 0, nn}]] /.Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[
   Series[1/ggf[Exp[-s[x, y]]], {x, 0, nn}], {x, y}]]

Sum_{n>=1} Sum_{k=1..n} T(n,k)*y^k*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-s(x,y))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)) and @ is the exponential Hadamard product (see Panafieu and Dovgal) and s(x,y) is the e.g.f. for A367948.

A363834 Number of labeled digraphs (with self loops allowed) on [n] such that every strongly connected component of size at least 2 contains a vertex with a self loop.

Original entry on oeis.org

1, 2, 15, 452, 58023, 31083662, 66296957895, 554842541248592, 18340342731323665263, 2411916363098805776251322, 1266238008719333748929247025455, 2657054767893996575723268008873476172, 22295054304671836968688374028608806896204023

Offset: 0

Geoffrey Critzer, Oct 19 2023

nonn

The sequence gives a good lower bound for the number of convergent binary relations (A365534) which is only known for n <= 6.

			a(2) = 15 because there are 16 labeled digraphs with self loops on [2] and all of them are good except: [1->2,2->1].

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A365534, A070322, A003030.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; sm[x_] :=  Total[Table[2^n - 1, {n, 1, Length[strong]}] strong Table[ x^i/i!, {i, 1, 58}]]; ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /.
  Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(sm[x] + x)]], {x, 0, nn}], x]

Sum_{n>=0} a(n)*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(sm(x)-1+x))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), sm(x) = Sum_{n>=0} (2^n-1)*A003030(n)*x^n/n! and @ is the exponential Hadamard product (see Panafieu and Dovgal).

cp's OEIS Frontend

A002522 a(n) = n^2 + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A365534 Number of convergent Boolean relation matrices on [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

A367948 Triangular array read by rows. T(n,k) is the number of strongly connected binary relations on [n] (A186081) with period k, n >= 1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A366218 Number of convergent binary relations on [n] (A365534) that converge to an equivalence relation (A000110).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A366252 Number of convergent binary relations on [n] (A365534) that converge to a quasi-order relation (A000798).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula