A189243 - OEIS

%I #40 May 01 2013 21:06:47

%S 1,2,6,21,88,390,1914

%N Number of ways to dissect a nonsquare rectangle into n rectangles with equal area.

%C Dissections which differ by rotations or reflections are counted as distinct.

%C Rectangles may have different shapes.

%C a(1) to a(5) are the same (but not a(6)) as:

%C   A033540 a(n+1) = n*(a(n)+1), n >= 1, a(1) = 1.

%C If the dissections with a cross (where four squares share a vertex) were counted twice then a(1) to a(5) would be the same as the 'guillotine partitions' counted by A006318. - _Geoffrey H. Morley_, Dec 31 2012

%H Geoffrey H. Morley, <a href="/A189243/a189243_1.pdf">Illustration of terms up to a(5)</a>

%H N. J. A. Sloane, <a href="/A189243/a189243.jpg">Illustration of the term a(4) = 21</a>

%H "056254628", <a href="http://bbs.emath.ac.cn/thread-2916-1-4.html">A Chinese web page containing the problem and illustrating the initial terms</a>

%F For n > 4, a(n) = b(n)+

%F +-------+   +-------+   +-------+   +---+---+   +---+---+

%F |       |   |       |   |       |   |   |   |   |   |   |

%F +-------+   +-------+   +-------+   +---+---+   +---+---+

%F |[a(n-1)|   |       |   |       |   |[a(n-2)|   |       |

%F |-a(n-2)|*4+| a(n-2)|*2+| a(n-3)|*4+|-a(n-3)|*4+| a(n-4)|*2

%F |-a(n-3)|   +-------+   +---+---+   |-a(n-4)|   +---+---+

%F |]      |   |       |   |   |   |   |]      |   |   |   |

%F +-------+   +-------+   +---+---+   +-------+   +---+---+

%F = b(n)+4*a(n-1)+2*a(n-2)-4*a(n-3)-2*a(n-4) where b(n) is the number of tilings in which no side of the rectangle comprises the side of a tile or the equal sides of two congruent tiles. For example, b(5) = 2. '*2' counts, say, rotation clockwise by 90 degrees (and rescaling the aspect ratio), while '*4' counts all rotations. - _Geoffrey H. Morley_, Dec 07 2012

%e There are 6 ways to form a rectangle from 3 rectangles with same area:

%e +-----+ +-+-+-+ +-----+ +--+--+ +-+---+ +---+-+

%e |     | | | | | |     | |  |  | | |   | |   | |

%e +-----+ | | | | +--+--+ |  |  | | |   | |   | |

%e |     | | | | | |  |  | |  |  | | +---+ +---+ |

%e +-----+ | | | | |  |  | +--+--+ | |   | |   | |

%e |     | | | | | |  |  | |     | | |   | |   | |

%e +-----+ +-+-+-+ +--+--+ +-----+ +-+---+ +---+-+

%e So a(3)=6.

%e From _Geoffrey H. Morley_, Dec 03 2012: (Start)

%e b(n) in the given formula is the sum of the appropriate tilings from certain 'frames'. A number that appears in a subrectangle in a frame is the number of rectangles into which the subrectangle is to be divided. Tilings are also counted that are from a reflection and/or half-turn of the frame.

%e For n = 6 there are 3(X2) frames:

%e +---+-+-+  +-+-----+  +-+-----+

%e |   | | |  | |     |  | |     |

%e |   | | |  | +---+-+  | |  2  |

%e +-+-+ | |  | |   | |  | |     |

%e | | | | |  | +---+ |  | +---+-+

%e | | +-+-+  | |   | |  | |   | |

%e | | |   |  +-+---+ |  +-+---+ |

%e | | |   |  |     | |  |     | |

%e +-+-+---+  +-----+-+  +-----+-+

%e   2 ways     2 ways     8 ways

%e The only other frames which yield desired tilings are obtained by rotating each frame above by 90 degrees and scaling it to fit a rectangle with the inverse aspect ratio.

%e So b(6) = 2(2+2+8) = 24, and a(6) = b(6)+4*a(5)+2*a(4)-4*a(3)-2*a(2) = 24+4*88+2*21-4*6-2*2 = 390.

%e For n = 7 we can use 7(X2) frames:

%e +---+--+

%e |   |  |

%e |   |  |

%e | 4 |3 |

%e |   |  |

%e |   |  |

%e |   |  |

%e +---+--+

%e 63 ways [of creating tilings counted by b(7)]

%e +---+--+  +-+----+  +--+---+  +-----++  +--+---+  +----+-+

%e |   |  |  | |    |  |  |   |  ++----+|  |  |   |  ++-+-+ |

%e |   +-++  | +---++  |2 | 2 |  ||    ||  |  +-+-+  || | | |

%e | 3 | ||  |2|   ||  |  +--++  ||    ||  |2 | | |  || | | |

%e |   | ||  | | 2 ||  |  |  ||  || 3  ||  |  | | |  || +-+-+

%e |   | ||  | |   ||  +--+--+|  ||    ||  +--+-+2|  || |   |

%e +---+-+|  +-+---+|  |     ||  |+----++  |    | |  |+-+---+

%e +-----++  +-----++  +-----++  ++-----+  +----+-+  ++-----+

%e 24 ways   16 ways   12 ways   10 ways    8 ways    4 ways

%e As for n = 6, these are only half the frames and tilings.

%e So b(7) = 2(63+24+16+12+10+8+4) = 274, and a(7) = b(7)+4*a(6)+2*a(5)-4*a(4)-2*a(3) = 274+4*390+2*88-4*21-2*6 = 1914.

%e (End)

%Y See the analogous sequences A219861 and A108066 where we count dissections up to symmetry of nonsquare rectangles and squares respectively. - _Geoffrey H. Morley_, Dec 03 2012

%K nonn,nice,more

%O 1,2

%A _Yi Yang_, Apr 19 2011

%E Edited by _N. J. A. Sloane_, Apr 21 2011

%E a(7) added by _Geoffrey H. Morley_, Dec 03 2012

%E a(7) corrected by _Geoffrey H. Morley_, Dec 05 2012