

A102726


Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.


86



1, 1, 2, 4, 8, 16, 31, 60, 114, 214, 398, 732, 1334, 2410, 4321, 7688, 13590, 23869, 41686, 72405, 125144, 215286, 368778, 629156, 1069396, 1811336, 3058130, 5147484, 8639976, 14463901, 24154348, 40244877, 66911558, 111026746, 183886685, 304034456, 501877227
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The sequence is the same no matter which of the six patterns of three letters is chosen as the one to be avoided.


LINKS



FORMULA

G.f.: Sum_{i>=1} (1/(1x^i))*Product_{j>=1, j<>i} (1x^i)/((1x^(ji))*(1x^ix^j)).
Asymptotics (Savage and Wilf, 2005): a(n) ~ c * ((1+sqrt(5))/2)^n, where c = r/(r1)/(rs) * (r * Product_{j>=3} (11/r)/(1r^(1j))/(11/rr^(j))  Product_{j>=3} (11/r^2)/(1r^(2j))/(11/r^2r^(j)) ) = 18.9399867283479198666671671745270505487677312850521421513193261105... and r = (1+sqrt(5))/2, s = (1sqrt(5))/2.  Vaclav Kotesovec, May 02 2014


EXAMPLE

a(6) = 31 because there are 32 compositions of 6 into positive parts and only one of these, namely 6 = 1+2+3, contains the pattern (123), the other 31 compositions of 6 avoid that pattern.


MAPLE

b:= proc(n, m, t) option remember; `if`(n=0, 1,
add(b(ni, min(m, i, ni), min(t, ni,
`if`(i>m, i, t))), i=1..min(n, t)))
end:
a:= n> b(n$3):


MATHEMATICA

b[n_, m_, t_] := b[n, m, t] = If[n == 0, 1, Sum[b[n  i, Min[m, i, n  i], Min[t, n  i, If[i > m, i, t]]], {i, 1, Min[n, t]}]];
a[n_] := b[n, n, n];
mstype[q_]:=q/.Table[Union[q][[i]]>i, {i, Length[Union[q]]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MemberQ[Union[mstype/@Subsets[#]], {1, 2, 3}]&]], {n, 0, 10}] (* Gus Wiseman, Jun 22 2020 *)


PROG

(PARI) seq(n)={Vec(sum(i=1, n, prod(j=1, n, if(i==j, 1, (1x^i)/((1x^(ji))*(1x^ix^j))) + O(x*x^n))/(1x^i)))} \\ Andrew Howroyd, Dec 31 2020


CROSSREFS

The version for patterns is A226316.
These compositions are ranked by the complement of A335479.
The version for prime indices is A335521.
Compositions are counted by A011782.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a given composition are counted by A335465.


KEYWORD

easy,nonn


AUTHOR

Herbert S. Wilf, Feb 07 2005


EXTENSIONS



STATUS

approved



