|
%I #47 Feb 23 2020 18:52:17
%S 1,1,3,4,16,36,64,218,752,1104,2112,4096,9608,45960,90416,178944,
%T 266496,528384,1048576,1540944,9133760,22692704,45277312,30194176,
%U 90196736,180011008,135032832,269500416,537919488,1073741824
%N Irregular triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with color scheme given by the partitions of n in canonical ordering.
%C Colors are not interchangeable. Adjacent nodes may have the same color.
%C A partition [b_1, ..., b_m] with b_i > 0 and Sum_{i=1..m} b_i = n corresponds to a color scheme on n nodes having m colors. To find out which digraphs are equivalent with respect to a color scheme, consider the automorphism group on the partition. This group is the m-fold product of the symmetric groups on the b_i nodes, and therefore contains Product_{i=1..m} b_i! elements (i.e. the permutations).
%C Calculate the number of equivalence classes by determining the cycle index of the group induced by the automorphism group in the set of the edges [(i,j)|i,j in [1..n]; i != j] and set, with Pólya, the variable values to 2.
%C The left column of the triangle gives the number of unlabeled digraphs, while the right flank of the triangle gives the number of labeled digraphs.
%C Canonical ordering is also known as graded reverse lexicographic ordering, see A080577, A063008, or link below. Partitions here have the property b_i >= b_j for i < j.
%D N. G. de Bruijn, Pólyas Abzähl-Theorie: Muster für Graphen und chemische Verbindungen, Selecta Mathematica III, Springer-Verlag (1971), 1-55.
%H Peter Dolland, <a href="/A328773/b328773.txt">Table of n, a(n) for n = 0..138</a> (rows 0..10)
%H OEIS Wiki, <a href="http://oeis.org/wiki/Orderings of partitions#A_comparison">Orderings of partitions (a comparison)</a>.
%F T(n, 1) = A000273(n).
%F T(n, A000041(n)) = A053763(n) = 2^(n^2 - n).
%F T(n, A000041(n)-1) = 2^(n^2 - 3*n - 1) * (2^(2*n) + 8) for n > 1.
%e The sequence begins:
%e 1;
%e 1;
%e 3, 4;
%e 16, 36, 64;
%e 218, 752, 1104, 2112, 4096;
%e 9608, 45960, 90416, 178944, 266496, 528384, 1048576;
%e ...
%e For n = 3, the three partitions of n are [3], [2, 1] and [1, 1, 1]. T(n,1) = 16 gives the number of colored digraphs with all nodes having the same color; T(n, 2) = 36 gives the number of colored digraphs with two nodes having the first color and one node having the second color; T(n, 3) gives the number of colored digraphs with each node having its own color.
%e For n = 5, k = 4 the required partition is [3,1,1]. T(5,4) = 178944 is then the number of colored digraphs with 5 nodes, where 3 nodes have the first color and the other two nodes each has its own color.
%o (PARI) \\ here C(p) computes sequence value for given partition.
%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, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
%o C(p)={((i,v)->if(i>#p, 2^edges(v), my(s=0); forpart(q=p[i], s+=permcount(q)*self()(i+1, concat(v,Vec(q)))); s/p[i]!))(1, [])}
%o Row(n)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)], ,4))}
%o { for(n=0, 6, print(Row(n))) } \\ _Andrew Howroyd_, Nov 02 2019
%Y Cf. A000041 equals the row length, A080577 lists the partitions in the used order, A063008 instantiates the index sequences encoding the partitions. A000273 and A053763 represent the flanks of the triangle.
%K nonn,tabf
%O 0,3
%A _Peter Dolland_, Oct 27 2019
|
