|
|
A334155
|
|
a(n) is the number of length n decorated permutations avoiding the pattern 001.
|
|
1
|
|
|
1, 2, 5, 15, 57, 273, 1593, 10953, 86553, 771993, 7666713, 83871513, 1001957913, 12976997913, 181106559513, 2709277004313, 43247182412313, 733699248716313, 13182759232076313, 250070586344012313, 4994229502288460313, 104743211837530700313, 2301653725221036620313
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
A decorated permutation of length n is a word w=w_1...w_n on the letters {0,...,n} such that the restriction of w to its nonzero entries is an ordinary permutation in one-line notation. Then w avoids the pattern 001 if there is no subword w_{i_1}w_{i_2}w_{i_3} with i_1 < i_2 < i_3 such that w_{i_1}=w_{i_2} = 0 and w_{i_3} > 0.
a(n) is also the number of decorated permutations of length n avoiding the pattern 010. This can be proved via a simple bijection mapping a 001-avoiding decorated permutation to a 010-avoiding decorated permutation.
The number of decorated permutations of length n avoiding the pattern 012 is A334154.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n! + Sum_{j=0..n-1} (j+1)*j!.
|
|
EXAMPLE
|
For n=3, the a(3)=15 decorated permutations avoiding 001 are 000, 010, 100, 012, 102, 120, 021, 201, 210, 123, 132, 213, 231, 312, and 321.
For n=5, 10302 does not avoid 001, because it contains the subword 002.
|
|
PROG
|
(PARI) a(n) = n! + sum(j=0, n-1, (j+1)*j!); \\ Michel Marcus, May 11 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|