# Puzzles & Games Network problem

Discussion in 'Puzzles & Games' started by amantine, Feb 17, 2005.

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...

One new observation I made is that the number of connections is the same in every pattern.

4. ### GopherMember

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]