A334154 a(n) is the number of length n decorated permutations avoiding the pattern 012.

1, 2, 5, 15, 54, 236, 1254, 7986, 59584, 509304, 4897272, 52237448, 611460432, 7787383488, 107155194928, 1583776282704, 25019083516416, 420609003810944, 7496930998018176, 141203784944996736, 2802115237399913728, 58432523737192745472, 1277372108617847278848

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 012 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} = 0 and 0 < w_{i_2} < w_{i_3}.

Links

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

Formula

a(n) = n! + Sum_{j=1..n} Sum_{l=1..n-j+1} binomial(n-l,j-1)*binomial(n-j,l-1)*(l-1)!.

Example

For n=3, there are 16 decorated permutations of length 3 (000, 001, 010, 100, 012, 102, 120, 021, 201, 210, 123, 132, 213, 231, 312, and 321). All of these avoid 012 except 012 itself. Therefore, a(3) = 15.
For n=5, 02031 is a decorated permutation that does not avoid 012 because it contains the subword 023.

Prog

(PARI) a(n) = n! + sum(j=1, n, sum(l=1, n-j+1, binomial(n-l, j-1)*binomial(n-j, l-1)*(l-1)!)); \\ Michel Marcus, May 11 2020

Crossrefs

Cf. A334155, A334156.

Sequence in context: A171450 A204190 A051295 * A009383 A376349 A104429

Adjacent sequences: A334151 A334152 A334153 * A334155 A334156 A334157

Keyword

nonn

Author

Jordan Weaver, Apr 16 2020

Status

approved