A096222 Number of different rectangles when a piece of paper is folded n times in alternate directions.

1, 3, 9, 30, 100, 360, 1296, 4896, 18496, 71808, 278784, 1098240, 4326400, 17172480, 68161536, 271589376, 1082146816, 4320165888, 17247043584, 68920934400, 275415040000, 1101122764800, 4402342526976, 17605073043456, 70403108110336

Offset

0,2

Comments

Similar to A000537, which counts all possible rectangles in an n X n array of squares. In this sequence we count the rectangles in an a X b array of squares, where a=2^floor(n/2) and b=2^ceiling(n/2). Note that a(n) is the product of two triangular numbers.

Links

Table of n, a(n) for n=0..24.

Formula

a(n) = a b (a+1) (b+1)/4, where a=2^floor(n/2) and b=2^ceiling(n/2).

a(n) (mod 10^k) is cyclic. For (mod 10) the cycle is 0, 0, 0, 6, 6, 6, 8, 4. - Robert G. Wilson v, Jul 31 2004

Conjectures from Colin Barker, Feb 04 2020: (Start)

G.f.: (1 - 3*x - 9*x^2 + 24*x^3) / ((1 - 2*x)*(1 - 4*x)*(1 - 8*x^2)).

a(n) = 6*a(n-1) - 48*a(n-3) + 64*a(n-4) for n>3.

(End)

Example

a(1) = 3: fold a 1 X 2 rectangle down the middle; there are 3 rectangles, the one on the left, the one on the right and the one we started with. a(2) = 9 : fold a 2 X 2 rectangle along the X and Y axes; there 4 rectangles of size 1 X 1, 4 of size 1 X 2 or 2 X 1 and 1 of size 2 X 2.

Mathematica

Table[a=2^Floor[n/2]; b=2^Ceiling[n/2]; Sum[i*j, {i, a}, {j, b}], {n, 20}]

Crossrefs

Cf. A000537.

Sequence in context: A275690 A089931 A148946 * A148947 A090573 A228339

Adjacent sequences: A096219 A096220 A096221 * A096223 A096224 A096225

Keyword

nonn

Author

Bill Liebeskind (billlieb(AT)hotmail.com), Jul 29 2004

Extensions

Edited by T. D. Noe, Jul 30 2004

More terms from Robert G. Wilson v, Jul 31 2004

Status

approved