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

Author

Ralf Stephan, May 08 2007

Keywords

• nonn

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.

Programs

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

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

Extensions

More terms from Vladeta Jovovic, Oct 03 2007