Results 1 to 3 of 3

Math Help - Number of paths

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Number of paths



    a) Write down the adjacency matrix, F.

    This part I can do. (Using the convention that loops count as 1 edge)

    F = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}

    The ordering of the vertices are v_1, v_2, v_3, v_4 for both rows and columns.

    b) Explain why the number of paths of length 2^n which begin and end at v_1 is always one more than the number of walks of length 2^n which begin at v_1 and end at v_2.

    I'm stuck on this part.

    This is what I have done so far:

    So I have computed F^2 = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix}<br />

    And I have also computed F^4 = \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix} \begin{bmatrix} 3 & 2 & 2 & 2 \\ 2 & 3 & 2 & 2 \\ 2 & 2 & 3 & 2 \\ 2 & 2 & 2 & 3 \end{bmatrix} = \begin{bmatrix} 21 & 20 & 20 & 20 \\ 20 & 21 & 20 & 20 \\ 20 & 20 & 21 & 20 \\ 20 & 20 & 20 & 21 \end{bmatrix}<br />

    Now we can see the that entry in (v_1, v_1) is always 1 more than the entry in (v_1, v_2)

    But how do I generalise this for all F^{2^n}?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Well, I can think of two possible approaches to this problem. One is to diagonalize F. I think you might be able to do that, since it is symmetric. That would enable you to produce a closed-form expression for the required power of F.

    Another approach is to reason about the problem and come up with an argument (I don't know what that would be, but it seems to me that you might be able to come up with one) showing the desired result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    I don't know what role the 2^n part plays... but this might work for the path length being any specific number :

    We consider a walk from v1 to v2. The stage at which the walk reaches v2 for the final time and loops there before terminating, we take the walk to v1 instead and loop there. This way we can construct a bijection between walks from v1 to v1 and those from v1 to v2, leaving out the case when the whole path is a succession of loops on v1 itself. Hence the result.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of Paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2010, 06:07 AM
  2. Finding the number of paths...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 18th 2010, 05:02 PM
  3. Number of Paths
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 29th 2008, 10:37 AM
  4. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 07:54 AM
  5. Integration along Paths
    Posted in the Calculus Forum
    Replies: 3
    Last Post: June 6th 2007, 04:35 PM

Search Tags


/mathhelpforum @mathhelpforum