[seqfan] Re: A graph counting problem

[Max Alekseyev]

On Wed, Dec 30, 2009 at 10:20 AM,  <franktaw at netscape.net> 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?

It looks like you are talking about some kind of k-partite graphs
where nodes in each part are labeled identically (hence, k is simply
the number of distinct labels).
My best guess was that you meant k-partite graphs on n nodes where
nodes are indistinguishable within their parts and parts are
indistinguishable from each other.
Then for n=3 we would have the following eight graphs:
1) all three nodes in the same part (here k=1)
2) two nodes are in one part, one in another, no edges (here k=2)
3) two nodes are in one part, one in another and there is one edge
between the parts (k=2)
4) two nodes are in one part, one in another and there are two edges
between the parts (k=2)
5) each of the nodes forms its own part and there are no edges (k=3)
6) each of the nodes forms its own part and there is one edge (k=3)
7) each of the nodes forms its own part and there are two edges (k=3)
8) each of the nodes forms its own part and there are three edges (k=3)

> -----
> (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.)

I don't understand this example - could you please elaborate a bit more?

Max