|
%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
| 