A110837 - OEIS

%I #23 Jan 10 2023 16:12:37

%S 1,2,8,36,176,864,4304,21448,107168,535488,2677088,13383712,66916832,

%T 334575552,1672869152,8364302864,41821471424,209107142784,

%U 1045535499584,5227676426944,26138381063744,130691899964544,653459494468544,3267297445575296,16336487201109056

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

%H Seiichi Manyama, <a href="/A110837/b110837.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Fo#fold">Index entries for sequences obtained by enumerating foldings</a>

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

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

%e 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.

%p a:= proc(n) option remember; `if`(n=1, 1,

%p       2*add(max(a(k), a(n-k)), k=1..n-1))

%p     end:

%p seq(a(n), n=1..25);  # _Alois P. Heinz_, Jan 08 2023

%t a[n_] := a[n] = If[n==1, 1, 2*Sum[Max[a[k], a[n-k]], {k, 1, n-1}]];

%t Table[a[n], {n, 1, 25}] (* _Jean-François Alcover_, Jan 10 2023, after _Alois P. Heinz_ *)

%Y Cf. A001011, A075496.

%K nonn

%O 1,2

%A _Henry Bottomley_, Sep 16 2005