cp's OEIS Frontend

A224959 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) - p(j-1) <= 2.

%I A224959 #23 Jun 02 2025 08:31:27
%S A224959 1,1,2,4,8,15,29,55,105,199,378,716,1358,2572,4873,9229,17480,33102,
%T A224959 62688,118709,224795,425676,806068,1526371,2890338,5473125,10363871,
%U A224959 19624925,37161558,70368705,133249369,252319408,477788980,904735349,1713195705,3244086145
%N A224959 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) - p(j-1) <= 2.
%H A224959 Alois P. Heinz, <a href="/A224959/b224959.txt">Table of n, a(n) for n = 0..3607</a>
%F A224959 a(n) ~ c * d^n, where d=1.893587506319686491635881459546948770530553555112342985931092896452453511... and c=0.6398882559654423774981963082429746674258714212085034829366885993226... - _Vaclav Kotesovec_, May 01 2014
%e A224959 There are a(5) = 15 such compositions of 5:
%e A224959 01:  [ 1 1 1 1 1 ]
%e A224959 02:  [ 1 1 1 2 ]
%e A224959 03:  [ 1 1 2 1 ]
%e A224959 04:  [ 1 1 3 ]
%e A224959 05:  [ 1 2 1 1 ]
%e A224959 06:  [ 1 2 2 ]
%e A224959 07:  [ 1 3 1 ]
%e A224959 08:  [ 2 1 1 1 ]
%e A224959 09:  [ 2 1 2 ]
%e A224959 10:  [ 2 2 1 ]
%e A224959 11:  [ 2 3 ]
%e A224959 12:  [ 3 1 1 ]
%e A224959 13:  [ 3 2 ]
%e A224959 14:  [ 4 1 ]
%e A224959 15:  [ 5 ]
%e A224959 (the single forbidden composition is [ 1 4 ]).
%p A224959 b:= proc(n, i) option remember;
%p A224959       `if`(n=0, 1, add(b(n-j, max(1, j-2)), j=i..n))
%p A224959     end:
%p A224959 a:= n-> b(n, 1):
%p A224959 seq(a(n), n=0..40);  # _Alois P. Heinz_, May 02 2013
%t A224959 b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, Max[1, j-2]], {j, i, n}]];
%t A224959 a[n_] := b[n, 1];
%t A224959 a /@ Range[0, 40] (* _Jean-François Alcover_, Dec 19 2020, after _Alois P. Heinz_ *)
%Y A224959 Cf. A003116 (compositions such that p(j) - p(j-1) <= 1).
%Y A224959 Cf. A225084 (triangle: compositions of n such that max(p(j) - p(j-1)) = k).
%Y A224959 Cf. A225085 (triangle: compositions of n such that max(p(j) - p(j-1)) <= k).
%K A224959 nonn
%O A224959 0,3
%A A224959 _Joerg Arndt_, Apr 21 2013