A110837 Number of ways to fold a strip of n stamps taking account of order and direction of folds.

1, 2, 8, 36, 176, 864, 4304, 21448, 107168, 535488, 2677088, 13383712, 66916832, 334575552, 1672869152, 8364302864, 41821471424, 209107142784, 1045535499584, 5227676426944, 26138381063744, 130691899964544, 653459494468544, 3267297445575296, 16336487201109056

Offset: 1

Author

Henry Bottomley, Sep 16 2005

Keywords

• nonn

Examples

			a(3) = 8 since with an initial strip of three stamps there are two possible folding positions for the initial fold, each of which could be folded up or down, so there are four possible initial folds, each leaving one possible folding position which can be folded up or down, making eight possible folding patterns.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..1000
• Index entries for sequences obtained by enumerating foldings

Crossrefs

Cf. A001011, A075496.

Programs

Maple

a:= proc(n) option remember; `if`(n=1, 1,
      2*add(max(a(k), a(n-k)), k=1..n-1))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Jan 08 2023

Mathematica

a[n_] := a[n] = If[n==1, 1, 2*Sum[Max[a[k], a[n-k]], {k, 1, n-1}]];
Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Jan 10 2023, after Alois P. Heinz *)

Formula

a(n) = 2 * Sum_{0

a(n) ~ 0.054816154756...*5^n.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.