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
Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..900 (first 400 terms from Alois P. Heinz)
M. Elder and V. Vatter, Problems and conjectures presented at the third international conference on permutation petterns
Carla D. Savage and Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, Advances in Applied Mathematics 36 (2006), pp.194-201.
Wikipedia, Permutation pattern
FORMULA
G.f.: Sum_{i>=1} (1/(1-x^i))*Product_{j>=1, j<>i} (1-x^i)/((1-x^(j-i))*(1-x^i-x^j)).
Asymptotics (Savage and Wilf, 2005): a(n) ~ c * ((1+sqrt(5))/2)^n, where c = r/(r-1)/(r-s) * (r * Product_{j>=3} (1-1/r)/(1-r^(1-j))/(1-1/r-r^(-j)) - Product_{j>=3} (1-1/r^2)/(1-r^(2-j))/(1-1/r^2-r^(-j)) ) = 18.9399867283479198666671671745270505487677312850521421513193261105... and r = (1+sqrt(5))/2, s = (1-sqrt(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(n-i, min(m, i, n-i), min(t, n-i,
`if`(i>m, i, t))), i=1..min(n, t)))
end:
a:= n-> b(n$3):
seq(a(n), n=0..50); # Alois P. Heinz, Mar 18 2014
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];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)
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, (1-x^i)/((1-x^(j-i))*(1-x^i-x^j))) + O(x*x^n))/(1-x^i)))} \\ Andrew Howroyd, Dec 31 2020
CROSSREFS
The version for patterns is A226316.
These compositions are ranked by the complement of A335479.
The matching version is A335514.
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
More terms from Ralf Stephan, May 27 2005
STATUS
approved