A332829 Number of compositions of n such that the difference between adjacent parts is at least two.

1, 1, 1, 1, 3, 4, 6, 9, 15, 23, 36, 55, 87, 136, 212, 329, 515, 802, 1251, 1949, 3043, 4745, 7401, 11535, 17994, 28063, 43766, 68243, 106433, 165981, 258854, 403670, 629530, 981750, 1531055, 2387660, 3723569, 5806905, 9055889, 14122638, 22024291, 34346886

Offset: 0

Author

Alois P. Heinz, Feb 25 2020

Keywords

• nonn

Examples

			a(4) = 3: 13, 31, 4.
a(5) = 4: 131, 14, 41, 5.
a(6) = 6: 141, 24, 42, 15, 51, 6.
a(7) = 9: 313, 142, 241, 151, 25, 52, 16, 61, 7.
a(8) = 15: 1313, 3131, 242, 314, 413, 152, 251, 35, 53, 161, 26, 62, 17, 71, 8.
a(9) = 23:  13131, 1314, 1413, 3141, 4131, 414, 252, 135, 153, 315, 351, 513, 531, 162, 261, 36, 63, 171, 27, 72, 18, 81, 9.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1750

Crossrefs

Cf. A003242, A328222.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, add(`if`(abs
      (i-j)<2, 0, b(n-j, `if`(n<2*j-1, -1, j))), j=1..n))
    end:
a:= n-> b(n, -1):
seq(a(n), n=0..50);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[If[Abs[i - j] < 2, 0,
     b[n - j, If[n < 2*j - 1, -1, j]]], {j, 1, n}]];
a[n_] := b[n, -1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 13 2022, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n, where d = 1.55950091106966174000570854045613844480247532446123619115121795622156266..., c = 0.42021981384104890468461570042297109905705539874851026797544718780579866... - Vaclav Kotesovec, Feb 28 2020