A334155 a(n) is the number of length n decorated permutations avoiding the pattern 001.

1, 2, 5, 15, 57, 273, 1593, 10953, 86553, 771993, 7666713, 83871513, 1001957913, 12976997913, 181106559513, 2709277004313, 43247182412313, 733699248716313, 13182759232076313, 250070586344012313, 4994229502288460313, 104743211837530700313, 2301653725221036620313

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

Table of n, a(n) for n=0..22.

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

Cf. A334154.

Sequence in context: A005976 A351158 A187981 * A373768 A348365 A048192

Adjacent sequences: A334152 A334153 A334154 * A334156 A334157 A334158

Keyword

nonn

Author

Jordan Weaver, Apr 16 2020

Status

approved