A000595 -id:A000595 - cp's OEIS frontend

A175716 The total number of elements(ordered pairs) in all equivalence relations on {1,2,...,n}.

0, 1, 6, 27, 120, 560, 2778, 14665, 82232, 488403, 3062980, 20221520, 140134404, 1016698813, 7703878042, 60833235795, 499592325152, 4259301450652, 37634032670886, 344092369602461, 3250925202629100

Offset: 0

Geoffrey Critzer, Dec 04 2010

			a(2) = 6 because the equivalence relations on {1,2}: {(1,1), (2,2)}, {(1,1), (2,2), (1,2), (2,1)} contain 6 ordered pairs.

Cf. A124427, A000595.

f[list_] := Length[list]^2; Table[Total[Map[f, Level[SetParttions[n], {2}]]], {n, 0, 12}] (* or *)
Range[0,20]! CoefficientList[Series[(x + x^2)Exp[x] * Exp[Exp[x] - 1], {x, 0, 20}], x]

a(n) = n*A124427(n). - Joerg Arndt, Dec 04 2010

E.g.f.: (x+x^2) * exp(x) * exp(exp(x)-1).

A320993 Number of connected self-dual marked graphs on 2n nodes.

Original entry on oeis.org

1, 1, 6, 81, 2796, 285205, 96322648, 112087066485, 458071927263177, 6665704296474517580, 349377209492189224235030, 66602723163954143548104716149, 46557323273646194397454383970079368, 120168498151800396724425771086539073209571, 1152049915423012273792614840558950392103437052846

Offset: 0

N. J. A. Sloane, Oct 26 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 274.
Andrew Howroyd, PARI Program

Cf. A000666 (not necessarily connected marked graphs), A000595 (self dual on 2n nodes), A054921 (connected marked graphs).

\\ See link for program.
A320993seq(15) \\ Andrew Howroyd, Jan 27 2020

a(2*n-1) = b(2*n-1) - A054921(2*n-1)/2, a(2*n) = b(2*n) - (A054921(2*n)-a(n))/2 where b is the Inverse Euler transform of A000595. - Andrew Howroyd, Jan 27 2020

a(0)=1 prepended and terms a(7) and beyond from Andrew Howroyd, Jan 26 2020

A326253 Number of sequences of distinct ordered pairs of positive integers up to n.

Original entry on oeis.org

1, 2, 65, 986410, 56874039553217, 42163840398198058854693626, 1011182700521015817607065606491025592595137, 1653481537585545171449931620186035466059689728986775126016505970

Offset: 0

Gus Wiseman, Jun 21 2019

nonn

			The a(2) = 65 sequences:
  ()  (11)  (11,12)  (11,12,21)  (11,12,21,22)
      (12)  (11,21)  (11,12,22)  (11,12,22,21)
      (21)  (11,22)  (11,21,12)  (11,21,12,22)
      (22)  (12,11)  (11,21,22)  (11,21,22,12)
            (12,21)  (11,22,12)  (11,22,12,21)
            (12,22)  (11,22,21)  (11,22,21,12)
            (21,11)  (12,11,21)  (12,11,21,22)
            (21,12)  (12,11,22)  (12,11,22,21)
            (21,22)  (12,21,11)  (12,21,11,22)
            (22,11)  (12,21,22)  (12,21,22,11)
            (22,12)  (12,22,11)  (12,22,11,21)
            (22,21)  (12,22,21)  (12,22,21,11)
                     (21,11,12)  (21,11,12,22)
                     (21,11,22)  (21,11,22,12)
                     (21,12,11)  (21,12,11,22)
                     (21,12,22)  (21,12,22,11)
                     (21,22,11)  (21,22,11,12)
                     (21,22,12)  (21,22,12,11)
                     (22,11,12)  (22,11,12,21)
                     (22,11,21)  (22,11,21,12)
                     (22,12,11)  (22,12,11,21)
                     (22,12,21)  (22,12,21,11)
                     (22,21,11)  (22,21,11,12)
                     (22,21,12)  (22,21,12,11)

Cf. A000522, A000595, A002416, A095661, A229865, A326209, A326237, A326251, A326252, A326258.

Table[Sum[k!*Binomial[n^2,k],{k,0,n^2}],{n,0,4}]

a(n) = A000522(n^2).

A381089 Number of binary relations on n unlabeled points without isolated points.

Original entry on oeis.org

1, 0, 7, 86, 2846, 285984, 96348100, 112089342912, 458072631172864, 6665705090236713408, 349377212708652631367712, 66602723210653815331014240512, 46557323276092409455163109412993536, 120168498152266645852126063743794842575872

Offset: 0

Peter Dolland, Feb 13 2025

nonn

Equivalently, the number of simple digraphs on n unlabeled two-colored nodes where each node is connected to at least one other node.

			For n = 2 there are 10 (=A000595(2)) - 3 (=number of relations with isolated points) = 7 = a(2) relations.
For n = 3 there are 104 (=A000595(3)) - 2 * 7 (=number of relations with exactly one isolated point) - 3 * 0 (=number of relations with exactly two isolated points) - 4 * 1 (=number of relations with exactly three isolated points) = 86 = a(3) relations.

Alois P. Heinz, Table of n, a(n) for n = 0..50

Cf. A000595.

a(n) = A000595(n) - Sum_{i=1..n} (i+1)*a(n-i).

A384105 Triangle read by rows: T(n,k) is the number of binary relations on a set of n objects, exactly k of which are self referencing, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 3, 4, 3, 16, 36, 36, 16, 218, 752, 1104, 752, 218, 9608, 45960, 90416, 90416, 45960, 9608, 1540944, 9133760, 22692704, 30194176, 22692704, 9133760, 1540944, 882033440, 6154473664, 18425858880, 30679088480, 30679088480, 18425858880, 6154473664, 882033440

Offset: 0

Peter Dolland, May 19 2025

Also the number of essentially different simple digraphs on a node set A of size n with a distinguished subset B of size k, where elements are indistinguishable within B and within A \ B.

			Triangle starts:
            1
            1,              1
            3,              4,              3
           16,             36,             36,              16
          218,            752,           1104,             752,             218
         9608,          45960,          90416,           90416,           45960, ...
      1540944,        9133760,       22692704,        30194176,        22692704, ...
    882033440,     6154473664,    18425858880,     30679088480,     30679088480, ...
1793359192848, 14334221970688, 50138592081152, 100240050239744, 125284653092864, ...
...

Peter Dolland, Python calculation of T(n,k)

Cf. A000273 (edge cases), A000595 (row sums), A353996, A328874, A383617.

T(n,k) = T(n,n-k).
T(n,0) = T(n,n) = A000273(n).
T(n,1) = T(n,n-1) = A353996(n+1) = A329874(n,4).
Sum_{k=0..n} T(n,k) = A000595(n).

A030243 Number of nonisomorphic relations with a nontrivial symmetry.

Original entry on oeis.org

0, 0, 4, 34, 580, 23702

Offset: 0

Christian G. Bower

Equals A000595-A030242.

A174137 Partial sums of A006905.

Original entry on oeis.org

1, 3, 16, 187, 4181, 158484, 9573673, 887796203, 123095499826, 25013843421773, 7332464142932061, 3060854010476035118, 1800064413234246359355, 1477862758280253372432667, 1680717420907850482529235664

Offset: 0

Jonathan Vos Post, Mar 09 2010

nonn

Partial sums of number of transitive relations on n labeled nodes. After 3, none of the values shown is prime.

Cf. A006905, A000595, A001173, A091073.

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

A382018 Number of orbits under the action of the permutation group S(n) on the nonsingular n X n matrices over GF(2).

Original entry on oeis.org

1, 1, 4, 33, 908, 85411, 28227922, 32597166327

Offset: 0

Søren Fuglede Jørgensen, Mar 12 2025

The action is defined by f.M(i,j)=M(f(i),f(j)).

Equivalently, the number of digraphs on n unlabeled nodes with loops allowed but no more than one arc with the same start and end node with adjacency matrices invertible over GF(2).

			For n = 2, representatives of the four different orbits are [[1, 0], [0, 1]], [[1, 1], [0, 1]], [[0, 1], [1, 1]], and [[0, 1], [1, 0]].

Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, On Exact Sizes of Minimal CNOT Circuits, RC 2025, LNCS, vol 15716, pp. 71-88; arXiv:2503.01467 [quant-ph], 2025, Table 1.

Cf. A000595, A002884, A224879.

cp's OEIS Frontend

A175716 The total number of elements(ordered pairs) in all equivalence relations on {1,2,...,n}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A320993 Number of connected self-dual marked graphs on 2n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A326253 Number of sequences of distinct ordered pairs of positive integers up to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A381089 Number of binary relations on n unlabeled points without isolated points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A384105 Triangle read by rows: T(n,k) is the number of binary relations on a set of n objects, exactly k of which are self referencing, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A030243 Number of nonisomorphic relations with a nontrivial symmetry.

Views

Author

Keywords

Crossrefs

A174137 Partial sums of A006905.

Views

Author

Keywords

Comments

Crossrefs

Formula

A382018 Number of orbits under the action of the permutation group S(n) on the nonsingular n X n matrices over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs