login
A062764
Number of partitions of the unit square into 2^n dyadic rectangles, each of area 2^{-n}.
1
1, 2, 7, 82, 11047, 198860242, 64197955389505447, 6678916619587233636236512800877522, 72230102121526702892392003475289782931885785764402133686496289624487
OFFSET
0,2
COMMENTS
A dyadic rectangle is of the form [a2^{-b},(a+1)2^{-b}]x [c2^{-d},(c+1)2^{-d}] with a,b,c,d nonnegative integers.
The number of dyadic equipartitions of the unit cube (or higher dimensional cube) seems much more difficult.
REFERENCES
S. Janson, D. Randall and J. H. Spencer, Random dyadic tilings of the Unit Square, Tech Report 2001:18, Uppsala (Sweden)
LINKS
Cannon, Sarah; Levin, David A.; Stauffer, Alexandre Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings. Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017. LIPIcs - Leibniz Int. Proc. Inform. 81, Article 34, 21 p. (2017).
J. C. Lagarias, J. H. Spencer and J. P. Vinson, Counting dyadic equipartitions of the unit square, Discrete Math. 257 (2002), 481-499.
FORMULA
a(n) = 2a(n-1)^2 - a(n-2)^4 for n >= 2.
EXAMPLE
a(2)=7; the 7 partitions are as follows:
(#1) 4 vertical strips;
(#2) 4 horizontal strips;
(#3) 4 squares;
(#4) 2 horizontal strips on top, two squares on bottom;
(#5) like #4, but with top/bottom reversed;
(#6) two vertical strips on left, two squares on right;
(#7) like #6, but with left/right reversed.
MAPLE
a:=proc(n) option remember: if n=0 then 1 elif n=1 then 2 else 2*procname(n-1)^2-procname(n-2)^4; fi; end; seq(a(n), n=0..8); # Muniru A Asiru, Jun 29 2018
PROG
(PARI) { for (n=0, 11, if (n, a=2*a1^2 - a2^4; a2=a1; a1=a, a=a1=1; a2=0); write("b062764.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 10 2009
(GAP) a:=[1, 2];; for n in [3..9] do a[n]:=2*a[n-1]^2-a[n-2]^4; od; a; # Muniru A Asiru, Jun 29 2018
CROSSREFS
Sequence in context: A208806 A319144 A111822 * A163855 A268299 A041291
KEYWORD
nonn
AUTHOR
Joel Spencer (spencer(AT)cs.nyu.edu), Jul 16 2001
EXTENSIONS
More terms from Vladeta Jovovic, Jul 18 2001
STATUS
approved