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.