mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-11-24, 02:50   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

248710 Posts
Default approximation of possible self-avoiding walks

I've been recently about self-avoiding walks recently, and I've noticed that the number of possible paths increases rapidly as the size of the lattice increases. However, it also seems very hard to calculate the exact number of possible paths.

Does anyone know any formulas for approximating the number of self-avoiding walks in an arbitrary lattice? For example, how many possible paths should I expect for a three-dimensional 20 x 20 x 20 lattice, or a five-dimensional 4 x 4 x 4 x 4 x 4 lattice?
ixfd64 is offline   Reply With Quote
Old 2007-11-26, 05:57   #2
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

2×7×13 Posts
Default

I guess we should try some original research. I'm assuming that you mean I need to set a bit everytime I enter a square/cube/whatever, and then randomly chose a nonconflicting path until I am surrounded. You can represent this as an array of bits, and run a large amount of trial runs. Unfortunately, this is a 'hard' problem... It is likely in other words intractable. You'de be trying to create a function that approximates the statistical result.

There is also a subtle relationship between what you're describing and (at least):
Nonrepeating n-digit sequences like 000100111 where if you look at any three digits in a row, you'll only see that combination once. These are called "De Bruijn" sequences. There are inperfect sequences that are longer then 9 bits that will repeat some 2-bit combinations and others that don't contain all 2-bit combinations. These could be considered an analogy of uncrossed and multicrossed 'squares' in the first paragraph. If you write a program to evaluate one, you should be able to use that strategy to attack the other.
Euler circuits
Hamiltonian paths
"Snake-in-the-Box" problems are like the first paragraph but deal with the edges connecting the corners of a box.

You'll notice that most of them are linking to each other on Wikipedia. The common theme is paths - rather it's a geometric or digital path. Reading about these subjects should be quite interesting or absolutely mind numbing.

http://en.wikipedia.org/wiki/De_Bruijn_sequence
http://en.wikipedia.org/wiki/Eulerian_path
http://en.wikipedia.org/wiki/Hamiltonian_path
Especially read: http://en.wikipedia.org/wiki/Snake-in-the-box
Running those names through any search engine should be enlightning.

Last fiddled with by nibble4bits on 2007-11-26 at 05:58
nibble4bits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Easier pi(x) approximation mathPuzzles Math 8 2017-05-04 10:58

All times are UTC. The time now is 19:53.


Fri Dec 2 19:53:15 UTC 2022 up 106 days, 17:21, 0 users, load averages: 1.37, 1.42, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔