[seqfan] Re: A graph counting problem

[Maximilian Hasler]

On Tue, Jan 5, 2010 at 6:55 PM, Max Alekseyev <maxale at gmail.com> wrote:
>
> 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?

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

> > (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?

n=3 is the sum of the labels - this gives the following possibilities :

* 1 node with label "3"
 (no other nodes and thus no edges)

* 2 nodes, one labelled "2" and one labelled "1"
 They *can* be connected or not connected :
 either
   (2)    (1)
(disconnected graph: 2 nodes, no edge)
 or
   (2)---(1)
(connected graph : one edge with endpoints 1 and 2)

* 3 nodes, all labelled "1" ; they cannot be connected to each other
by the additional requirement (same labels cannot be connected).


connected graphs for n=4 and n=5 :

a( n=4 ) = 3 :
{ 1-2-1  ;  1-3  ;  4 }

a( n=5 ) = 6 :
{ 5 ;  4-1 ; 3-3 ; 1-3-1 ; 2-1-2 ; 1-2=11 }
where "1-2=11" stands for a 2 connected to each of three 1's (not
possible to draw this in one dimension...)

* if one node = 5, that's all.
* if one node = 4, it must be connected to a node 1, and that's all.
* if one node = 3, it can be connected to a 2 (and nothing else) or it
can be connected to a 1; that 1 cannot be connected to anything (since
only 1 is left) so the 3 must be connected to another 1.
* if the largest node = 2, then it cannot be connected to 3,4,5 and it
cannot be connected to another 2, so it must be connected to a 1. That
1 could be connected to an other 2 (and nothing else can be in the
graph), but to nothing else.
It remains the possibility that the "initial" 2 is connected to 2
other "1"s (=> the 1-2=11).

Maximilian