4
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ squeeze mapping? $\endgroup$
    – Will Jagy
    Dec 6, 2011 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, 2011 at 1:06
  • 1
    $\begingroup$ @Will: Horizontal or vertical scaling, e.g., $x \mapsto \frac{1}{2} x$. $\endgroup$
    – Joseph O'Rourke
    Dec 6, 2011 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, 2011 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, 2011 at 1:44

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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, 2011 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, 2011 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, 2011 at 9:11
  • $\begingroup$ Erm, I thought we did not allow self-crossings... $\endgroup$
    – fedja
    Dec 6, 2011 at 14:13
  • $\begingroup$ Neither my example nor my combinatoric proof nor Gerry's example includes any self-crossings. $\endgroup$
    – Will Sawin
    Dec 6, 2011 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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