|
|
A335473
|
|
Number of compositions of n avoiding the pattern (2,1,2).
|
|
9
|
|
|
1, 1, 2, 4, 8, 15, 29, 55, 103, 190, 347, 630, 1134, 2028, 3585, 6291, 10950, 18944, 32574, 55692, 94618, 159758, 268147, 447502, 743097, 1227910, 2020110, 3308302, 5394617, 8757108, 14155386, 22784542, 36529813, 58343498, 92850871, 147254007, 232750871, 366671436
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of (1,2,2) or (2,2,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,1,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 <= n with F(0,m,k)=1 and F(n,m,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020
|
|
EXAMPLE
|
The a(0) = 1 through a(5) = 15 compositions:
() (1) (2) (3) (4) (5)
(11) (12) (13) (14)
(21) (22) (23)
(111) (31) (32)
(112) (41)
(121) (113)
(211) (122)
(1111) (131)
(221)
(311)
(1112)
(1121)
(1211)
(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, 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, 1, 1)} \\ Andrew Howroyd, Dec 31 2020
|
|
CROSSREFS
|
The version for patterns is A001710.
The version for prime indices is A335450.
These compositions are ranked by A335469.
The (1,2,1)-avoiding version is A335471.
The complement A335472 is the matching version.
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
|
|
|
|