Sequence A001181, Baxter Permutations
How many different ways are there to divide a rectangle into N smaller rectangles, ignoring differences in relative sizes, but counting rotations and reflections as distinct?
The answer is the number of Baxter permutations, given by Sloane's sequence A001181. The sequence starts: 0, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, ...
N=1:
1
N=2:
|
1 2 |
|
2 1 |
N=3:
|
1 2 3 |
|
1 3 2 |
2 1 3 |
2 3 1 |
3 1 2 |
|
3 2 1 |
N=4:
|
1 2 3 4 | |||||||||
|
1 2 4 3 |
1 3 2 4 |
1 3 4 2 |
1 4 2 3 |
2 1 3 4 |
2 3 1 4 |
2 3 4 1 |
3 1 2 4 |
3 4 1 2 |
4 1 2 3 |
|
1 4 3 2 |
2 1 4 3 |
2 4 3 1 |
3 2 1 4 |
3 2 4 1 |
3 4 2 1 |
4 2 3 1 |
4 2 1 3 |
4 3 1 2 |
4 1 3 2 |
|
4 3 2 1 |
The figures for N=5 are here.
The Meta-Narayana Triangle
In the above illustration, the figures have been grouped in the following way: 1, 1+1, 1+4+1, 1+10+10+1, and in the N=5 figures below, the groups are 1+20+50+20+1. These groups are distinguished by the "width" and "height" of the figures in each group.
This division of the Nth Baxter number into N parts reflects the following triangle of numbers, which is like Pascal's triangle and the Narayana triangle, and is constructed in a similar way:
1 sum: 1 1 1 sum: 2 1 4 1 sum: 6 1 10 10 1 sum: 22 1 20 50 20 1 sum: 92 1 35 175 175 35 1 sum: 422 1 56 490 980 490 56 1 sum: 2074 1 84 1176 4116 4116 1176 84 1 sum: 10754This triangle is "listed" in the OEIS as sequence A56939; see that entry for some formulas and references.
The rows of this triangle can be computed from the tetrahedral numbers using a method similar to that for the Pascal and Narayana triangles. For example, consider row 7: it is computed from the first 6 tetrahedral numbers, which are: 1, 4, 10, 20, 35, 56. Using these numbers in the successive fractions, and starting with 1, we get:
first term: 1
1×56/1 = 56
56×35/4 = 490
490×20/10 = 980
980×10/20 = 490
490×4/35 = 56
56×1/56 = 1
A similar procedure with the triangular numbers generates the Narayana triangle, and the same procedure with the natural numbers generates the Pascal triangle.
"Missing" Patterns
I said above that we were counting all rotations and reflections as distinct. However, if you look carefully through the N=5 patterns below, there seem to be some missing patterns. For example, the following 4 are in the list:
|
2 1 5 3 4 |
2 3 1 5 4 |
4 3 5 1 2 |
4 5 1 3 2 |
but the other 4 versions of this pattern (rotated 90 degrees from these 4) are missing. Where are the missing patterns?
The "missing" patterns are in the table but in different, topologically equivalent forms. For example, the "missing" pattern that comes from rotating pattern 4 5 1 3 2 90o to the right is shown here. It can be transformed into the pattern 2 1 4 5 3 by moving one of the horizontal partitions down and the other one up:
|
"missing" |
→
|
|
→
|
2 1 4 5 3 |
Transformations of this type are not considered significant when deciding whether two patterns are equivalent.
Some other sequences are discussed here.
References
[1] Bo Yao, Hongyu Chen, Chung-Kuan Cheng, and Ronald Graham, Revisiting Floorplan Representations, Proceedings of the 2001 international symposium on Physical design ISBN 1-58113-347-2
[2] Eyal Ackerman, Gill Barequet, and Ron Y. Pinter, On the number of rectangular partitions, Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (2004)
[3] Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4, page 31. PDF online
Appendix: Rectangle Partitions for N=5
|
1 2 3 4 5 | |||||||||
|
1 2 3 5 4 |
1 2 4 3 5 |
1 2 4 5 3 |
1 2 5 3 4 |
1 3 2 4 5 |
1 3 4 2 5 |
1 3 4 5 2 |
1 4 2 3 5 |
1 4 5 2 3 |
1 5 2 3 4 |
|
2 1 3 4 5 |
2 3 1 4 5 |
2 3 4 1 5 |
2 3 4 5 1 |
3 1 2 4 5 |
3 4 1 2 5 |
3 4 5 1 2 |
4 1 2 3 5 |
4 5 1 2 3 |
5 1 2 3 4 |
|
1 2 5 4 3 |
1 3 2 5 4 |
1 3 5 4 2 |
1 4 3 2 5 |
1 4 3 5 2 |
1 4 5 3 2 |
1 5 3 4 2 |
1 5 3 2 4 |
1 5 4 2 3 |
1 5 2 4 3 |
|
2 1 3 5 4 |
2 1 4 3 5 |
2 1 4 5 3 |
2 1 5 3 4 |
2 3 1 5 4 |
2 3 5 4 1 |
2 4 3 1 5 |
2 4 3 5 1 |
2 4 5 3 1 |
2 5 3 4 1 |
|
2 5 3 1 4 |
3 2 1 4 5 |
3 2 4 1 5 |
3 2 4 5 1 |
3 1 2 5 4 |
3 4 2 1 5 |
3 4 2 5 1 |
3 4 5 2 1 |
3 5 4 1 2 |
4 2 3 1 5 |
|
4 2 3 5 1 |
4 2 1 3 5 |
4 3 1 2 5 |
4 3 5 1 2 |
4 1 3 2 5 |
4 1 3 5 2 |
4 5 1 3 2 |
4 5 2 1 3 |
4 5 2 3 1 |
4 5 3 1 2 |
|
5 2 3 4 1 |
5 2 3 1 4 |
5 2 1 3 4 |
5 3 4 1 2 |
5 3 1 2 4 |
5 4 1 2 3 |
5 1 3 4 2 |
5 1 3 2 4 |
5 1 4 2 3 |
5 1 2 4 3 |
|
1 5 4 3 2 |
2 1 5 4 3 |
2 5 4 3 1 |
3 2 1 5 4 |
3 2 5 4 1 |
3 5 4 2 1 |
4 3 2 1 5 |
4 3 2 5 1 |
4 3 5 2 1 |
4 5 3 2 1 |
|
5 2 4 3 1 |
5 2 1 4 3 |
5 3 2 4 1 |
5 3 2 1 4 |
5 3 4 2 1 |
5 4 3 1 2 |
5 4 2 3 1 |
5 4 2 1 3 |
5 4 1 3 2 |
5 1 4 3 2 |
|
5 4 3 2 1 |
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Oct 02.
s.30