[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