cp's OEIS Frontend

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

%I A102726 #40 Jan 01 2021 03:18:44
%S A102726 1,1,2,4,8,16,31,60,114,214,398,732,1334,2410,4321,7688,13590,23869,
%T A102726 41686,72405,125144,215286,368778,629156,1069396,1811336,3058130,
%U A102726 5147484,8639976,14463901,24154348,40244877,66911558,111026746,183886685,304034456,501877227
%N A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.
%C A102726 The sequence is the same no matter which of the six patterns of three letters is chosen as the one to be avoided.
%H A102726 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 A102726 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 A102726 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 A102726 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A102726 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A102726 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 A102726 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 A102726 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 A102726 b:= proc(n, m, t) option remember; `if`(n=0, 1,
%p A102726       add(b(n-i, min(m, i, n-i), min(t, n-i,
%p A102726       `if`(i>m, i, t))), i=1..min(n, t)))
%p A102726     end:
%p A102726 a:= n-> b(n$3):
%p A102726 seq(a(n), n=0..50);  # _Alois P. Heinz_, Mar 18 2014
%t A102726 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 A102726 a[n_] := b[n, n, n];
%t A102726 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Nov 10 2017, after _Alois P. Heinz_ *)
%t A102726 mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
%t A102726 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union[mstype/@Subsets[#]],{1,2,3}]&]],{n,0,10}] (* _Gus Wiseman_, Jun 22 2020 *)
%o A102726 (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 A102726 The version for patterns is A226316.
%Y A102726 These compositions are ranked by the complement of A335479.
%Y A102726 The matching version is A335514.
%Y A102726 The version for prime indices is A335521.
%Y A102726 Constant patterns are counted by A000005 and ranked by A272919.
%Y A102726 Permutations are counted by A000142 and ranked by A333218.
%Y A102726 Patterns are counted by A000670 and ranked by A333217.
%Y A102726 Compositions are counted by A011782.
%Y A102726 Strict compositions are counted by A032020 and ranked by A233564.
%Y A102726 Patterns matched by compositions are counted by A335456.
%Y A102726 Minimal patterns avoided by a given composition are counted by A335465.
%Y A102726 Cf. A056986, A106356, A232464, A269134, A333755.
%K A102726 easy,nonn
%O A102726 0,3
%A A102726 Herbert S. Wilf, Feb 07 2005
%E A102726 More terms from _Ralf Stephan_, May 27 2005