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
27 comments:
:D
that 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.
http://www.artificiallife.bitsystemsph.com
Zeppe, I got the formula from p.214 of Spectra of Graphs: Theory and Applications (scanned copy)
Number 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"
Great Article
IEEE final year projects on machine learning
JavaScript Training in Chennai
Final Year Project Centers in Chennai
JavaScript Training in Chennai
Cool 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.
The Article looks very good.
This is a wonderful article.
Thanks again for a great article!
This sort of clever work and reporting!
I needed to see and read this post today and smile.
I hope they find each other. simply gorgeous work!
Great post.
Good work! Glad to have found your page!! This is such great work
This is such a great resource that you are providing and you give it away for free.
This is a very interesting post. Thank you for posting a lot of interesting posts.
Thanks for taking the time to discuss this.
what an interesting blog you have here bro!
An incredible article dude.
I read this post your post is so nice and very informative post thanks for sharing this post.
Amazing! This blog looks exactly like my old one!
Very value able post, I read the whole story when I start reading it.
Nice Blog. Thanks for sharing with us. Such amazing information.
I appreciate your post thanks for sharing the information.
Very Interesting and amazing how your post is! It Is Useful and helpful for me That I like it very much.
This is a really good.
Post a Comment