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,2

Links

Seiichi Manyama, Table of n, a(n) for n = 1..1000

Index entries for sequences obtained by enumerating foldings

Formula

a(n) = 2 * Sum_{0<k<n} max{a(k), a(n-k)} starting with a(1)=1.

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

Example

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.

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

Crossrefs

Cf. A001011, A075496.

Sequence in context: A109980 A186338 A190862 * A372088 A166229 A109318

Adjacent sequences: A110834 A110835 A110836 * A110838 A110839 A110840

Keyword

nonn

Author

Henry Bottomley, Sep 16 2005

Status

approved