|
| |
|
|
A102726
|
|
Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.
|
|
0
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,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.
|
|
|
REFERENCES
| Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, preprint, 2005.
|
|
|
LINKS
| M. Elder and V. Vatter, Problems and conjectures presented at the third international conference on permutation petterns
|
|
|
FORMULA
| G.f.: sum((1/(1-x^i))*prod((1-x^i)/((1-x^(j-i))*(1-x^i-x^j)), j=1..infinity; j not equal to i), i=1..infinity)
|
|
|
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.
|
|
|
CROSSREFS
| Sequence in context: A000128 A106399 A007800 * A188900 A189075 A189077
Adjacent sequences: A102723 A102724 A102725 * A102727 A102728 A102729
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Herbert S. Wilf (wilf(AT)math.upenn.edu), Feb 07 2005
|
|
|
EXTENSIONS
| More terms from Ralf Stephan (ralf(AT)ark.in-berlin.de), May 27 2005
|
| |
|
|
