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

%I #40 Jan 01 2021 03:18:44

%S 1,1,2,4,8,16,31,60,114,214,398,732,1334,2410,4321,7688,13590,23869,

%T 41686,72405,125144,215286,368778,629156,1069396,1811336,3058130,

%U 5147484,8639976,14463901,24154348,40244877,66911558,111026746,183886685,304034456,501877227

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

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

%H Alois P. Heinz and Vaclav Kotesovec, <a href="/A102726/b102726.txt">Table of n, a(n) for n = 0..900</a> (first 400 terms from Alois P. Heinz)

%H M. Elder and V. Vatter, <a href="http://arXiv.org/abs/math.CO/0505504">Problems and conjectures presented at the third international conference on permutation petterns</a>

%H Carla D. Savage and Herbert S. Wilf, <a href="http://dx.doi.org/10.1016/j.aam.2005.06.003">Pattern avoidance in compositions and multiset permutations</a>, Advances in Applied Mathematics 36 (2006), pp.194-201.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>

%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>

%F 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)).

%F 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

%e 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.

%p b:= proc(n, m, t) option remember; `if`(n=0, 1,

%p add(b(n-i, min(m, i, n-i), min(t, n-i,

%p `if`(i>m, i, t))), i=1..min(n, t)))

%p end:

%p a:= n-> b(n$3):

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Mar 18 2014

%t 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]}]];

%t a[n_] := b[n, n, n];

%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Nov 10 2017, after _Alois P. Heinz_ *)

%t mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union[mstype/@Subsets[#]],{1,2,3}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 22 2020 *)

%o (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

%Y The version for patterns is A226316.

%Y These compositions are ranked by the complement of A335479.

%Y The matching version is A335514.

%Y The version for prime indices is A335521.

%Y Constant patterns are counted by A000005 and ranked by A272919.

%Y Permutations are counted by A000142 and ranked by A333218.

%Y Patterns are counted by A000670 and ranked by A333217.

%Y Compositions are counted by A011782.

%Y Strict compositions are counted by A032020 and ranked by A233564.

%Y Patterns matched by compositions are counted by A335456.

%Y Minimal patterns avoided by a given composition are counted by A335465.

%Y Cf. A056986, A106356, A232464, A269134, A333755.

%K easy,nonn

%O 0,3

%A Herbert S. Wilf, Feb 07 2005

%E More terms from _Ralf Stephan_, May 27 2005