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.
ReplyDeleteThe Article looks very good.
ReplyDeleteThis is a wonderful article.
ReplyDeleteThanks again for a great article!
ReplyDeleteThis sort of clever work and reporting!
ReplyDeleteI needed to see and read this post today and smile.
ReplyDeleteI hope they find each other. simply gorgeous work!
ReplyDeleteGreat post.
ReplyDeleteGood work! Glad to have found your page!! This is such great work
ReplyDeleteThis is such a great resource that you are providing and you give it away for free.
ReplyDeleteThis is a very interesting post. Thank you for posting a lot of interesting posts.
ReplyDeleteThanks for taking the time to discuss this.
ReplyDeletewhat an interesting blog you have here bro!
ReplyDeleteAn incredible article dude.
ReplyDeleteI read this post your post is so nice and very informative post thanks for sharing this post.
ReplyDeleteAmazing! This blog looks exactly like my old one!
ReplyDeleteVery value able post, I read the whole story when I start reading it.
ReplyDeleteNice Blog. Thanks for sharing with us. Such amazing information.
ReplyDeleteI appreciate your post thanks for sharing the information.
ReplyDeleteVery Interesting and amazing how your post is! It Is Useful and helpful for me That I like it very much.
ReplyDeleteThis is a really good.
ReplyDelete