The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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 Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid. 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. Constant patterns are counted by A000005 and ranked by A272919. Permutations are counted by A000142 and ranked by A333218. Patterns are counted by A000670 and ranked by A333217. Compositions are counted by A011782. Strict compositions are counted by A032020 and ranked by A233564. Patterns matched by compositions are counted by A335456. Minimal patterns avoided by a given composition are counted by A335465. Cf. A056986, A106356, A232464, A269134, A333755. Sequence in context: A007800 A362063 A309982 * A188900 A189075 A345372 Adjacent sequences: A102723 A102724 A102725 * A102727 A102728 A102729 KEYWORD easy,nonn AUTHOR Herbert S. Wilf, Feb 07 2005 EXTENSIONS More terms from Ralf Stephan, May 27 2005 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 4 13:15 EST 2024. Contains 370532 sequences. (Running on oeis4.)