A093934 Number of equivalence classes of unlabeled tournaments with n signed nodes.

1, 2, 4, 12, 48, 296, 3040, 54256, 1716608, 97213472, 9937755904, 1849103423168, 631027551238656, 397616229914793600, 465313769910614218240, 1016485858155549165160192, 4163516302794478683289989120, 32101177200132015985353543496192, 467507173926886632279989196725442560

Offset

0,2

Comments

Similar to unlabeled tournaments (A000568), with the additional feature that each node carries either a plus sign or a minus sign.

Equivalence is defined with respect to the action of S_n on the nodes (and the induced action on the edges).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms n = 0..30 from N. J. A. Sloane)

Formula

a(n) = Sum_{j} (1/(Product (r^(j_r) (j_r)!))) * 2^{t_j},

where j runs through all partitions of n into odd parts, say with j_1 parts of size 1, j_3 parts of size 3, etc.,

and t_j = (1/2)*[ Sum_{r=1..n, s=1..n} j_r j_s gcd(r,s) + Sum_{r} j_r ].

Maple

with(combinat); with(numtheory);
for n from 1 to 30 do
p:=partition(n); s:=0:
for k from 1 to nops(p) do
# get next partition of n
ex:=1:
# discard if there is an even part
for i from 1 to nops(p[k]) do if p[k][i] mod 2=0 then ex:=0:break:fi: od:
# analyze an odd partition
if ex=1 then
# convert partition to list of sizes of parts
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:
# get number of parts
nump := add(a(i), i=1..n);
# get multiplicity
c:=1: for i from 1 to n do c:=c*a(i)!*i^a(i): od:
# get exponent t(j)
tj:=0;
for i from 1 to n do for j from 1 to n do
if a(i)>0 and a(j)>0 then tj:=tj+a(i)*a(j)*gcd(i, j); fi;
od: od:
s:=s + (1/c)*2^((tj+nump)/2);
fi:
od;
A[n]:=s;
od:
[seq(A[n], n=1..30)];

Mathematica

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], {i, 1, Length[v]}];
oddp[v_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];
a[n_] := Module[{s = 0}, Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]* 2^Length[p]], {p, IntegerPartitions[n]}]; s/n!];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

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, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
a(n) = {my(s=0); forpart(p=n, if(oddp(p), s+=permcount(p)*2^(#p+edges(p)))); s/n!} \\ Andrew Howroyd, Feb 29 2020

Crossrefs

Cf. A000568.

Sequence in context: A263867 A326863 A082480 * A109458 A030963 A030879

Adjacent sequences: A093931 A093932 A093933 * A093935 A093936 A093937

Keyword

nonn

Author

Nadia Heninger and N. J. A. Sloane, Jul 21 2009

Status

approved