Graph Problem: (n+1) Knots & Edges - How Many Possible Graphs?

[pixel01]

Hello all,

I have got this graph problem. There are (n+1) knots which are numbered as A1, A2...An,An+1. We can connect those knots with lines (edges). The question is : How many possible graphs are there totally?
Notes: A graph can be a tree of any kinds, but muts not contain a loop.

Thanks

 

[EnumaElish]

Number of r-combinations out of n elements, without repetition?

 

[pixel01]

Number of r-combinations out of n elements, without repetition?

Thanks for your ansser.
The number of combinations out of n elements,without repetition is just double the number of graphs of the same type. For n relatively large, we can have graphs without tree, and graphs with tree structure as well, so the final answer must be higher than just the number of combinations out of n elements...

 

[EnumaElish]

http://en.wikipedia.org/wiki/Graph_theory
http://en.wikipedia.org/wiki/Graphical_enumeration
http://en.wikipedia.org/wiki/Pólya_enumeration_theorem (although, "This article or section is in need of attention from an expert on the subject.")

 

[pixel01]

Thanks Enuma. I have done it!
Great chance to revise the graph theory.