A128742 Number of compositions of n which avoid the pattern 112.

1, 1, 2, 4, 7, 13, 24, 43, 78, 142, 256, 463, 838, 1513, 2735, 4944, 8931, 16139, 29164, 52693, 95213, 172042, 310855, 561682, 1014898, 1833794, 3313454, 5987026, 10817836, 19546558, 35318325, 63816013, 115307993, 208347899, 376459955, 680218580, 1229074432

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.

Crossrefs

Cf. A003116, A003475.

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, 0):
seq(a(n), n=0..40);  # 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, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)

PARI

my(N=40, x='x+O('x^N)); Vec(1/(1-sum(k=1, N, x^k*prod(j=1, k-1, 1-x^(2*j))))) \\ Seiichi Manyama, Jan 13 2022

PARI

my(N=40, x='x+O('x^N)); Vec(1/sum(k=0, N, (-1)^k*x^k^2/prod(j=1, k, 1-x^(2*j-1)))) \\ Seiichi Manyama, Jan 13 2022

Formula

G.f.: 1/( 1 - Sum_{j>=1} x^j*Product_{i=1..j-1} (1-x^(2*i)) ).

G.f.: 1/( Sum_{k>=0} (-1)^k * x^(k^2) / Product_{j=1..k} (1-x^(2*j-1)) ). - Seiichi Manyama, Jan 13 2022