|
|
A000273
|
|
Number of unlabeled simple digraphs with n nodes.
(Formerly M3032 N1229)
|
|
50
|
|
|
1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848, 13027956824399552, 341260431952972580352, 32522909385055886111197440, 11366745430825400574433894004224, 14669085692712929869037096075316220928, 70315656615234999521385506555979904091217920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
CRC Handbook of Combinatorial Designs, 1996, p. 651.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 225.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, Table 5.1.2 and p. 241, Table A4.
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
|
Fatemeh Arbabjolfaei and Young-Han Kim, Fundamentals of Index Coding, Foundations and Trends in Communications and Information Theory (2018) Vol. 14, Issue 3-4.
|
|
FORMULA
|
|
|
MAPLE
|
with(combinat):with(numtheory):
for n from 0 to 20 do p:=partition(n):
s:=0:for k from 1 to nops(p) do
q:=convert(p[k], multiset):
for i from 1 to n do a(i):=0:od:for i from 1 to nops(q) do a(q[i][1]):=q[i][2]:od:
c:=1:ord:=1:for i from 1 to n do c:=c*a(i)!*i^a(i): if a(i)<>0 then ord:=lcm(ord, i):fi:od:
g:=0:for d from 1 to ord do if ord mod d=0 then g1:=0:for del from 1 to d do if del<=n and d mod del=0 then g1:=g1+del*a(del):fi:od:g:=g+phi(ord/d)*g1*(g1-1):fi:od:
s:=s+2^(g/ord)/c:
od:
print(n, s):
od:
# second Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
end:
|
|
MATHEMATICA
|
Table[CycleIndex[PairGroup[SymmetricGroup[n], Ordered], t]/.Table[t[i]->1+x^i, {i, 1, n^2}]/.{x->1}, {n, 1, 7}] (* or *)
Table[GraphPolynomial[n, t, Directed]/.{t->1}, {n, 1, 20}]
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-1];
a[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
|
|
PROG
|
(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]-1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017
(Python)
from math import gcd, factorial
from sympy.utilities.iterables import partitions
def permcount(v):
m, s, k = 1, 0, 0
for i, t in enumerate(v):
k = k+1 if i > 0 and t == v[i-1] else 1; m *= t*k; s += t
return factorial(s)//m
def edges(v): return sum(sum(2*gcd(v[i], v[j]) for j in range(i)) for i in range(1, len(v))) + sum(vi-1 for vi in v)
def a(n):
s = 0
for p in partitions(n):
pvec = []
for i in sorted(p): pvec.extend([i]*p[i])
s += permcount(pvec)*2**edges(pvec)
return s//factorial(n)
(Python)
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000273(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s)<<1 for r, s in combinations(p.keys(), 2))+sum(r*(q*r-1) for q, r in p.items()), prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 05 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,core,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|