A373692 Table of the number of ways T(m,n) to partition a 2m X 2n grid into Cartesian products of size 2 X 2, read by ascending antidiagonals.

1, 3, 3, 15, 45, 15, 105, 1575, 1575, 105, 945, 99225, 510525, 99225, 945, 10395, 9823275, 376473825, 376473825, 9823275, 10395, 135135, 1404728325, 533407191975, 4202869719825, 533407191975, 1404728325, 135135, 2027025, 273922023375, 1302400497234375, 115509334438258425, 115509334438258425, 1302400497234375, 273922023375, 2027025

Offset

1,2

Comments

This is a special case of the problem to partition a Cartesian product P X Q into squares P_i X Q_i, i.e. |P_i| = |Q_i|. In our case all subsets have size 2. Using the terminology of A160911 we deal with partitions of type (2m X 2n: 2,2,2,...).

From Markus Sigg, Jul 25-26 2024: (Start)

T(m,n) is a multiple of (2m-1)(2n-1) as there are that many ways to place a Cartesian product with one point in the top left of the grid, and the resulting configurations are equivalent.

For m,n > 1, starting with the Cartesian product {1,2m} X {1,2n} and evaluating the options for adding a Cartesian product with one point in (1,2) shows that T(m,n) is a multiple of (2m-1)(2n-1)*lcm(2m-3,2n-3). (End)

Links

Markus Sigg, Table of n, a(n) for n = 1..59

Rainer Rosenthal, Colored illustration showing that T(2,2) = 45.

Rainer Rosenthal, Expanded Example.

Markus Sigg, C program for computing the very first terms of the sequence.

Markus Sigg, C program for computing more terms of the sequence, namely T(ROWS/2,COLS/2) where ROWS and COLS are defined in the first program lines.

Example

Table T(m,n) begins:
.
     n       1             2                 3              4             5
  m \ ---------------------------------------------------------------------
  1 |        1             3                15            105           945
  2 |        3            45              1575          99225       9823275
  3 |       15          1575            510525      376473825  533407191975
  4 |      105         99225         376473825  4202869719825
  5 |      945       9823275      533407191975  115509334438258425
  6 |    10395    1404728325  1302400497234375  6907197292027901339625
  7 |   135135  273922023375
  8 |  2027025
.
These are the T(1,2) = 3 possible partitions:	
.
    |A A B B|   |A B A B|   |A B B A|
    |A A B B|   |A B A B|   |A B B A|
    _________________________________
       #1          #2          #3
.
For T(2,2) = 45 consider these special partitions:
.
   |A A B B|   |A A B B|   |A A B B|
   |A A B B|   |A A B B|   |A A C C|
   |C C D D|   |C D C D|   |D D B B|
   |C C D D|   |C D C D|   |D D C C|
  ___________________________________
     Base1       Base2       Base3
.
Any partition is equivalent to exactly one of these partitions, i.e. it differs only by the order of the rows and columns. The number of equivalent partitions is respectively 9, 18, 18. Thus we have T(2,2) = 9 + 18 + 18 = 45.
See the picture and the expanded example in the link section.
.
Some other known terms: T(5,5) = 84250218148544569727025, T(6,4) = 6907197292027901339625, T(7,4) = 814287280679532017261528625, T(8,4) = 173936355367823940296258779550625, T(9,4) = 62626268302216078023651174787170095625, T(10,4) = 35784629301848063975515694953866493243805625.

Prog

(C) // See Markus Sigg link.

Crossrefs

Cf. A001147 (column 1), A079484 (column 2 - conjectured), A160911.

Sequence in context: A165553 A056314 A171379 * A078631 A352802 A160639

Adjacent sequences: A373689 A373690 A373691 * A373693 A373694 A373695

Keyword

nonn,tabl,hard

Author

Rainer Rosenthal and Markus Sigg, Jun 13 2024

Extensions

a(24) and beyond from Markus Sigg, Jul 18 2024

Status

approved