login
Number of equivalence classes of unlabeled tournaments with n signed nodes.
2

%I #26 Jul 02 2024 14:50:56

%S 1,2,4,12,48,296,3040,54256,1716608,97213472,9937755904,1849103423168,

%T 631027551238656,397616229914793600,465313769910614218240,

%U 1016485858155549165160192,4163516302794478683289989120,32101177200132015985353543496192,467507173926886632279989196725442560

%N Number of equivalence classes of unlabeled tournaments with n signed nodes.

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

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

%H Andrew Howroyd, <a href="/A093934/b093934.txt">Table of n, a(n) for n = 0..50</a> (terms n = 0..30 from N. J. A. Sloane)

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

%F 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.,

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

%p with(combinat); with(numtheory);

%p for n from 1 to 30 do

%p p:=partition(n); s:=0:

%p for k from 1 to nops(p) do

%p # get next partition of n

%p ex:=1:

%p # discard if there is an even part

%p for i from 1 to nops(p[k]) do if p[k][i] mod 2=0 then ex:=0:break:fi: od:

%p # analyze an odd partition

%p if ex=1 then

%p # convert partition to list of sizes of parts

%p q:=convert(p[k],multiset);

%p for i from 1 to n do a(i):=0: od:

%p for i from 1 to nops(q) do a(q[i][1]):=q[i][2]: od:

%p # get number of parts

%p nump := add(a(i),i=1..n);

%p # get multiplicity

%p c:=1: for i from 1 to n do c:=c*a(i)!*i^a(i): od:

%p # get exponent t(j)

%p tj:=0;

%p for i from 1 to n do for j from 1 to n do

%p if a(i)>0 and a(j)>0 then tj:=tj+a(i)*a(j)*gcd(i,j); fi;

%p od: od:

%p s:=s + (1/c)*2^((tj+nump)/2);

%p fi:

%p od;

%p A[n]:=s;

%p od:

%p [seq(A[n],n=1..30)];

%t 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];

%t 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]}];

%t oddp[v_] := Module[{i}, For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1];

%t a[n_] := Module[{s = 0}, Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]* 2^Length[p]], {p, IntegerPartitions[n]}]; s/n!];

%t a /@ Range[0, 18] (* _Jean-François Alcover_, Jan 07 2021, after _Andrew Howroyd_ *)

%o (PARI)

%o 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}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}

%o oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}

%o 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

%o (Python)

%o from itertools import product

%o from math import prod, factorial, gcd

%o from fractions import Fraction

%o from sympy.utilities.iterables import partitions

%o def A093934(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r,s) for r,s in product(p.keys(),repeat=2))+sum(p.values())>>1),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n) if all(q&1 for q in p))) # _Chai Wah Wu_, Jul 01 2024

%Y Cf. A000568.

%K nonn

%O 0,2

%A _Nadia Heninger_ and _N. J. A. Sloane_, Jul 21 2009