My math teacher asked me if I had any ideas to solve this problem, which he couldn't solve either. The problem Imagine a telephone network. There is a central point to which all phones must be connected. However, it is also to connect a point via another point. All points must be somehow connected to the central point and there must be no redundant connections. The number n is the number of points. Example for n = 2. The central C can be connected to the two points, called 1 and 2, in the following three manners: C-1-2 (1 connected to C and 2 connected through 1) C-2-1 (2 connected to C and 1 connected through 2) C-12 (1 and 2 connected directly to C) We already know that the numbers of unique patterns to connect n points is equal to (n+1)^(n-1). Let's call this formula P(n). This gives for different n: n -> number of patterns 1 -> 1 2 -> 3 3 -> 16 4 -> 125 The problem is how to prove this formula? I've checked the cases 1, 2 and 3 by hand and they are true. I doubt the mathematics book my teacher has is wrong, but the proof is not in there. I hope you guys can solve the puzzle of proving this formula. I don't know the answer myself. The differents methods I tried I tried using induction to try and show that P(n+1) = P(n) + extra patterns added by new point However, it is very difficult to calculate the new patterns that can occur when you add a new point. Maybe binomial expansion gives a clue, but that didn't help me much either. The second method I tried is finding a way to simply calculated the number of patterns from scratch. This is terribly difficult. I first tried calculating the total number of patterns possible and then you still have to remove duplicates. However, even calculating the total number is very difficult. I thought of seeing the tree as a linear line with a certain amount of points at each distance from the central point C. When the number of points at a distance q is m(q), the total amount of patterns with possible with those numbers of points at different distances from the line is: product (from x=1 to x=qmax) m(x-1)^m(x) However, I don't know how to calculate all the different possibilies for the different numbers of points at different distances from the central points. There are 2^n possible ways, but there is no easy to combine these two formula into one formula. Even if you were able to do this, you would have to remove duplicate patterns. I don't know how do this either.

Mmmmmmmmmmm a difficuclt problem as the possible connections obviously increase by magnitude. Especialy if for example C-1-2-C are also options: 1 and 2 connected directly to C and to eachother. I did find this in some old notes, I can't find a direct relationship but maybe of use to you. Network formula V + R - L = 1 V = vertices = points to connect L = lines = the connections R = regions = closed areas created by connections ie: C-C, C-1-C...

Ideas... Consider representing a graph as an adjacency matrix where 1 means connected and 0 means unconnected. For example, n = 3 A 1 2 3 1 0 1 1 2 1 0 0 3 1 0 0 Represents... 1 ---- 2 | | 3 Sum of all degrees = 4 Sum of lines = 2 Sometimes the 1 and 0s are also used to indicate direction. A 1 2 3 1 0 1 0 2 1 0 0 3 0 1 0 Represents... 1 ------ 2 <------ 3 A 1 2 3 1 1 0 0 2 0 1 0 3 0 0 1 Represents Points 1 2 3 pointing at themselves and not connected to each other. How many graphs can be represented by a nxn matrix? What do we subtract to get to the number of unique paths that you gave in your formula? [Edited on 2-17-2005 by Gopher]