1Introduction AaronRobertson and Patterns PermutationsContainingandAvoiding

Discrete Mathematics and Theoretical Computer Science 3, 1999, 151–154

Permutations Containing and Avoiding

and

Patterns

Aaron Robertson

Department of Mathematics, Colgate University, Hamilton, NY 13346 received April 5, 1999, revised May 12, 1999, accepted May 19, 1999.

We prove that the number of permutations which avoid -patterns and have exactly one -pattern, equals

, for . We then give a bijection onto the set of permutations which avoid -patterns and have exactly one -pattern. Finally, we show that the number of permutations which contain exactly one -pattern and exactly one -pattern is ^{! " $#}, for^%& .

Keywords: Patterns, Words

1 Introduction

In 1990, Herb Wilf asked the following: How many permutations of length^' avoid a given pattern,⁽ ? By pattern-avoiding we mean the following: Let⁾ be a permutation of length^' and let(*,+-(/.01(32044401(3576

be a permutation of length^8%9:' (we will call this a pattern of length⁸ ). Let^; be a set of^< integers, and let^=>?; . Define(A@1BDCED+F=70;G6 to be ^H if⁼ is the smallest element in^; ,^I if it is the second smallest, ..., and^< if it is the largest. The permutation⁾ avoids the pattern⁽ if and only if there does not exist a set of indicesJK*L+NMO.0PMQ2704440PM576, such that(%*R+S(A@TBUCEU+1)V+NMO.60PJD60T(A@1BDCED+1)V+NM260!JU604440T(A@TBUCEU+1)V+NMW5X60!JU6P6.

In two beautiful papers ([B1] and [N]), the number of subsequences containing exactly one^HYZI -pattern and exactly one ^HI7Y -pattern are enumerated. Noonan shows in [N] that the number of permutations containing exactly one ^HIY -pattern is the simple formula ^{[\^] 2}

\

\7_

[!`

. B´ona proves that the even simpler formula ^]2

\Da

[

\Da

[b`

enumerates the number of permutations containing exactly one^HYZI -pattern. B´ona’s result proved a conjecture first made by Noonan and Zeilberger in [NZ].

Noonan and Zeilberger considered in [NZ] the number of permutations of length^' which contain ex- actly^< p-patterns, for^{< c?H} . B´ona, in [B2], made further progress concerning the number of permutations with exactly^<dHYUI -patterns. In this article we work towards the following generalization: How many per- mutations of length^' avoid patterns^(Ae, for^Mfchg , and contain^<ij($i -patterns, for^=kclH,^<imcnH ? We will first consider the permutations of length^' which avoid^HYZI -patterns, but contain exactly one^HIY -pattern.

We then define a natural bijection between these permutations and the permutations of length ^' which avoid^HIY -patterns, but contain exactly one ^HYZI -pattern. Finally, we will calculate the number of permu- tations which contain one^HIY -pattern and one^HYZI -pattern. These results address questions first raised in [NZ].^o

email:[email protected] 1365–8050 c

p

1999 Maison de l’Informatique et des Math´ematiques Discr`etes (MIMD), Paris, France

152 Aaron Robertson

2 Known Results

For completeness, two results which are already known are given below.

Lemma 1: The number of permutations of length^' with one^HI -pattern is^'q:H .

Proof: Induct on^' . The base case is trivial. A permutation,^r , of length^' with one^HI -pattern must have

's*trj+WH6 or^'*urv+wI76 . If^'*urj+OH6 , by induction we get^'xqI permutation. If^'*urj+TIZ6 , then we must

have'sq?H*yrj+WH6 (or we would have more than one ^HI -pattern). The rest of the entries of^r must be

decreasing. Hence we get^H more permutation from this second case, for a total of^'q:H . Lemma 2: The number of permutations which avoid both the pattern^HI7Y and^HYUI is^{I \Da .} . Proof: Let ^{z \} denote the number of permutations we are interested in. Then ^{z \ *|{}

\

eF}v.

z

\Da

e with

z~K*yH . To see this, let^ be a permutation of length^'€qH . Insert the element^' into the^MQ‚1ƒ position of

 . Let⁾ be this new permutation of length^' . To assure that⁾ avoids the ^HYZI -pattern, we must have all entries preceding^' in⁾ be larger than the entries following^' . To assure that⁾ avoids the ^HIY -pattern, the entries preceding^' must be in decreasing order. This argument gives the sum in the recursion. The recursion holds by noting that if^'„*RH , there is one permutation which avoids both patterns. To complete the proof note that^{z \ *…I \Da .} .

3 One 123-pattern, but no 132-pattern

Theorem 1: The number of permutations of length^' which have exactly one ^HI7Y -pattern, and avoid the

HYZI -pattern is^{+1'xqIZ6OI \a [} .

Proof: Call a permutation good if it has exactly one ^HI7Y -pattern and avoids the ^HYZI -pattern, and let^{† \} denote the number of good permutations of length^' . Let^‡ be a permutation of length^'€qH . Insert the element^' into the^Mw‚1ƒ position of^‡ . Call this newly constructed permutation of length^' ,⁾ . To assure that ⁾ avoids the ^HYUI pattern, we must have all elements preceding^' in⁾ be larger than the elements following^' in⁾ . For⁾ to be a good permutation, we must consider two disjoint cases.

Case I: The pattern^HI7Y appears in the elements following^' in⁾ . This forces the elements preceding^' to be in decreasing order. Summing over^M, this case accounts for^{

\

eF}v.

†

\Da

e permutations.

Case II: The pattern ^HIY appears in the elements preceding and including^' in⁾ . This forces the ^Y in the pattern to be^' . Hence the elements preceding^' must contain exactly one ^HI -pattern. (Further there must be at least^I elements. Hence^M must be at least^Y ). From Lemma 1, this number is^Mˆq€I . We are also forced to avoid both patterns in the elements following^' . Lemma 2 implies that there are^{I \Da ea .} such permutations. Summing over^M, this case accounts for^{

\Da

.

e‰}

[

+1MvqI76PI

\Da

ea .Š

'qI permutations.

We have established that the recurrence relation

† \ * \

‹

e‰}j.

†

\Da

e Š

\a

.

‹

eF}

[

+1MGqI76PI

\Da

ea . Š

'qI$0

which holds for^'ctY (^{† ~} *,g$0W†U.Œ*Lgˆ0W†72K*,g ), enumerates the permutations of length^' which avoid the pattern^HYZI and contain exactly one ^HIY -pattern.

One easy way to proceed would be to find the generating function of^{† \} . However, in this article we would like to employ a different, and in many circumstances more powerful, tool. We will use the Maple procedurefindrecin Doron Zeilberger’s Maple package EKHAD^ . (The Maple shareware

Ž

Available for download atwww.math.temple.edu/˜zeilberg/

Permutations Containing and Avoiding^HI7Y and ^HYZI Patterns 153 packagegfuncould have also been used.) Instructions for its use are available online. To usefind- rec we compute the first few terms of^{† \} . These are (for ^'c‘ ) A0HI$0PYUI0P’Zg$0H“ZI$0OZ7’$0HgZI . We typefindrec([4,12,32,80,192,448,1024],0,2,n,N)and are given the recurrence ^{” \ *}

A+T”

\Da

.•q–”

\Da

26 for^'–c… . Define^{” ~} *ug$0—”3.˜*tgˆ0!”A2˜*Rg$0 and^”

[

*yH , and it is routine to verify that

† \

*y”

\ for^'nc,g . Another routine calculation shows us that ^{” \} *™+N'sqhI76PI

\Da

[ for^'?c,Y , thereby proving the statement of the theorem.

4 One 132-pattern, but no 123-pattern

Theorem 2: The number of permutations of length^' which have exactly one ^HYUI -pattern, and avoid the

HIY -pattern is^{+1'xqIZ6OI \a [} .

Proof: We prove this by exhibiting a (natural) bijection from the permutations counted in Theorem 1 to the permutations counted in this theorem. Define šœ›-*ž)Ÿ› ) avoids ^HYZI -pattern and contains one

HIY -pattern^¡ and¢£›-*¤)y›¥) avoids ^HI7Y -pattern and contains one ^HYZI -pattern^¡ . We will show that

¦ š ¦* ¦ ¢ ¦

, by using the following bijection:

Letr–›Aš…q/§ž¢ . Let^¨k>š , and let^BD©C be the^HI7Y -pattern in^¨ . Then^r acts on the elements of^¨ as follows:rv+1ª36«*¬ª ifª®­>¯X©0PC¡ ,^{rv+w©6¥*…C} , and^rj+1C6¥*?©. In other words, all elements keep their positions except^© and^C switch places. An easy examination of several cases shows that this is a bijection, thereby proving the theorem.

5 One 132-pattern and one 123-pattern

Theorem 3: The number of permutations of length^' which have exactly one ^HYZI -pattern and one ^HIY - pattern is+N'qYZ6+1'xqsD6OI

\a3°

.

Proof: We use the same insertion technique as in the proof of Theorem 1. Call a permutation good if it has exactly one^HIY -pattern and exactly one^HYZI -pattern and let^{† \} denote the number of good permutations of length^' . Let^‡ be a permutation of length^'%qhH . Insert the element^' into the^MQ‚1ƒ position of^‡ . Let⁾ be this newly constructed permutation of length^' . We note that the^HYZI -pattern cannot consist of elements only preceding^' . If this were the case, we would have two ^HIY -patterns ending with^' . For⁾ to be a good permutation, we must consider the following disjoint cases.

Case I: The^HYUI -pattern consists of elements following^' . In this case all elements preceding^' must be larger than the elements following^' .

Subcase A: The^HI7Y -pattern consists of elements following^' . Summing over^M we get^{

\

eF}v.

†

\a

e good

permutations in this subcase.

Subcase B: The elements preceding^' have exactly one ^HI -pattern. This gives a ^HIY -pattern where the 3 in the pattern is^' . We must also avoid the ^HIY -pattern in the elements following^' . Summing over^M and using Lemma 1 and Theorem 1, we get^{

\a

[

eF}

[

+1MjqhI76+1'€q®M±q®YZ6PI

\Da

ea 2

good permutations in this subcase.

Case II: The^HYUI -pattern has the first element preceding^' , the last element following^' , and^' as the middle element. The elements preceding^' must be'qlH70P'q¬I$04440O'qlH

Š

I0O'q¬M, where^'q:M

immediately precedes^' in⁾ . See [B1] for a more detailed argument as to why this must be true.

Subcase A: The elements preceding^' have exactly one^HI -pattern. This gives a^HIY -pattern where the last element of the pattern is^' . We must also avoid both the^HIY and the^HYUI pattern in the elements following

154 Aaron Robertson

' . Summing over^M and using Lemma 1 and Lemma 2 we have^{

\Da

.

eF}b²

+NM±qYZ6PI

\Da

ea .

good permutations in this subcase.

Subcase B: The^HIY -pattern consists of elements following^' . We must have the elements preceding^' in⁾ be decreasing to avoid another ^HI7Y -pattern. Further, the elements following^' must not contain a

HYZI -pattern. Using Theorem 1 and summing over^M, we get a total of ^{

\Da

[

eF}³2

+N'qhMfqI76PI

\Da

ea [ good permutations in this subcase.

In total, we find that the following recurrence enumerates the permutations of length^' which contain exactly one^HIY -pattern and one^HYZI -pattern.

† \ * \

‹

e‰}j.

†

\Da

e Š

\a

²

‹

eF}v.

+wIXM+N'qMGqU6

Š

'qYZ6PI

\Da

ea ²

for^'sc¬´ and^{† . *¬† 2 *†}

[

* 

²

*…g .

Usingfindrecagain by typingfindrec([2,12,48,160,480,1344,3584],1,1,n,N) (where the list is the first few terms of our recurrence for^'sc´ ) we get the recurrence^{z \_ . * 2µ}

\7_

2P¶

\ z \ ,

with^z7. *?I . After reindexing, another routine calculation shows that^{z \ *¬† \} . Solving^{z \} for an explicit answer, we find that^{† \} *L+N'qYZ6+1'xqsD6OI

\a3°

.

We conjecture that the generating function for the number of permutations with exactly zero or exactly one^HYUI -pattern and exactly^<KHI7Y -patterns is·k+1¸D6P¹$+WH q®I¸D6Wº

_ .

, where^·k+1¸D6 is a polynomial. For more evidence, and further extensions see [RWZ].

Acknowledgements

The author would like to thank Robin Chapman for his useful comments.

References

[B1] M. B´ona, Permutations with one or two^HYZI -subsequences., Discrete Mathematics, 181, 1998, 267- 274.

[B2] M. B´ona, The Number of Permutations with Exactly^<˜HYZI -subsequences is^· -recursive in the Size!., Advances in Applied Mathematics, 18, 1997, 510-522.

[N] J. Noonan, The Number of Permutations Containing Exactly One Increasing Subsequence of Length

Y , Discrete Mathematics, 152, 1996, 307-313.

[NZ] J. Noonan and D. Zeilberger, The Enumeration of Permutations with a Prescribed Number of “For- bidden” Patterns, Advances in Applied Mathematics, 17, 1996, 381-407.

[RWZ] A. Robertson, H. Wilf, and D. Zeilberger, Patterns and Fractions, submitted.

Seewww.math.temple.edu/˜[aaron,zeilberg]/for preprint.