cp's OEIS Frontend

A328773 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.

%I A328773 #47 Feb 23 2020 18:52:17
%S A328773 1,1,3,4,16,36,64,218,752,1104,2112,4096,9608,45960,90416,178944,
%T A328773 266496,528384,1048576,1540944,9133760,22692704,45277312,30194176,
%U A328773 90196736,180011008,135032832,269500416,537919488,1073741824
%N A328773 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 A328773 Colors are not interchangeable. Adjacent nodes may have the same color.
%C A328773 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 A328773 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 A328773 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 A328773 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 A328773 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 A328773 Peter Dolland, <a href="/A328773/b328773.txt">Table of n, a(n) for n = 0..138</a> (rows 0..10)
%H A328773 OEIS Wiki, <a href="http://oeis.org/wiki/Orderings of partitions#A_comparison">Orderings of partitions (a comparison)</a>.
%F A328773 T(n, 1) = A000273(n).
%F A328773 T(n, A000041(n)) = A053763(n) = 2^(n^2 - n).
%F A328773 T(n, A000041(n)-1) = 2^(n^2 - 3*n - 1) * (2^(2*n) + 8) for n > 1.
%e A328773 The sequence begins:
%e A328773       1;
%e A328773       1;
%e A328773       3,       4;
%e A328773      16,      36,       64;
%e A328773     218,     752,     1104,     2112,     4096;
%e A328773    9608,   45960,    90416,   178944,   266496,   528384,   1048576;
%e A328773    ...
%e A328773 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 A328773 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 A328773 (PARI) \\ here C(p) computes sequence value for given partition.
%o A328773 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 A328773 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 A328773 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 A328773 Row(n)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)], ,4))}
%o A328773 { for(n=0, 6, print(Row(n))) } \\ _Andrew Howroyd_, Nov 02 2019
%Y A328773 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 A328773 nonn,tabf
%O A328773 0,3
%A A328773 _Peter Dolland_, Oct 27 2019