A357757 We draw n non-crossing straight line segments inside an n X n square between 2*n grid points on its perimeter, allowing no more similar connections between the remaining perimeter grid points. a(n) is the count of distinct possibilities for each n without duplicates by rotation or reflection.

1, 2, 18, 86

Offset

1,2

Comments

The square figures with the line segments running inside them can be imagined as modernist windows of a house with irregularly divided glass panes. Any one of them, whether rotated in the vertical plane or viewed from the "inside" or the "outside", counts as distinct if no other window looks the same with similar transpositions.

Observation: Taken any one configuration that makes up such a window, if we count the grid divisions along and around the window frame between the consecutive 2*n end points of the n line segments (or window bars), it will add up to 4*n. More important than this obvious fact, is that this is essentially partitioning 4*n into 2*n parts such that these parts may range from 1 through n+2. Latter is the upper limit because any greater value would indicate missing extra window bars at the corners, which is not permitted by the definition. Therefore it appears that solving the enumerating problem of this sequence may involve reduced partitions under the given constraints. In the Example section, this count is shown for 3 X 3 windows.

For every n, an easily sorted special table may help eliminating duplicates in manual or programmed enumeration alike, inasmuch it lists for each candidate configuration the number of line segments having specific "steepness". This ratio value describes the proportions of the grid-aligned bounding box of a line segment, not necessarily taking into account its orientation. For example, this value for a line segment running along a grid line between two opposite sides will have the form of 0/n, while for another one, the smallest possible that is just cutting a corner, will be shown as 1/1, and so on. Below is shown such a table for n=3, with the 18 distinct configurations counted. In this comparison table, some of the windows have identical set of window bars, yet the relative positions of these are different, as can be seen on the linked illustration.

.

| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

____|_______________________________________________________________________

|

0/3 | 1

1/1 | 2 2 2 1 2 1 1 1 1 1 1

1/2 | 1 2 2 2 1 2 1 1 1 2 1

1/3 | 1 1 3 1 1 1 1 1 2 2 1

2/2 | 1

2/3 | 1 1 1 1

3/3 | 1 1

.

Links

Table of n, a(n) for n=1..4.

Tamas Sandor Nagy, Illustration for a(1) to a(3)

Example

a(1) = 1 because only one non-crossing straight line segment can be drawn inside a 1 X 1 square between its perimeter grid points, namely, one of its diagonals. Rotating or reflecting this figure will not result in another distinct shape to be counted.
a(2) = 2 because there are two distinct configurations. In the first one, two parallel line segments run from opposite corners to the midpoints on the sides of the 2 X 2 square. In the second, one line segment connects two neighboring side midpoints, while the other runs from a corner to a third midpoint, not crossing the former. In both cases, no further line segment may fit without crossing the existing ones.
Count of grid divisions around the 18 distinct 3 X 3 window frames between the window bars:
.
  2, 1, 5, 1, 2, 1
  2, 2, 4, 1, 2, 1
  2, 3, 3, 1, 2, 1
  1, 3, 2, 2, 3, 1
  2, 1, 3, 2, 1, 3
  2, 3, 1, 2, 3, 1
  4, 1, 1, 4, 1, 1
  2, 1, 2, 3, 1, 3
  3, 1, 2, 3, 1, 2
  3, 2, 3, 1, 2, 1
  4, 1, 3, 1, 2, 1
  2, 1, 1, 4, 2, 2
  3, 1, 1, 4, 2, 1
  2, 1, 1, 4, 1, 3
  3, 1, 1, 4, 1, 2
  1, 1, 2, 1, 3, 4
  3, 1, 3, 3, 1, 1
  2, 1, 3, 3, 1, 2
.

Crossrefs

Sequence in context: A343514 A360301 A070171 * A172529 A201236 A206623

Adjacent sequences: A357754 A357755 A357756 * A357758 A357759 A357760

Keyword

nonn,more

Author

Tamas Sandor Nagy, Nov 26 2022

Status

approved