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

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

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

Prog

(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

Crossrefs

Cf. A003116, A003475.

Sequence in context: A049284 A049285 A002843 * A318748 A107281 A006744

Adjacent sequences: A128739 A128740 A128741 * A128743 A128744 A128745

Keyword

nonn

Author

Ralf Stephan, May 08 2007

Status

approved