# [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.)