Suppose you have a chain of length n. How many walks of length k are there on the chain? For instance, for a chain of length 5, there are 5 paths of length 0 (start at each vertex and don't go anywhere), 8 of length 1 (traverse each edge either left-right or right-left), 14 of length 2 (8 walks that change direction once, 6 walks that don't change direction) etc.
Curiously enough, there's an explicit formula for this
For example, to find the number of walks of length 2 in a chain of length 5, plug n=5, k=2 into formula above, and get
Which is 14.
Notebook, web version
:D
ReplyDeletethat formula is amazing! Could you put a reference to it, please? I'm really curious to see the demonstration :)
this is a very interesting blog. I will surely go back again.
ReplyDeletehttp://www.artificiallife.bitsystemsph.com
Zeppe, I got the formula from p.214 of Spectra of Graphs: Theory and Applications (scanned copy)
ReplyDeleteNumber of walks of length n is the sum of entries of A^k where A is the adjacency matrix of the graph. From that you could guess that the formula would have something to do with eigenvalues of the adjacency matrix.
For instance, the number of self-returning walks of length k is the trace of A^k, which is e1^k+e2^k+.... where e's are eigenvalues of the adjacency matrix of the graph
I'm still working out the mechanics of finding eigenvalues for matrices like this, but they seem to come up pretty often in physics. For instance, see page 5 of http://arxiv.org/abs/cond-mat/0001408, it gives expression for eigenvalues of the adjacency matrix of a loop of length n. Using expression from eq.24 there you would get a simple formula for number of self-returning walks of length k in a loop
"Number of walks of length n is the sum of entries of A^k", should be "Number of walks of length k is the sum of entries of A^k"
ReplyDeleteGreat Article
ReplyDeleteIEEE final year projects on machine learning
JavaScript Training in Chennai
Final Year Project Centers in Chennai
JavaScript Training in Chennai
This comment has been removed by the author.
ReplyDeleteCool formula: Remini app brings new life to your cherished old photos, turning faded memories into vibrant masterpieces. With its free and paid versions, Remini app makes photo restoration and artistic transformation accessible to all, backed by a user-friendly interface that's a breeze to navigate. you can easily download Remini app from gbnine.
ReplyDelete