cp's OEIS Frontend

A173258 Number of compositions of n where differences between neighboring parts are in {-1,1}.

%I A173258 #60 Oct 17 2023 15:48:26
%S A173258 1,1,1,3,2,4,5,5,7,10,9,14,16,19,24,31,35,45,55,66,84,104,124,156,192,
%T A173258 236,292,363,444,551,681,839,1040,1287,1586,1967,2430,3001,3717,4597,
%U A173258 5683,7034,8697,10758,13312,16469,20369,25204,31180,38574,47726,59047
%N A173258 Number of compositions of n where differences between neighboring parts are in {-1,1}.
%H A173258 Alois P. Heinz, <a href="/A173258/b173258.txt">Table of n, a(n) for n = 0..5000</a>
%H A173258 John Tyler Rascoe, <a href="/A173258/a173258.pdf">Illustration of n = 1..16</a>
%F A173258 a(n) ~ c * d^n, where d=1.23729141259673487395949649334678514763130846902468..., c=1.134796087242490181499736234755111281606636700030106.... - _Vaclav Kotesovec_, May 01 2014
%F A173258 G.f.: 1 + Sum_{k>0} G(x,k) where G(x,k) = x^k*(1 + G(x,k+1) + G(x,k-1)) for k > 0 and G(x,0) = 0. - _John Tyler Rascoe_, Sep 16 2023
%e A173258 a(3) = 3: [3], [2,1], [1,2].
%e A173258 a(4) = 2: [4], [1,2,1].
%e A173258 a(5) = 4: [5], [3,2], [2,3], [2,1,2].
%e A173258 a(6) = 5: [6], [3,2,1], [2,1,2,1], [1,2,3], [1,2,1,2].
%p A173258 b:= proc(n, i) option remember;
%p A173258       `if`(n<1 or i<1, 0, `if`(n=i, 1, add(b(n-i, i+j), j=[-1, 1])))
%p A173258     end:
%p A173258 a:= n-> `if`(n=0, 1, add(b(n, j), j=1..n)):
%p A173258 seq(a(n), n=0..70);
%t A173258 b[n_, i_] := b[n, i] = If[n < 1 || i < 1, 0, If[n == i, 1, Sum[b[n - i, i + j], {j, {-1, 1}}]]]; a[n_] := If[n == 0, 1, Sum[b[n, j], {j, 1, n}]]; Table[a[n], {n, 0, 70}] // Flatten (* _Jean-François Alcover_, Dec 13 2013, translated from Maple *)
%o A173258 (PARI)
%o A173258 step(R,n)={matrix(n, n, i, j, if(i>j, if(j>1, R[i-j, j-1]) + if(j+1<=n, R[i-j, j+1])) )}
%o A173258 a(n)={my(R=matid(n), t=(n==0), m=0); while(R, m++; t+=vecsum(R[n,]); R=step(R,n)); t} \\ _Andrew Howroyd_, Aug 23 2019
%Y A173258 Column k=1 of A214247, A214249.
%Y A173258 Row sums of A309938, A364039.
%Y A173258 Cf. A227310, A291904, A291905, A343795, A362500, A363718, A364529.
%K A173258 nonn
%O A173258 0,4
%A A173258 _Alois P. Heinz_, Jul 08 2012