A232394 The number of compositions of n with no more than 3 consecutive identical parts (summands).

1, 1, 2, 4, 7, 15, 29, 57, 111, 218, 429, 841, 1651, 3239, 6355, 12473, 24475, 48029, 94249, 184946, 362932, 712194, 1397569, 2742507, 5381729, 10560797, 20723884, 40667338, 79803197, 156601100, 307304821, 603036937, 1183364302, 2322164658, 4556879623

Offset

0,3

Links

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

Formula

The g.f. for the number of compositions of n with no more than m consecutive identical parts is 1/( 1 - sum_{j>=1} x^j*(1 - x^(j*m))/(1 - x^j)/ (1 + x^j*(1 - x^(j*m))/(1 - x^j)) ); set m = 3 for this sequence.

a(n) ~ c * d^n, where d=1.962341312018097075518216734398388302205091029921968626465436021267458..., c=0.506212613637348069558928622560083229757824786467201325660889396545904... - Vaclav Kotesovec, May 01 2014

Example

a(6) = 29 because there are 32 compositions of 6 but we exclude: 1+1+1+1+1+1, 1+1+1+1+2, 2+1+1+1+1.

Maple

b:= proc(n, t, c) option remember;
       `if`(n=0, 1, add(`if`(t<>j, b(n-j, j, 1),
       `if`(c<3, b(n-j, j, c+1), 0)), j=1..n))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 24 2013

Mathematica

Series[1/(1-Sum[(z^j+z^(2j)+z^(3j))/(1+z^j+z^(2j)+z^(3j)), {j, 1, nn}]), {z, 0, nn}], z]

Crossrefs

Cf. A003242, A128695, A232464.

Sequence in context: A248574 A136336 A244456 * A356626 A115178 A331934

Adjacent sequences: A232391 A232392 A232393 * A232395 A232396 A232397

Keyword

nonn

Author

Geoffrey Critzer, Nov 23 2013

Status

approved