Puzzles & Games Network problem

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

  1. amantine

    amantine Premium Member

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

    kiwirobin Premium Member

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

    amantine Premium Member

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

    Gopher Member

    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]
     
  5. kiwirobin

    kiwirobin Premium Member

    Hence the =1 in the network formula?