A000595 -id:A000595 - cp's OEIS frontend

A000250 Number of symmetric reflexive relations on n nodes: (1/2)*A000666.

1, 3, 10, 45, 272, 2548, 39632, 1104306, 56871880, 5463113568, 978181717680, 326167542296048, 202701136710498400, 235284321080559981952, 511531711735594715527360, 2089424601541011618029114896, 16084004145036771186002041099712, 234026948449058790311618594954430848, 6454432593140577452393525511509194184320

Offset: 1

N. J. A. Sloane

Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; Enumeration of graphs with signed points and lines. J. Graph Theory 1 (1977), no. 4, 295-308.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
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).

Jean-François Alcover, Table of n, a(n) for n = 1..40
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]

Cf. A000595, A001173, A001174.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]} ] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2  n!)];
a /@ Range[19] (* Jean-François Alcover, Jan 17 2020, after Andrew Howroyd in A000666 *)

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000250(n): return int(sum(Fraction(1<>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items())-1,prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 14 2024

More terms from Vladeta Jovovic, Apr 18 2000

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007

A055973 Number of unlabeled digraphs with loops (relations) on n nodes and with an even number of arcs.

Original entry on oeis.org

1, 1, 6, 52, 1540, 145984, 48467296, 56141454464, 229148555640864, 3333310786076963968, 174695272746896566439424, 33301710992539090379269318144, 23278728241293494584257987458067456, 60084295633556503802059558812644803074048, 576025077880237078776946976495257043823396069376

Offset: 0

Vladeta Jovovic, Jul 19 2000

Also relations considered equivalent when isomorphic and when complemented. - Christian G. Bower, Jan 05 2004

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

Cf. A000171, A000595, A007869, A047832, A054928, A055974.

a(2*n) = (A000595(2*n) + A047832(n))/2; a(2*n+1) = A000595(2*n+1)/2.
a(n) = (A000595(n) + A000171(2*n+1))/2.
a(n) = sum {1*s_1+2*s_2+...=n, 1*t_1+2*t_2=2} (fixA[s_1, s_2, ...;t_1, t_2]/(1^s_1*s_1!*2^s_2*s_2!*...*1^t_1*t_1!*2^t_2*t_2!)) where fixA[...] = prod {i, j>=1} ( (sum {d|lcm(i, j)} (d*t_d))^(gcd(i, j)*s_i*s_j)) - Christian G. Bower, Jan 05 2004

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 19 2020

A055974 Number of unlabeled digraphs with loops (relations) on n nodes and with an odd number of arcs.

Original entry on oeis.org

0, 1, 4, 52, 1504, 145984, 48461696, 56141454464, 229148544420864, 3333310786076963968, 174695272746603272722432, 33301710992539090379269318144, 23278728241293494481773139193036800, 60084295633556503802059558812644803074048, 576025077880237078776946485247979728479746359296

Offset: 0

Vladeta Jovovic, Jul 19 2000

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

Cf. A000171, A000595, A047832, A054960, A055973.

a(2*n) = (A000595(2*n) - A047832(n))/2; a(2*n+1) = A000595(2*n+1)/2.

a(n) = (A000595(n) - A000171(2*n+1))/2.

a(0)=0 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 19 2020

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Original entry on oeis.org

0, 4, 72, 2608, 272752, 93847104, 110518842048, 454710381676032, 6640565658505128832, 348708024629593894001152, 66538376166308068986316241408, 46534722991725338264882258863095808, 120139253095727581744381043433138973706240, 1151909524447243687554850690730124812494959992832

Offset: 1

Peter Dolland, Nov 02 2019

nonn

Also the number of colored digraphs on n unlabeled nodes with nodes of exactly two colors. (Understand "(x,x) in the relation" for several nodes x as a special color!)

			n=2: We label node 1 with (1,1) in the relation and node 2 with (2,2) not in the relation, and we have two differently labeled nodes and so a(2) = A053763(2) = 4.
n=3: We have exactly either one or two nodes x with (x,x) in the relation. In A328773 this labelings correspond to the color schemes [2,1] and [1,2], both represented by the column index 2. So we have a(3) = 2 * A328773(3,2) = 72.

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

Cf. A000595 (arbitrary binary relations), A000273 (digraphs, i.e. reflexive resp. antireflexive binary relations), A053763 (digraphs with distinguishing labeled nodes), A328773 (digraphs with given color scheme).

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := Module[{s = 0}, Do[t = 2^edges[p]; s += t*(1 - 2^(1 - Length[p]))* permcount[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 14] (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i])}
a(n) = {my(s=0); forpart(p=n, my(t=2^edges(p)); s+=t*(1 - 2^(1-#p))*permcount(p)); s/n!} \\ Andrew Howroyd, Nov 02 2019

a(n) = A000595(n) - 2 * A000273(n) for n >= 1.

A343592 Number of symmetry types of digraphs with n nodes.

Original entry on oeis.org

1, 2, 4, 9, 14, 36

Offset: 1

Peter Dolland, Apr 21 2021

The symmetry type of a digraph is determined by its automorphism group. It is a permutation group on the nodes set, and therefore a subgroup of the symmetric group Sn. The total number of these is determined by A000638. But not all of them occur as an automorphism group of a digraph.

			The four symmetry types of the digraphs with 3 nodes are represented by:
1.) {}, the empty graph, has together with the full graph the automorphism group S_3 (as subgroup of S_3) as symmetry type.
2.) {(1,2)} has together with 6 other digraphs the trivial automorphism group {id} as symmetry type. This digraph class is called asymmetric. Their values are given by A051504.
3.) {(1,2),(2,1)} has together with 5 other digraphs the automorphism group containing id and a transposition (so it is C_2 as the subgroup of S_3) as symmetry type.
4.) {(1,2),(2,3),(3,1)} has as the only digraph with three nodes the automorphism group C_3 as symmetry type. As a consequence it has to be self-complementary.
The total of the sizes of the symmetry type classes yields the number of digraphs A000273. Here: 2+7+6+1 = 16 = A000273(3).
Note, that for n > 3 there may be different symmetry types with isomorphic automorphism groups. For n=4 both {(1,2)} and {(1,2),(3,4)} have C_2 as automorphism group, but they are different as permutation group.

Peter Dolland, Digraph Symmetry Tables for n = 3..6
Götz Pfeiffer, Subgroups. [broken link]

Cf. A000273, A000638, A051504, A053763, A000595.

A383617 Triangle read by rows: T(n,k) is the number of binary relations on a set of n objects, k of which are picked out, 0 <= k <= n.

Original entry on oeis.org

1, 2, 2, 10, 16, 10, 104, 272, 272, 104, 3044, 11456, 16960, 11456, 3044, 291968, 1432608, 2842304, 2842304, 1432608, 291968, 96928992, 578431232, 1441700480, 1920352256, 1441700480, 578431232, 96928992, 112282908928, 784780122880, 2351993457920, 3918054495616, 3918054495616, 2351993457920, 784780122880, 112282908928

Offset: 0

Peter Dolland, May 02 2025

The row sums are the number of simple digraphs with n 4-colored nodes. The colors result from the four cases combining the property self-referencing (yes/no) with "picked out" (yes/no).

			Triangle starts:
            1;
            2,            2;
           10,           16,            10;
          104,          272,           272,           104;
         3044,        11456,         16960,         11456,          3044;
       291968,      1432608,       2842304,       2842304,       1432608,  291968;
     96928992,    578431232,    1441700480,    1920352256,    1441700480, ...
 112282908928, 784780122880, 2351993457920, 3918054495616, 3918054495616, ...
...
Example n=2, k=1: The both objects are differentiated. As a consequence all binary relations on two different objects have to be counted: These are the subsets of the cross product of the objects set with itself. This contains four pairs, so the number of subsets is 2^4 = 16.

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

Cf. A000595 (edge cases), A353996 (row sums), A329874 (4th column = row sums).

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

A029849 Number of nonisomorphic and nonantiisomorphic relations.

Original entry on oeis.org

1, 2, 9, 74, 1740, 149572, 48575680, 56147642904, 229149201466592, 3333310913116926416, 174695272793893644765312, 33301710992572083379669646560, 23278728241293538748514513208527104

Offset: 0

Christian G. Bower, Jan 15 1998 and Jun 15 1998

Cf. A000595, A002500.

a(n) = (A000595(n) + A002500(n)) / 2. - Sean A. Irvine, Mar 05 2020

A046858 Irregular triangle read by rows: T(n,k) = number of directed graphs-with-loops with n nodes and k arcs (n >= 0, 0 <= k <= n^2).

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 2, 1, 1, 2, 8, 17, 24, 24, 17, 8, 2, 1, 1, 2, 9, 32, 95, 203, 373, 515, 584, 515, 373, 203, 95, 32, 9, 2, 1, 1, 2, 9, 36, 157, 549, 1692, 4374, 9626, 17874, 28373, 38486, 44805, 44805, 38486, 28373, 17874, 9626, 4374, 1692, 549, 157, 36, 9, 2, 1, 1

Offset: 0

N. J. A. Sloane

Equivalently, T(n,k) = number of relations on n-set with strength k (n >= 0, 0<=k<=n^2).

			Triangle begins:
[1],
[1, 1],
[1, 2, 4, 2, 1],
[1, 2, 8, 17, 24, 24, 17, 8, 2, 1],
[1, 2, 9, 32, 95, 203, 373, 515, 584, 515, 373, 203, 95, 32, 9, 2, 1] (the last batch giving the numbers of directed graphs with loops on 4 nodes and from 0 to 16 arcs).

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

Cf. A000595.

Needs["Combinatorica`"]; Join[{{1}, {1,1}}, CoefficientList[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n], Ordered], Permutations[Range[n^2-n+1, n^2]], 2],s]/.Table[s[i]->1+x^i, {i,1,n^2-n}], {n,2,7}], x]]//Grid (* Geoffrey Critzer, Sep 29 2012 *)

More terms from Vladeta Jovovic, Feb 07 2000

Edited by N. J. A. Sloane Apr 16 2008 at the suggestion of Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 24 2008

A054920 Number of connected unlabeled reflexive relations with n nodes such that complement is also connected.

Original entry on oeis.org

2, 4, 68, 2592, 278796, 95720106, 111891292036, 457846756500066, 6664787020904248568, 349363873490889302878250, 66602024342830108271942323060, 46557190064705399729526041154647820

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000595, A054919.

A000595 = Import["https://oeis.org/A000595/b000595.txt", "Table"][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
A054919 = Join[{1}, EulerInvTransform[A000595 // Rest]];
a[n_] := 2 A054919[[n + 1]] - A000595[[n + 1]];
Array[a, 50] (* Jean-François Alcover, Sep 01 2019, updated Mar 17 2020 *)

a(n) = 2*A054919(n) - A000595(n).

More terms from Vladeta Jovovic, Jul 17 2000

A154238 Number of orbits of the action g*b = b o (g x g) of the group of permutations g of an n-element set S on the set of closed binary operations b on S.

Original entry on oeis.org

1, 1, 10, 3411, 179228736, 2483590604688125, 14325593551925794051596768, 50976900379139614139041610902600299311, 155682086692129060007763454017522652304844346252853248

Offset: 0

David Pasino, Jan 05 2009, Jan 08 2009, Jan 12 2009

nonn

Here are several different ways of expressing the condition that g*b = b:
b(u, v) = b(gu, gv) for all u, v in S.
The level sets of b are closed under g x g.
The level sets of b are unions of cycles of g x g.
The cycles of g x g are subsets of level sets of b.
b is constant on cycles of g x g.
There is no requirement for g to be an automorphism of b. Given g, the fixed b are determined by simply choosing a value in S for each cycle of g x g. The product b(u, v) is defined to be that constant value for every (u, v) in the cycle.
So the number of degrees of freedom for b is the number of cycles of g x g. How many cycles does g have on S x S? If u is in a c-cycle C and v is in a d-cycle D, then (u, v) is in an lcm(c, d)-cycle and C x D is partitioned into these cycles, so there must be cd/lcm(c, d) of them, which is gcd(c, d).
So letting s_k be the number of k-cycles of g on S for each k from 1 to n, the total number of cycles of g on S x S is the sum on k and j of gcd(k, j) s_k s_j. That's the number of degrees of freedom for b and each degree has valence n, so raise n to that power. Then multiply by the well-known number of permutations of type s, which is n! divided by the factorials of the s_k and by the powers k^s_k. Add this up over all the partitions of n and divide by n!.
Additional comments from Christian G. Bower: This is the number of nonisomorphic n-state relations on a set of n elements. If at the step of raising n to the power, we raised instead some constant m to that power, the formula would give the number of isomorphism classes of m-state relations on an n-element set.

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

Cf. k-state relations: A000595 for k=2, A004105 for k=3, A001374 for k=4, A053516 for k=5.
Cf. A001329, A091057.
Cf. A000595, A004105, A001374, A053516. - Vladeta Jovovic, Jan 06 2009

a(n) = Sum_{1*s_1 + 2*s_2 + ... = n} (fixA[s_1, s_2,..]/(1^s_1*s_1!*2^s_2*s2!* ...)) where fixA[s_1, s_2, ...] = n^(Sum_{i, j>=1} gcd(i, j)*s_i*s_j).

Edited by Christian G. Bower and N. J. A. Sloane, Jan 08 2009

cp's OEIS Frontend

A000250 Number of symmetric reflexive relations on n nodes: (1/2)*A000666.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A055973 Number of unlabeled digraphs with loops (relations) on n nodes and with an even number of arcs.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A055974 Number of unlabeled digraphs with loops (relations) on n nodes and with an odd number of arcs.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A343592 Number of symmetry types of digraphs with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A383617 Triangle read by rows: T(n,k) is the number of binary relations on a set of n objects, k of which are picked out, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A029849 Number of nonisomorphic and nonantiisomorphic relations.

Views

Author

Keywords

Crossrefs

Formula

A046858 Irregular triangle read by rows: T(n,k) = number of directed graphs-with-loops with n nodes and k arcs (n >= 0, 0 <= k <= n^2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A054920 Number of connected unlabeled reflexive relations with n nodes such that complement is also connected.

Views

Author

Keywords