login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A334154 a(n) is the number of length n decorated permutations avoiding the pattern 012. 1
1, 2, 5, 15, 54, 236, 1254, 7986, 59584, 509304, 4897272, 52237448, 611460432, 7787383488, 107155194928, 1583776282704, 25019083516416, 420609003810944, 7496930998018176, 141203784944996736, 2802115237399913728, 58432523737192745472, 1277372108617847278848 (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 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 A104429 A109319

Adjacent sequences:  A334151 A334152 A334153 * A334155 A334156 A334157

KEYWORD

nonn

AUTHOR

Jordan Weaver, Apr 16 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 08:19 EDT 2021. Contains 348066 sequences. (Running on oeis4.)