[seqfan] A graph counting problem

franktaw at netscape.net franktaw at netscape.net
Wed Dec 30 16:20:51 CET 2009


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?

Hand calculating, I get starting at n = 0,

1,1,2,4,8,16,35,77,179;

the number of connected graphs of this sort, starting at n = 1,

1,1,2,3,6,12,28,65.

These numbers are consistent with each other (the first is the Euler 
transform of the second), but I do not have a high degree of confidence 
in the last couple in each list.

The first sequence is not in the database.  The second matches 
<http://www.research.att.com/~njas/sequences/A073431>;  a sequence 
concerning gatomorphisms.

So, are these numbers correct?  Can someone compute more, and verify or 
refute the match to A073431?  If it does match, what does it mean?

-----
(For example, the 4 graphs for n=3 are:

(3), (2-1), (2 1), and (1 1 1); the first 2 of these are connected.)

Franklin T. Adams-Watters




More information about the SeqFan mailing list