[seqfan] Re: A graph counting problem
Max Alekseyev
maxale at gmail.com
Wed Jan 6 02:17:00 CET 2010
On Tue, Jan 5, 2010 at 7:30 PM, Maximilian Hasler
<maximilian.hasler at gmail.com> wrote:
>> > Consider graphs where each node is labeled with a positive integer;
>> > labels may be used more than once. Two nodes with the same label may
>> > not be connected by an edge. Graphs are distinguished up to
>> > permutations of nodes with the same label. How many graphs are there
>> > with labels totaling n?
>>
>> I don't quite understand this definition.
>> What is the number of nodes in the graph? Are permutations of labels
>> are taken into account?
>
> The number is "arbitrary" but constrained by the fact that each node
> carries a positive integer number, and the sum of all these numbers
> equals n
Thanks to you and Franklin for clarification.
What was confusing to me is the term "totaling". I did not catch that
it refers to summing up the labels.
Now, the sequence is clear to me and I can even offer first 30 terms:
1, 2, 4, 8, 16, 35, 77, 179, 440, 1160, 3264, 9950, 33206, 121943,
494011, 2235399, 11391306, 65287199, 422908306, 3130775625,
26490210964, 255257056748, 2825013955541, 36147331371446,
531237157370531, 8965348473026888, 175629366371057918,
3992619892094868709, 104457049859201232450, 3162313206707299567108,
And here is my PARI/GP script that computes this sequence (with rather
complicated embedded explicit formula):
{ part2freq(p) = local(r);
r = vector(sum(i=1,#p,p[i]));
for(j=1,#p, r[p[j]]++);
r
}
{ a(n) = local(s,p,k,P,r);
s=0;
p=partitions(n);
for(i=1,#p,
k=part2freq(p[i]);
k = select(x->(x>0),k);
P = vector(#k,j,partitions(k[j]));
for(j=1,#k, for(t=1,#P[j], P[j][t] = part2freq(P[j][t]) ));
forvec(v = vector(#k,j,[1,#P[j]]), \\ fix cycle structures
r = 1 / prod(j=1,#k, prod(t=1,#P[j][v[j]], t^P[j][v[j]][t] *
P[j][v[j]][t]! ));
for(j=1,#k, for(t=j+1,#k,
r *= prod(ii=1,k[j], prod(jj=1,k[t], 2^(gcd(ii,jj) *
P[j][v[j]][ii] * P[t][v[t]][jj]) ));
));
s += r;
);
);
s
}
Regards,
Max
More information about the SeqFan
mailing list