This is likely a very easy counting question inspired by some elementary geometry:

Consider a simple rectilinear polygon embedded in a plane in such a way that each of its edges is parallel to one of the coordinate axis. Two such polygons are considered distinct if they are not related by some composition of translation, scalar multiplication and squeeze mapping.

I would like to asses the number of such distinct simple rectilinear polygons which have $2n$ horizontal (equivalently vertical) edges for any chosen $n\in\mathbb N$.

Thank you.

  • 1
    $\begingroup$ squeeze mapping? $\endgroup$ – Will Jagy Dec 6 '11 at 0:28
  • $\begingroup$ The number of vertical edges doesn't necessarily equal the number of horizontal edges unless you make some assumption about the shape of the polygon. (E.g.a polygon consisting of seven unit squares arranged in a C-shape.) $\endgroup$ – Hugh Thomas Dec 6 '11 at 1:06
  • 1
    $\begingroup$ @Will: Horizontal or vertical scaling, e.g., $x \mapsto \frac{1}{2} x$. $\endgroup$ – Joseph O'Rourke Dec 6 '11 at 1:07
  • $\begingroup$ @Hugh: I think you are counting edges differently? Any C-shape is composed of 4 horizontal and 4 vertical edges, where each edge is a segment perhaps of different length. $\endgroup$ – Joseph O'Rourke Dec 6 '11 at 1:11
  • $\begingroup$ Counting left right turn sequences might be a good start. Gerhard "Ask Me About System Design" Paseman, 2011.12.05 $\endgroup$ – Gerhard Paseman Dec 6 '11 at 1:44

The number of right turns must always be 4 more than the number of left turns. This is the only constraint on turn sequences. Proof: Take the minimal impossible sequence satisfying this property. It must contain RR, so it is either RRRR or contains RRL. Delete the RL, find an example, and then add a small "tab" off the corner. If it's RRRR, draw a rectangle.

The number of words like that should be a fairly standard combinatorics problem. I don't know the exact formula.

Already with 6 turns, though, the number of distinct polygons is infinite. In assembling an L-shape, I have 6 degrees of freedom counting translation, and you only have a 4-dimensional space of symmetries.

  • $\begingroup$ Or to be more explicit, if we are interpreting the problem correctly, then the L-shapes consisting of an $n\times1$ rectangle upright with a $2\times1$ base all have 6 sides and are inequivalent for distinct $n$. $\endgroup$ – Gerry Myerson Dec 6 '11 at 5:05
  • 1
    $\begingroup$ If I'm reading the OP correctly, the condition was that there are $2n$ horizontal and $2n$ vertical segments, so the L-shapes are not valid examples. Fortunately, this isn't really an issue, as we can just use a larger staircase polygon. $\endgroup$ – Michael Biro Dec 6 '11 at 5:18
  • $\begingroup$ In my innitial question I indeed only considered boundaries composed of 2n vertical and 2n horizontal line segments. But that restriction steams only from the geometric background in which the question originaly arised and there is no particular reason why L-shapes and simmilar objects couldn't be considered as well. Anyway thank you for the answer! $\endgroup$ – HeWhoHungers Dec 6 '11 at 9:11
  • $\begingroup$ Erm, I thought we did not allow self-crossings... $\endgroup$ – fedja Dec 6 '11 at 14:13
  • $\begingroup$ Neither my example nor my combinatoric proof nor Gerry's example includes any self-crossings. $\endgroup$ – Will Sawin Dec 6 '11 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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