|
|
A335471
|
|
Number of compositions of n avoiding the pattern (1,2,1).
|
|
9
|
|
|
1, 1, 2, 4, 7, 13, 23, 40, 67, 115, 190, 311, 505, 807, 1285, 2031, 3164, 4896, 7550, 11499, 17480, 26379, 39558, 58946, 87469, 129051, 189484, 277143, 403477, 584653, 844236, 1213743, 1738372, 2481770, 3528698, 5003364, 7070225, 9958387, 13982822, 19580613, 27333403
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of (1,1,2)-avoiding or (2,1,1)-avoiding compositions.
We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
A composition of n is a finite sequence of positive integers summing to n.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = F(n,n,1) where F(n,m,k) = F(n,m-1,k) + k*(Sum_{i=1..floor(n/m)} F(n-i*m, m-1, k+i)) for m > 0 with F(0,m,k)=1 and F(n,0,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020
|
|
EXAMPLE
|
The a(0) = 1 through a(5) = 13 compositions:
() (1) (2) (3) (4) (5)
(11) (12) (13) (14)
(21) (22) (23)
(111) (31) (32)
(112) (41)
(211) (113)
(1111) (122)
(212)
(221)
(311)
(1112)
(2111)
(11111)
|
|
MATHEMATICA
|
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, ___, y_, ___, x_, ___}/; x<y]&]], {n, 0, 10}]
|
|
PROG
|
(PARI) a(n)={local(Cache=Map()); my(F(n, m, k)=if(m>n, m=n); if(m==0, n==0, my(hk=[n, m, k], z); if(!mapisdefined(Cache, hk, &z), z=self()(n, m-1, k) + k*sum(i=1, n\m, self()(n-i*m, m-1, k+i)); mapput(Cache, hk, z)); z)); F(n, n, 1)} \\ Andrew Howroyd, Dec 31 2020
|
|
CROSSREFS
|
The version for patterns is A001710.
The version for prime indices is A335449.
These compositions are ranked by A335467.
The complement A335470 is the matching version.
The (2,1,2)-avoiding version is A335473.
Compositions are counted by A011782.
Compositions avoiding (1,2,3) are counted by A102726.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|