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

Links

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

Formula

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

Example

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.

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

Crossrefs

Cf. A003242, A328222.

Sequence in context: A107340 A326655 A291866 * A173270 A301657 A241342

Adjacent sequences: A332826 A332827 A332828 * A332830 A332831 A332832

Keyword

nonn

Author

Alois P. Heinz, Feb 25 2020

Status

approved