|
%I #23 Jan 13 2022 06:06:12
%S 1,1,2,4,7,13,24,43,78,142,256,463,838,1513,2735,4944,8931,16139,
%T 29164,52693,95213,172042,310855,561682,1014898,1833794,3313454,
%U 5987026,10817836,19546558,35318325,63816013,115307993,208347899,376459955,680218580,1229074432
%N Number of compositions of n which avoid the pattern 112.
%H Alois P. Heinz, <a href="/A128742/b128742.txt">Table of n, a(n) for n = 0..1000</a>
%H S. Heubach and T. Mansour, <a href="https://arxiv.org/abs/math/0603285">Enumeration of 3-letter patterns in combinations</a>, arXiv:math/0603285 [math.CO], 2006.
%F G.f.: 1/( 1 - Sum_{j>=1} x^j*Product_{i=1..j-1} (1-x^(2*i)) ).
%F 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
%p b:= proc(n, t, l) option remember; `if`(n=0, 1, add(
%p b(n-j, is(j=l), j), j=1..min(n, `if`(t, l, n))))
%p end:
%p a:= n-> b(n, false, 0):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Oct 24 2017
%t 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]]}]];
%t a[n_] := b[n, False, 0];
%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Nov 06 2017, after _Alois P. Heinz_ *)
%o (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
%o (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
%Y Cf. A003116, A003475.
%K nonn
%O 0,3
%A _Ralf Stephan_, May 08 2007
|
