Timeline for Distinct closed walks with $2n$ steps in the $n$-dimensional hypercube
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 4 at 14:01 | vote | accept | m3tro | ||
| Sep 4 at 13:14 | comment | added | David E Speyer | Glad to see it worked out! If you don't want to quotient by reflections, you can just use the rotations terms in the Burnside computation, and divide by $2n$ (order of the rotation group) instead of $4n$. | |
| Sep 4 at 12:30 | comment | added | m3tro | @PeterTaylor thanks, but see my first comment to David above: "The reason I care about necklaces and not bracelets is because I don't want to quotient by reversal of the paths, paths are oriented". I see now that David has assumed quotient by reversal in his answer, but he could easily modify it to account for both possibilities. | |
| Sep 4 at 10:48 | comment | added | Peter Taylor | @m3tro, A054499. | |
| Sep 4 at 10:19 | comment | added | m3tro | Another neat result of the chord diagram approach is that one can immediately see which paths are "non-returning" (like path number 2 for 2D and paths number 3 and 4 in 3D in the image above) by checking whether the chord diagram is connected. The number of connected diagrams for different n is given in OEIS A018225 and, starting from n=2, is 1, 2, 6, 31... | |
| Sep 4 at 10:15 | comment | added | m3tro | I was about to post this as an answer right now, when I came across your answer. You did get to a solution of the problem (can you confirm that your approach would give A007769?) so I am happy accept your answer if you updated it with the additional information. | |
| Sep 4 at 10:07 | comment | added | m3tro | Hi David, thanks for the awesome answer. There has been in the meantime substantial discussion about this problem on the /r/math subreddit, see reddit.com/r/math/comments/1f7ui06/… I did figure out the connection to chord diagrams and realized that what I am looking for is OEIS A007769 "Number of chord diagrams with n chords; number of pairings on a necklace". Starting from n=2, we get 2, 5, 18, 105... The reason I care about necklaces and not bracelets is because I don't want to quotient by reversal of the paths, paths are oriented. | |
| Sep 4 at 9:32 | history | edited | David E Speyer | CC BY-SA 4.0 |
added 32 characters in body
|
| Sep 4 at 9:26 | history | edited | David E Speyer | CC BY-SA 4.0 |
added 350 characters in body
|
| Sep 4 at 9:21 | history | answered | David E Speyer | CC BY-SA 4.0 |