A062764 Number of partitions of the unit square into 2^n dyadic rectangles, each of area 2^{-n}.

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

Harry J. Smith, Table of n, a(n) for n = 0..11

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).

S. Janson, Random Dyadic Tilings

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

Adjacent sequences: A062761 A062762 A062763 * A062765 A062766 A062767

Keyword

nonn

Author

Joel Spencer (spencer(AT)cs.nyu.edu), Jul 16 2001

Extensions

More terms from Vladeta Jovovic, Jul 18 2001

Status

approved