OFFSET
0,2
COMMENTS
Number of orbits under the action of permutation group S(n) on n X n {0,1} matrices. 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. - Andrew Howroyd, Oct 22 2017
REFERENCES
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 76 (2.2.30)
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.
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).
LINKS
Jean-François Alcover, Table of n, a(n) for n = 0..50 (a(0)-a(37) from Charles R. Greathouse IV)
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.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
A. Casagrande, C. Piazza, and A. Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Preprint 2015.
Matthew Dabkowski, N. Fan, and R. Breiger, Exploratory blockmodeling for one-mode, unsigned, deterministic networks using integer programming and structural equivalence, Social Networks, Volume 47, October 2016, Pages 93-106.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Thomas M. A. Fink, Emmanuel Barillot, and Sebastian E. Ahnert, Dynamics of network motifs, 2006.
Frank Harary, Edgar M. Palmer, Robert W. Robinson, and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Sergiy Kozerenko, On the abstract properties of Markov graphs for maps on trees, Mathematical Bilten 41:2 (2017), pp. 5-21.
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]
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Samuel Reid, On Generalizing a Temporal Formalism for Game Theory to the Asymptotic Combinatorics of S5 Modal Frames, arXiv preprint arXiv:1305.0064 [math.LO], 2013.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
L. Travis, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.
FORMULA
a(n) = sum {1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...] / (1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 2^sum {i, j>=1} (gcd(i, j)*s_i*s_j). - Christian G. Bower, Jan 05 2004
a(n) ~ 2^(n^2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016
EXAMPLE
From Gus Wiseman, Jun 17 2019: (Start)
Non-isomorphic representatives of the a(2) = 10 relations:
{}
{1->1}
{1->2}
{1->1, 1->2}
{1->1, 2->1}
{1->1, 2->2}
{1->2, 2->1}
{1->1, 1->2, 2->1}
{1->1, 1->2, 2->2}
{1->1, 1->2, 2->1, 2->2}
(End)
MATHEMATICA
Join[{1, 2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n], Ordered], Permutations[Range[n^2-n+1, n^2]], 2], s] /. Table[s[i]->2, {i, 1, n^2-n}], {n, 2, 7}]] (* Geoffrey Critzer, Nov 02 2011 *)
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_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)
dinorm[m_]:=If[m=={}, {}, If[Union@@m!=Range[Max@@Flatten[m]], dinorm[m/.Apply[Rule, Table[{(Union@@m)[[i]], i}, {i, Length[Union@@m]}], {1}]], First[Sort[dinorm[m, 1]]]]];
dinorm[m_, aft_]:=If[Length[Union@@m]<=aft, {m}, With[{mx=Table[Count[m, i, {2}], {i, Select[Union@@m, #1>=aft&]}]}, Union@@(dinorm[#1, aft+1]&)/@Union[Table[Map[Sort, m/.{par+aft-1->aft, aft->par+aft-1}, {0}], {par, First/@Position[mx, Max[mx]]}]]]];
Table[Length[Union[dinorm/@Subsets[Tuples[Range[n], 2]]]], {n, 0, 3}] (* Gus Wiseman, Jun 17 2019 *)
PROG
(GAP) NSeq := function ( n ) return Sum(List(ConjugacyClasses(SymmetricGroup(n)), c -> (2^Length(Orbits(Group(Representative(c)), CartesianProduct([1..n], [1..n]), OnTuples))) * Size(c)))/Factorial(n); end; # Dan Hoey, May 04 2001
(PARI)
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, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017
(Python)
from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000595(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in product(p.keys(), repeat=2)), prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n))) # Chai Wah Wu, Jul 02 2024
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Feb 07 2000
Still more terms from Dan Hoey, May 04 2001
STATUS
approved