A128761 Number of compositions of n with parts in N which avoid the consecutive pattern 123.

1, 1, 2, 4, 8, 16, 31, 61, 119, 232, 453, 883, 1721, 3354, 6536, 12735, 24813, 48344, 94189, 183506, 357518, 696534, 1357019, 2643798, 5150746, 10034865, 19550268, 38088486, 74205248, 144569092, 281654211, 548727863, 1069049370, 2082756500

Offset

0,3

Links

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

S. Heubach and T. Mansour, Enumeration of 3-letter patterns in combinations, arXiv:math/0603285 [math.CO], 2006.

Formula

The Heubach/Mansour paper has a complicated g.f.

a(n) ~ c * d^n, where d = 1.948232199887283224240693518762976752988220177086321158242512704029011807341..., c = 0.57609601848694597639954632728322472031509789101742496394456882851645843... - Vaclav Kotesovec, Sep 20 2019

Maple

b:= proc(n, t, l) option remember; `if`(n=0, 1, add(
      b(n-j, is(j>l), j), j=1..min(n, `if`(t, l, n))))
    end:
a:= n-> b(n, false, n):
seq(a(n), n=0..35);  # Alois P. Heinz, Oct 24 2017

Mathematica

b[n_, t_, l_] := b[n, t, l] = If[n == 0, 1, Sum[b[n - j, j > l, j], {j, 1, Min[n, If[t, l, n]]}]];
a[n_] := b[n, False, n];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Nov 14 2017, after Alois P. Heinz *)

Crossrefs

Sequence in context: A223940 A189076 A192656 * A332726 A239557 A001591

Adjacent sequences: A128758 A128759 A128760 * A128762 A128763 A128764

Keyword

nonn

Author

Ralf Stephan, May 08 2007

Extensions

More terms from Vladeta Jovovic, Oct 03 2007

Status

approved