|
Search: id:A102726
|
|
|
| A102726 |
|
Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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 this_sequence A118891 A107066 A141019
Adjacent sequences: A102723 A102724 A102725 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
