[seqfan] Re: A graph counting problem
Maximilian Hasler
maximilian.hasler at gmail.com
Wed Jan 6 01:30:48 CET 2010
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
More information about the SeqFan
mailing list