41
\$\begingroup\$

I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021.

Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] team golf would excel at.

As I found out the hard way with the help of user202729, the definition of A049021 is... slippery. Instead, this challenge will have you compute a similar sequence.

(If, separate from this challenge, you're interested in computing more terms of A049021, I encourage it!)

Definition

This challenge will have you counting topologically distinct ways of partitioning a square into \$n\$ rectangles.

Two partitions are called topologically distinct if there's no homeomorphism \$A \rightarrow B\$ with the additional property that the corners of \$A\$'s square map surjectively to the corners of \$B\$'s square. The less fancy way of saying this is that if partitions \$A\$ and \$B\$ are topologically equivalent, there is a map from \$A \rightarrow B\$ and a map from \$B \rightarrow A\$ such that all nearby points stay nearby, and every corner of \$A\$ is sent to a distinct corner of \$B\$.

Examples of homeomorphisms are rotating the square, flipping the square, and "slightly" moving the boundaries of the rectangles.

When \$n = 4\$ there are seven topologically distinct partitions:

The seven topologically distinct ways of dissecting a square into 4 rectangles.

As user202729 pointed out, sometimes these equivalences are somewhat surprising; in particular, the following partitions are equivalent by homeomorphism: An example of two partitions that are homeomorphism.

Challenge

This challenge will have you write a program that computes as many terms of this new sequence as possible. In case of a close call, I will run submissions on my machine, a 2017 MacBook Pro with 8 GB of RAM.

(Be aware that some of these square partitions are more complicated then just putting two smaller partitions side-by-side.)

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ According to this paper (arxiv.org/abs/1105.3093), When n=4, there are 24 different ways to partition a square into 4 sub-rectangles. Is there a specific way you derived 7? Sorry if i am getting the question wrong. Edit: Also found a question on this matter on the Math Stack exchange math.stackexchange.com/questions/1116 \$\endgroup\$
    – user100752
    Mar 1, 2021 at 20:47
  • 11
    \$\begingroup\$ I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021 This must be the first time a challenge asks to write useful code \$\endgroup\$
    – Luis Mendo
    Mar 1, 2021 at 23:29
  • 2
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – Wheat Wizard ♦
    Mar 2, 2021 at 15:39
  • 1
    \$\begingroup\$ This configuration can't be generated by the algorithm used by the OEIS sequence. \$\newcommand{\x}[1]{\color{#1}{\blacksquare}} \newcommand{\r}{\x{red}} \newcommand{\g}{\x{green}} \newcommand{\b}{\x{blue}} \newcommand{\y}{\x{yellow}} \newcommand{\c}{\x{cyan}} \newcommand{\m}{\x{magenta}} \begin{matrix} \r\b\b\b\r\r\b\b\b\b\b\\ \r\g\y\y\r\r\g\g\g\g\y\\ \r\g\y\y\m\m\m\m\m\m\y\\ \r\g\y\y\c\c\c\r\r\b\b\\ \m\m\y\y\c\c\c\r\r\b\b\\ \m\m\y\y\c\c\c\r\r\g\y\\ \r\b\b\b\b\b\b\r\r\g\y\\ \r\g\g\g\g\y\y\r\r\g\y\\ \m\m\m\m\m\y\y\m\m\m\y\\ \end{matrix}\$ \$\endgroup\$
    – DELETE_ME
    Mar 3, 2021 at 7:02
  • 2
    \$\begingroup\$ As far as I can tell, this notion of homeomorphic dissections is equivalent to the adjacency graphs of the rectangular dissections being isomorphic. If that's correct, can we define the problem that way, to reduce confusion? If not, could we have an example where the two definitions differ? \$\endgroup\$
    – isaacg
    Mar 3, 2021 at 20:47

0

Reset to default

Your Answer

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