9
$\begingroup$

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.

  • 0
    $T$hen the problem is rather easy, and I know the solution and the exact number. Removing the intersections is worthy.2011-04-27

2 Answers 2

1

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.

0

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?

  • 0
    @Ross: True. Also, I had never thought about eliminating decreasing polynomials...2011-05-26