Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Definition: An edge-component is a sequence of some consecutive collinear-segments.

Consider an $n \times n$ grid-like arrangement of $2n$ lines. Is there any idea about the number of simple cycles with exactly $2n$ edge-components such that each line in the grid contains exactly one edge-component of the cycle? In other words, the cycles should traverse all the lines. A simple cycle is a cycle which passes through the nodes exactly once.

In the picture you can see a $7\times7$ grid-like arrangement and a desired 14-cycle. enter image description here

Any hint or observation is helpful.

share|improve this question
    
How about non-simple? If you allow intersections, it might be easier...and you'll also need to know how many 'units' the path traverses. –  Mitch Apr 26 '11 at 21:00
    
Then the problem is rather easy, and I know the solution and the exact number. Removing the intersections is worthy. –  Losy Apr 27 '11 at 4:47
add comment

2 Answers

The structures you want to count are constrained self-avoiding lattice polygons. This paper describes some exactly solved models; it is from this book, which is the standard reference on these types of problems.

Normally lattice polygons are counted based on their perimeter or area, but your constraint naturally suggests counting these $2n$-gons by the number of vertices/edges as you propose.

If the tours needn’t be self-avoiding, then there are $\frac{n!(n-1)!}{2}$ of them; permute the rows and columns, and divide by $2n$ because neither the start-point nor the orientation is relevant.

The first six terms ($n=2\;\:..\: 7$) are $1, 4, 26, 240, 2918, 44424$. Here are the $26$ octagons:

octagons

This sequence is now A203935 in OEIS; the superseeker failed to return any useful information.

share|improve this answer
add comment

What is your question? As there are $n$ vertical lines and $n$ horizontal lines, the circuit will certainly have at least $2n$ segments. Proving that you can always do it with $2n$ segments is not difficult: just imagine a staircase. Are you looking for how many different circuits are possible? Are rotation and reflection considered?

share|improve this answer
    
Absolutely! How many different circuits of length $2n$ are in the grid. This makes the problem rather hard. But because of the well shaped appearance of the grid, I want to see if any one has any suggestion for counting these circuits or an upper/lower bound for them. Although $(n-1)!$ is known as a lower bound. –  Losy Apr 27 '11 at 4:43
    
My first approach would be to calculate the small values and feed the list to oeis.org. n=1 yields 1 (the square), n=2 gives 4 (cut a corner out of the square). If you get 3 and 4 that may be enough. –  Ross Millikan Apr 27 '11 at 4:55
    
No dear. for $n=2$ you have only one circuit, why 4? $n=2$ the grid has 4 intersection points and 4 bounded segments, and then it has just one cycle. –  Losy Apr 27 '11 at 5:10
    
Exactly. For $2n=8$ there are 26 different cycles and for $2n=10$ there are 240 different cycles. And... –  Losy Apr 27 '11 at 5:29
    
@Losy: I misread your $n$ and you are right. For $n=2$ there is only one cycle. For $n=3$ there are four (cut one corner out of the square.) This is a correction to a comment that should be above yours. I put 4,26,240 into OEIS and only found two, neither of which seems right. I would write a program to get the next two or three, then see if it fits a polynomial. –  Ross Millikan Apr 27 '11 at 5:40
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.