COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION 4 Toufik Mansour 0 Department of Mathematics, Haifa University, 31905 Haifa, Israel 0 2 [email protected] n Abstract a J We study the generating function for the number of involutions on n letters containing exactly r 0 8 ≥ 1 occurrencesof 3412. It is shownthat finding this function for a givenr amounts to a routine check of all involutions on 2r+1 letters. O] 2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 05C90 C 1. Introduction . h t Permutations. Letπ Snandτ Smbetwopermutations. Anoccurrenceofτ inπisasubsequence a ∈ ∈ 1 i <i < <i n such that (π(i ),...,π(i )) is order-isomorphic to τ; in such a context, τ m ≤ 1 2 ··· m ≤ 1 m is usually called a pattern. [ In the last decade much attention has been paid to the problem of finding the numbers sr(n) for a σ 1 fixed r 0 and a given pattern τ (see [1, 2, 3, 5, 6, 7, 18, 20, 23, 25, 26, 27, 28, 29]). Most of the v authors≥consideronlythecaser =0,thusstudyingpermutationsavoiding agivenpattern. Onlyafew 8 papersconsiderthecaser >0,usuallyrestrictingthemselvestopatternsoflength3. Usingtwosimple 1 involutions(reverse andcomplement)on itisimmediatethatwithrespecttobeingequidistributed, 2 n S 1 the six patterns of length three fall into the two classes 123,321 and 132,213,231,312 . Noonan { } { } 0 [22] proved that s1 (n) = 3 2n . A general approach to the problem was suggested by Noonan 4 and Zeilberger [231]2;3they ganv(cid:0)en−a3n(cid:1)other proof of Noonan’s result, and conjectured that s2 (n) = 0 123 h/ 529nn(22+n−1117)n(n++150)0(cid:0)n2−n4(cid:1) and s1132(n) = (cid:0)2nn−−33(cid:1). The first conjecture was proved by Fulmek [10] and the latter conjecture was provedby B´onain [6]. A conjecture of Noonanand Zeilbergerstates that sr(n) t σ a is P-recursive in n for any r and τ. It was proved by B´ona [4] for σ =132. Mansour and Vainshtein m [20]suggestedanewapproachtothisprobleminthe caseσ =132,whichallowsonetogetanexplicit : expression for sr (n) for any given r. More precisely, they presented an algorithm that computes v 132 i the generating function sr (n)xn for any r 0. To get the result for a given r, the algorithm X Pn≥0 132 ≥ performscertainroutinechecksforeachelementofthesymmetricgroup . Thealgorithmhasbeen 2r r implemented in C, and yields explicit results for 1 r 6. S a ≤ ≤ Involutions. An involution π is a permutation such that π = π−1; let denote the set of all n- n I involutions. An even (resp. odd) involutionπ is an involution such that the number of occurrences of the pattern 21 in π is an even (resp. odd) number. Several authors have given enumerations of sets of involutions which avoid certain patterns. In [24] Regevprovidedanasymptoticformulafor (12...k)andshowedthat (1234)isenumeratedbythe n n I I nth Motzkin number M = [n/2] n C . In [11] Gessel enumerated (12...k). In [13] Gouyou– n Pi=0 (cid:0)2i(cid:1) i In Beauchamps gave an entirely bijective proof of some very nice exact formulas for (12345) and n I (123456). n I 1 2 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION Pattern-avoiding involutions have also been related with other combinatorial objects. Gire [12] has established a one-to-one correspondence between 1-2 trees having n edges and (321,3142) (this is n S the setofn-permutationsavoidingpatterns321and231,exceptthatthe latteris allowedwhenitis a subsequence ofthe pattern3142). Onthe otherhand, Guibert[14] hasestablishedbijections between 1-2 trees having n edges and each of the sets (231,4132), (3412), and (4321) (and therefore n n n S I I with (1234),bytransposingthecorrespondingYoungtableauxobtainedbyapplyingthe Robinson- n I Schensted algorithm). Also, Guibert [14] has established a bijection between (2143) and (1243). n n I I Morerecently,Guibert,Pergola,andPinzani[15]havegivenaone-to-onecorrespondencebetween1-2 trees having n edges and (2143). It follows that all these sets are enumerated by the nth Motzkin n I number M . Itremainsanopenproblemto provethe conjecture ofGuibert(in [14])that (1432)is n n I also enumerated by the nth Motzkin number M . This conjecture proved by Jaggard[16]. Recently, n Egge[8] gaveenumerationsand generatingfunctions for the number of involutions in (3412)which n I avoid various sets of additional patterns. Egge and Mansour [9] refined Egge’s results by studying generating functions for the number of even and odd involutions in (3412), and they studied the n I generating functions for the number of even and odd involutions in containing the pattern 3412 n I exactly once. For example, they proved the following theorem. Theorem 1.1. (see [9, Proposition7.7]) The generating function for the number of involutions in n I which contain the pattern 3412 exactly once is given by 2x 1 1 2x 2x2 − + − − . 2x2(1 x) 2x2√1 2x 3x2 − − − r n 0 1 2 3 4 5 6 7 8 9 10 11 12 \ 0 1 1 2 4 9 21 51 127 323 835 2188 5798 15511 1 0 0 0 0 1 5 20 70 231 735 2289 7029 21384 2 0 0 0 0 0 0 1 7 37 165 671 2563 9375 3 0 0 0 0 0 0 1 4 17 63 236 877 3270 4 0 0 0 0 0 0 2 12 56 220 803 2783 9364 5 0 0 0 0 0 0 0 2 14 80 383 1658 6690 6 0 0 0 0 0 0 0 2 11 51 212 856 3402 Table 1. First values for the sequence r (n) where 0 n 12 and 0 r 6 I3412 ≤ ≤ ≤ ≤ Inthispaper,wesuggestanewapproachtostudythenumberofinvolutionswhichcontainthepattern 3412 exactly r times, namely r (n), which allows one to get an explicit expression for r (n) for I3412 I3412 any given r (see Table 1). More precisely, we present an algorithm that computes the generating function (x) = r (n)xn for any r 0. To get the result for a given r, the algorithm Ir Pn≥0I3412 ≥ performs certain routine checks for each element of the involutions . The algorithm has been 2r+1 I implemented in C, and yields explicit results for 0 r 6. ≤ ≤ 2. Recall definitions and preliminary results 2.1. The case r 1. Fix r 1. To any π we assign a bipartite graphG in the following way. n π ≥ ≥ ∈I The vertices in one part of G , denoted V , are the entries of π, and the vertices of the second part, π 1 denoted V , are the occurrences of 3412 in π. Entry i V is connected by an edge to occurrence 4 1 ∈ j V if i enters j. For example, let π = 8231376511112910414, then π contains 2 occurrences 4 ∈ of 3412,and the graph G is presented on Figure 1. π COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION 3 1 2 3 4 (8,13,1,7) 5 6 7 V V 1 8 4 9 (11,12,9,10) 10 11 12 13 14 Figure 1. Graph G for π =8231376511112910414 π LetGbeanarbitraryconnectedcomponentofG ,andletV beitsvertexset. WedenoteV =V V , π 1 1 ∩ V =eV V , t = V , t = V . e e e 4 4 1 1 4 4 ∩ | | | | e e e e Lemma 2.1. For any connected component G of G one has t 2t +2. π 1 4 ≤ e Proof. Assumetothecontrarythattheabovestatementisnottrue. Considerthesmallestnforwhich there exists π such that for some connected component G of G one has n π ∈I e t >2t +2. ( ) 1 4 ∗ Evidently, G contains more than one vertex,since otherwise t =1 andt =0, which contradicts( ). 1 4 ∗ Let l be theenumber of leaves in G (recall that a leaf is a vertex of degree 1). Clearly, all the leaves belong to V ; the degree of any oteher vertex in V is at least 2, while the degree of any vertex in V 1 1 4 equals4. Cealculatingthe numberofedgesinGbeytwodifferentways,wegetl+2(t l) 4t ,whiceh 1 4 − ≤ together with ( ) gives l >4, so there exist ateleast five leavesin V . In the case r =1 there only one 1 ∗ occurrence of length 4, so there no five leaves in V1, therefore weecan assume that r 2. ≥ Leta V andletusconsiderthefollowingcasescorrespondingtothenumberofleavesinV incident 4 1 ∈ to a: e (i) Ifaincidenttooneleavex V exactly,thenthegraphG′ whichobtainedfromGbydeleting 1 ∈ x and a satisfies t′ +1 = t and t′ +1 = t , hence bey ( ) we have that t′ e> 2t′ +3, a 1 1 4 4 ∗ 1 4 contradiction to the minimality of n. (ii) If a incident to two leaves x,y V exactly, then the graph G′ which obtained from G by 1 ∈ deletingx,y andasatisfiest′1+2=t1 andt′4+1=t4, hencebye(∗)we havethatt′1 >2t′4e+2, a contradiction to the minimality of n. (iii) If there exist four leaves incident to a, then the graph G does not connect component, a contradiction. e (iv) By Cases(i)-(iii) we can assume that every vertex in V incident to three leaves exactly. Con- 4 sider a,b V with the leaves a1,a2,a3 V and b1,b2,b3 V such that there exists a 4 1 1 ∈ ∈ ∈ vertex u V incident to a and b. Therefore, if we consider all the involutions π of length at 1 ∈ most 7 with two occurrences a and b of 3412 and the corresponding graph G is connected π 4 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION component, then we see that each involution has two occurrences x x x x and y y y y of 1 2 3 4 1 2 3 4 3412 such that x ,x ,x ,x y ,y ,y ,y = 2, a contradiction for that every vertex 1 2 3 4 1 2 3 4 |{ }∩{ }| in V incident to three leaves exactly (more precisely, in , k = 0,1,2,...,5, there no in- 4 k I volutions which contain 3412 exactly twice; in there exists one involution which contain 6 I 3412 exactly twice, namely 351624; and in we have 7 involutions which contain 3412 ex- 7 I actly twice, namely 1462735, 3516247, 3517264, 3614725, 3617524, 4261735, and 4631725. Eachof these involutions has two occurrences x x x x and y y y y of 3412suchthat there 1 2 3 4 1 2 3 4 x ,x ,x ,x y ,y ,y ,y =2). 1 2 3 4 1 2 3 4 |{ }∩{ }| Hence, using Cases (i)-(iv) we get the desired result. (cid:3) Denote by G1 the connected component of G containing entry 1. Let π(i ),...,π(i ) be the entries π π 1 s ofπ belongingtoG1,andletσ =σ bethecorrespondinginvolution(σ isaninvolutionforany π π ∈Is π involutionπ). We saythatπ(i ),...,π(i )isthekernel ofπ anddenoteitkerπ; σ is calledtheshape 1 s of the kernel, or the kernel shape, s is called the size of the kernel, and the number of occurrences of 3412 in kerπ is called the capacity of the kernel. For example, for π =8231376511112910414 as above, the kernel equals 81314,its shape is 3412, the size equals 4, and the capacity equals 1. The following statement is implied immediately by Lemma 2.1. Theorem 2.2. Fix r 1. Let π contain exactly r occurrences of 3412, then the size of the n ≥ ∈ I kernel of π is at most 2r+2. We say that ρ is a kernel involution if it is the kernel shape for some involution π. Evidently ρ is a kernel involution if and only if σ =ρ is an involution. ρ Let ρ be an arbitrary kernel involution. We denote by (ρ) the set of all the involutions of all s ∈ I I possible sizes whose kernel shape equals ρ. For any π (ρ) we define the kernel cell decomposition ∈ I as follows. The number of cells in the decomposition equals s s. Let kerπ = π(i ),...,π(i ); the 1 s × cell C =C (π) for 1 ℓ s and 1 m s is defined by mℓ mℓ ≤ ≤ ≤ ≤ Cmℓ(π)= π(j) iℓ <j <iℓ+1, π(iρ−1(m))<π(j)<π(iρ−1(m+1)) , { | } where i =n+1 and α =n+1 for any α . If π coincides with ρ itself, then all the cells in s+1 n+1 n ∈I the decomposition are empty. An arbitrary permutation in (ρ) is obtained by filling in some of the I cells in the cell decomposition. A cell C is called infeasible if the existence of an entry a C would ∈ imply an occurrence of 3412 that contains a, two other entries x,y kerπ, and another entry z of π. ∈ Clearly, all infeasible cells are empty for any π (ρ). All the remaining cells are called feasible; a ∈ I feasible cellmay, or may not, be empty. The setof all feasible cells aredistributed into three subsets: (i) Free-cells;afree-cellisafeasiblecellmay,ormaynot,becontainanoccurrenceofthepattern 12, or contain an occurrence of the pattern 21; (ii) Diagonal-decreasing-cells; adiagonal-decreasing-cellisafeasiblecellC = π ,...,π such ii { j1 jd} that π > >π where j < <j ; j1 ··· jd 1 ··· d (iii) Decreasing-cells; a decreasing-cell is a feasible cell C = π ,...,π with i = j such that ij { j1 jd} 6 π > >π where j < <j . j1 ··· jd 1 ··· d Consider the involution π = 8231376511112910414. The kernel of π equals 81314, its shape is 3412. The cell decomposition of π contains four feasible cells: C = 2,3 , C = 7,6,5 , 11 22 { } { } C = 11,12,9,10 ,andC = 14 ,seeFigure2. Allthe othercellsareinfeasible; forexample,C 33 44 21 { } { } is infeasible, since if a C , then aπ′ π′ π′ is an occurrence of 3412 for any π′ whose kernel is of ∈ 21 i2 i3 i4 shape 3412. The cells C , C , and C are free-cells, and C is diagonal-decreasing-cell. 11 33 44 22 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION 5 C C 14 13 42 43 12 C 11 10 8 32 9 7 C21 6 C24 5 4 2 3 C14 1 Figure 2. Kernel cell decomposition for π (3412). ∈I Given a cell C in the kernelcell decomposition, all the kernelentries canbe positioned with respect ij to C . We say that x=π(i ) kerπ lies below C if ρ(k)<i, and above C if ρ(k) i. Similarly, ij k ij ij ∈ ≥ x lies to the left of C if k < j, and to the right of C if k j. As usual, we say that x lies to ij ij ≥ the southwest of C if it lies below C and to the left of it; the other three directions, northwest, ij ij southeast, and northeast, are defined similarly. The following statement plays a crucial role in our considerations. Lemma 2.3. Let π (ρ). ∈I (i) C is infeasible cell if and only if C is infeasible cell. ij ji (ii) C is feasible cell with i=j if and only if C and C are decreasing-cells. ij ij ji 6 (iii) Let C be a feasible cell; if there exits northwest or southeast of C an occurrence of the pattern ii ii 12 in the kernel shape ρ, then C is diagonal-decreasing-cell, otherwise C is free-cell. ii ii Proof. (i) Holds immediately by the fact that π is an involution. (ii) Let i = j. Using the fact that π is an involution we get that C contains an occurrence of ij 6 the pattern 12 if and only if C contains an occurrence of the pattern 12. Thus, if C contains an ji ij occurrence of the pattern 12, namely xy, then C contains an occurrence uv of the pattern 12, so ji xyuv is an occurrence of the pattern 3412, a contradiction. Hence, C is feasible cell if and only if ij C and C are decreasing-cells. ij ji (iii) Let C be a feasible cell such that there exists northwest of C an occurrence of the pattern 12 ii ii in the kernel shape ρ, namely xy. So, if C contains an occurrence of the pattern 12 in C , say uv, ii ii then xyuv is an occurrence of the pattern 3412. Hence, C is diagonal-decreasing-cell. (cid:3) ii Similarly as the arguments in the proof of Lemma 2.3 we have the following result. Lemma 2.4. Let a<b. (i) If C and C are decreasing-cells then every entry of C is greater than every entry of C ; ia ib ia ib (ii) If C and C are decreasing-cells then the entries of C are lie northwest of the entries of C ; ai bi bi ib (iii) If C is decreasing-cell, then all the cells C , with i=j, which are lie northeast of C and C ab ij ab ba 6 are infeasible cells. As a consequence of Lemmas 2.3 and 2.4, we get the following result. Let us define a partial order ≺ onthesetofallfree-cellsbysayingthatCml Cm′ℓ′ =Cmℓ ifm m′ andℓ ℓ′. Similarly,wedefine ≺ 6 ≤ ≤ a partialorder ′ and ′′ on the set of alldiagonal-decreasing-cellsanddecreasing-cells,respectively. ≺ ≺ Lemma 2.5. , ′, and ′′ are linear orders. ≺ ≺ ≺ Lemmas 2.3–2.5 yield immediately the following two results. Theorem 2.6. Let G be a connected component of G distinct from G1. Then all the vertices in V π π 1 belong to the same feeasible cell in the kernel cell decomposition of π. e 6 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION LetF(ρ)(respectively;DD(ρ)andD(ρ))bethesetofallfree-cells(respectively;diagonal-decreasing- cellsanddecreasing-cellswhichlie abovethe diagonal)inthe kernelcelldecompositioncorresponding to involutions in (ρ) and let f(ρ) = F(ρ) (respectively; dd(ρ) = DD(ρ) and d(ρ) = D(ρ)). We I | | | | | | remark that, by Lemma 2.3 and Lemma 2.4 we get that d(ρ) is a nonnegative integer number. We denote the cells in F(ρ) by C1,...,Cf(ρ) (respectively; DD1,...,DDdd(rho) and D1,...,Dd(ρ)) in such a way that Ci Cj (respectively; DDi ′ DDj and Di ′′ Dj) whenever i<j. ≺ ≺ ≺ Theorem 2.7. For any given sequence α ,...,α of arbitrary involutions, and two sequences 1 f(ρ) β ,...,β and γ ,...,γ of arbitrary decreasing involutions (a decreasing involution of length 1 dd(ρ) 1 d(ρ) n is the involution n(n 1)...1), there exists π (ρ) such that the content of the free-cell Ci is − ∈ I order-isomorphic to α , the content of the diagonal-decreasing-cell DDj is β , and the content of the i j decreasing-cell Dj is γ . j 2.2. The case r = 0. First of all, let us describe the cell block decomposition of an involution π (3412) as follows. n ∈I Proposition 2.8. (see [8, Proposition 2.8]) Let π I (3412). Then one of the following holds: n ∈ (i) π =(1,α) where (α 1,...,α 1) I (3412), 1 n−1 n−1 − − ∈ (ii) there exists t, 2 t n, such that π =(t,α,1,β) where (α 1,...,α 1) I (3412) and 1 t−2 t−2 ≤ ≤ − − ∈ (β t,...,β t) I (3412). 1 n−t n−t − − ∈ Thus, the kernel cell decomposition of π (3412) can be defined as follows. There are two kernel n ∈ I shapes ρ1 =1 and ρ2 =21. In the case ρ1 there exists only one cell which is free-cell, and in the case ρ2 there exist four cells: two are infeasible cells (C and C ), and the others are free-cells (C and 21 12 11 C ), see Figure 3. 22 (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) C11 (cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)C2(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)1 (cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:0)(cid:1)C2(cid:0)(cid:1)2 (cid:0)(cid:1) C (cid:0)(cid:1)C(cid:0)(cid:1)(cid:0)(cid:1) 11 (cid:0)(cid:1)1(cid:0)(cid:1)2 (cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) Figure 3. Kernel cell decomposition for π (1) (21). ∈I ∪I 3. Main Theorem and explicit results Let ρ be a kernel involution, and let s(ρ), c(ρ), f(ρ), dd(ρ), and d(ρ) be the size of ρ, the capacity of ρ, andthe number of free-cells,diagonal-decreasing-cells,decreasing-cellsin the cell decomposition associatedwith ρ, respectively. Denote by K the set of all kernelinvolutions,and byK the set of all t kernel shapes for involutions in . The main result of this note can be formulated as follows. t I Theorem 3.1. For any r 1, ≥ f(ρ)  xs(ρ)  (3.1) (x)= (x) , Ir X (1 x2)d(ρ)(1 x)dd(ρ) X YIrj ρ∈K2r+2 − − r1+···+rf(ρ)=r−c(ρ) j=1  where r 0 for 1 j f(ρ). j ≥ ≤ ≤ Proof. For any ρ K, denote by ρ(x) the generating function for the number of involutions in ∈ Ir π (ρ) containing exactly r occurrences of 3412. Evidently, (x) = ρ(x). To find ∈ In ∩I Ir Pρ∈KIr ρ(x),recallthatthekernelofanyπasabovecontainsexactlyc(ρ)occurrencesof3412. Theremaining Ir r c(ρ) occurrences of 3412 are distributed between the free-cells of the kernel cell decomposition of − π. By Theorem 2.6, each occurrence of 3412 belongs entirely to one free-cell. Besides, it follows from COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION 7 Theorem 2.7, that occurrences of 3412 in different free-cells do not influence one another. Also, by Lemmas2.3and2.4thediagonal-decreasing-cellsdonotinfluenceoneanother,andfordecreasingcell C we have that C = C where C contains arbitrary decreasing involution. Therefore, ij ij ji ij | | | | xs(ρ) f(ρ) ρ(x)= (x), Ir (1 x2)d(ρ)(1 x)dd(ρ) X YIrj − − r1+···+rf(ρ)=r−c(ρ) j=1 andwegettheexpressionsimilarto(3.1)withtheonlydifferencethattheoutersumisoverallρ K. However, if ρ K for t>2r+2, then by Theorem 2.2, c(ρ)>r, and hence ρ(x) 0. ∈ (cid:3) ∈ t Ir ≡ Theorem 3.1 provides a finite algorithm for finding (x) for any given r 0, since we have to r I ≥ consider all involutions in , and to perform certain routine operations with all shapes found so 2r+2 I far. Moreover,the amount of search can be decreased substantially due to the following proposition. Proposition 3.2. Let ψ0 =21, ψ1 =3412, ψ2 =351624, and ψr =3 5 1 7 2 9 4 11...(2r+1) (2r 4) (2r+2) (2r 2) (2r) − − for all r 3. Then the only kernel involution of capacity r 0 and size 2r+2 is ψr. Its contribution to (x)≥equals x2r+2 r+2(x). ≥ Ir (1−x)rI0 This proposition is proved easily by induction, similarly to Lemma 1. The feasible cells in the corre- spondingcelldecompositionis: C isfree-cellifi=1,3,5,...,2r+1,2r+2,C isdiagonal-decreasing- ii ii cell if i=2,4,...,2r, and all the other cells are infeasible cells, hence the contribution to (x) is as r I described. By the above proposition,it suffices to searchonly involutions in . Below we present 2r+1 I several explicit calculations. 3.1. The case r = 0. Let us start from the case r = 0. Observe that (3.1) remains valid for r = 0, provided the left hand side is replaced by (x) 1; subtracting 1 here accounts for the empty r I − involution. Also, by Subsection 2.2 we have only two shapes ρ1 = 1 and ρ2 = 21 with s(ρ1) = 1, c(ρ1) = 0, f(ρ1) = 1, dd(ρ1) = d(ρ1) = 0, s(ρ2) = 2, c(ρ2) = 0, f(ρ2) = 2, and dd(ρ2) = d(ρ2) = 0. Therefore, we get (x) 1=x (x)+x2 2(x). I0 − I0 I0 Corollary 3.3. (see [14, Rem. 4.28]) The generating function for the number of involutions which avoid 3412 is given by 1 x √1 2x 3x2 (x)= − − − − . I0 2x2 3.2. The case r = 1. Let now r = 1. The involutions in are exhibited only one kernel shape 4 distinct from ρ1 and ρ2 which is ρ3 =3412,whose contributioIn equals x4 3(x) (see Figure 4). 1−xI0 (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)C(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)C(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)C(cid:0)(cid:1)(cid:0)(cid:1)C C11 (cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)CC12(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)11 (cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)CC12(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)22 (cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1) (cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)CC234(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)111 (cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)CC(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)432(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)222(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)CC(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)234333(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)CC(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)234444(cid:0)(cid:0)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1) C11 (cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)C(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)1(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)2(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)C(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)13(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)C(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1)14(cid:0)(cid:0)(cid:0)(cid:1)(cid:1)(cid:1) (cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1)(cid:0)(cid:1) Figure 4. Kernel cell decomposition for π (1) (21) (3412). ∈I ∪I ∪I Therefore, (3.1) amounts to (x) = x (x)+2x2 (x) (x)+ x4 3(x), and we get the following I1 I1 I0 I1 1−xI0 result. 8 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION Corollary 3.4. The generating function for the number of involutions which contain 3412 exactly once is given by 1 2x 1 2x 2x2 −1 (x)= − + − − 1 2x 3x2 . I1 −2x2(1 x) 2x2 p − − − 3.3. The case r =2. Letr =2. We haveto checkthe kernelshapes ofinvolutionsin . Exhaustive 6 I search adds one new shape to the previous list; this is ρ4 =351624. Calculation of the parameters s, c, f, d, dd is straightforward,and we get Corollary 3.5. The generating function for the number of involutions which contain 3412 exactly twice is given by 1 2x 1 6x+8x2+8x3 15x4 2x5+4x6 −3 (x)= − − − − 1 2x 3x2 . I2 2x2(1 x) − 2x2(1 x)2 p − − − − 3.4. The cases r =3,4,5,6,7. Let r =3,4,5,6;exhaustive searchin , , , and reveals 2, 8 10 12 14 I I I I 5, 12, 25, 48, and 100 new kernel shapes, respectively, and we get Corollary 3.6. Let r=3,4,5,6,7. Then the generating function for the number of involutions which contain 3412 exactly r times is given by 1 1 1−2r (x)= F (x)+ G (x) 1 2x 3x2 , Ir 2x2 r 2x2 r p − − where (1 x2)F (x) = (1 2x)(1+x+x2), 3 − − − (1 x2)F (x) = 1+3x+4x2 8x3 2x4, 4 − − − − (1 x2)F (x) =3 7x 7x2+12x3+6x4, 5 − − − (1 x2)2F (x) = 5+9x+21x2 25x3 34x4+16x5+24x6 2x7 2x8, 6 − − − − − − (1 x2)2F (x) =7 11x 28x2+20x3+54x4 2x5 46x6+2x8, 7 − − − − − and (1 x)2G (x) =1 8x+18x2+x2 29x4 12x5+14x6+41x7+2x8 18x9, 3 − − − − − (1 x)4G (x) =1 14x+71x2 124x3 166x4+874x5 624x6 1332x7+1909x8 4 − − − − − − +426x9 1585x10+292x11+400x12 126x13, − − (1 x)4G (x) = 3+46x 267x2+627x3+134x4 3321x5+3954x6+5214x7 5 − − − − 11775x8 2186x9+14525x10 1701x11 8824x12+1537x13 − − − − +2594x14 216x15 324x16, − − (1 x)6G (x) =5 94x+712x2 2582x3+3124x4+8364x5 31620x6+15464x7 6 − − − − +77508x8 107098x9 76814x10+214160x11+5782x12 231050x13 − − − +62700x14+146176x15 65653x16 50328x17+29646x18 − − +6462x19 5346x20+486x21, − (1 x)6G (x) = 7+144x 1210x2+5020x3 8206x4 12180x5+69464x6 7 − − − − − 54210x7 181468x8+315366x9+239852x10 779338x11 − − − 124766x12+1226006x13 168810x14 1272344x15+418555x16 − − − +813368x17 373802x18 279554x19+153648x20+37188x21 − − 23166x22+486x23. − COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION 9 4. Further results As an easy consequence of Theorem 3.1 and Corollary 3.3 we get the following result. Corollary 4.1. Let r 0, then (x) is a rational function in the variables x and √1 2x 3x2. r ≥ I − − Another direction would be to match the approach of this note with the previous results on even (odd) permutations which contain 132 exactly r times (see [19]). We denote the generating function for the number of even (resp. odd) involutions in which contain r occurrences of 3412 by E (x) n r I (resp. O (x)) (see Table 2). r r n 0 1 2 3 4 5 6 7 8 9 10 11 12 \ 0 1 1 1 2 3 11 31 71 155 379 1051 2971 8053 1 0 0 0 0 1 5 14 30 82 320 1213 3895 11141 2 0 0 0 0 0 0 0 0 11 95 439 1463 4407 3 0 0 0 0 0 0 1 4 11 29 104 396 1486 4 0 0 0 0 0 0 0 0 14 108 321 1612 4782 5 0 0 0 0 0 0 0 0 6 60 275 878 2247 6 0 0 0 0 0 0 0 0 1 21 122 446 1504 Table2. Numberofeveninvolutionsin whichcontain3412exactlyrtimeswhere n I 0 n 12 and 0 r 6. ≤ ≤ ≤ ≤ We define N (x)=E (x) O (x) for any r, that is, r r r − N (x)= ( 1)21(π)xn, r X X − n≥0 π∈In contains 3412 exactly r times where 21(π) is the number of occurrencesof the pattern21 in π. Using the arguments in the proof of Theorem 3.1 we get the following result. Theorem 4.2. For any r 0, ≥ ( 1)21(ρ)xs(ρ)(1+x)dd(ρ) f(ρ)  (4.1) N (x) δ = − N (x) , r − r,0 X (1+x2)d(ρ)+dd(ρ) X Y rj ρ∈K2r+2 r1+···+rf(ρ)=r−c(ρ) j=1  where r 0 for 1 j f(ρ), δ =1, and δ =0 for all r 1. j 0,0 r,0 ≥ ≤ ≤ ≥ As an easy consequence of Theorem 4.2 we get the following result. Corollary 4.3. Let r 0, then N (x) is a rational function in the variables x and √1 2x+5x2. r ≥ − Clearly, 1 1 (4.2) E (x)= ( (x)+N (x)) and O (x)= ( (x) N (x)), r r r r r r 2 I 2 I − for all r 0. Hence, Corollary 4.1 and Corollary 4.3 give the following result. ≥ Corollary 4.4. For any r 0, the generating functions E (x) and O (x) are rational functions in r r ≥ the variables x, √1 2x 3x2, and √1 2x+5x2. − − − 10 COUNTING OCCURRENCES OF 3412 IN AN INVOLUTION Hence, Theorem 4.2 and Theorem 3.1 provide a finite algorithm for finding (x), N (x), E (x), and r r r I O (x) for any given r 0, since we have to consider all involutions in , and to perform certain r 2r+2 ≥ I routine operations with all shapes found so far. Moreover, the amount of search can be decreased substantially due to the following proposition which holds as easily consequence of Proposition 3.2. Proposition 4.5. Let ψ0 =21, ψ1 =3412, ψ2 =351624, and ψr =3 5 1 7 2 9 4 11...(2r+1) (2r 4) (2r+2) (2r 2) (2r) − − for all r 3. Then the only kernel involution of capacity r 0 and size 2r+2 is ψr. Its contribution to N (x)≥equals ( 1)r+1x2r+2(1+x)rNr+2(x). ≥ r − (1+x2)r 0 By the above proposition, it suffices to searchonly involutions in . Similarly as our calculations 2r+1 I for (x) where r =0,1,2,3,4,5,6,7with using Theorem 4.2 we get the following result. r I Corollary 4.6. Let r=0,1,2,3,4,5,6,7. Then the generating function N (x) is given by r 1 1 1−2r N (x)= P (x)+ Q (x) 1 2x+5x2 , r 2x2 r 2x2 r p − where P (x) =x 1, 0 − (x2+1)P (x) =(x+1)(2x2 2x+1), 1 − (x2+1)2P (x) =(x 1)(2x2 2x+1)(1+x)2, 2 − − (x2+1)3P (x) =(2x2 2x+1)(x6+x5+3x4 2x3 x2+x+1), 3 − − − (x2+1)4P (x) =(1 x2)(2x8 2x7+10x6+x5+15x4 12x3+12x2 3x+1), 4 − − − − (x2+1)5P (x) = 4x13 14x11+5x10 33x9+29x8 16x7+34x6 42x5+14x4+6x3 5 − − − − − 15x2+7x 3, − − (x2+1)6P (x) = 6x16+6x15 44x14+58x13 128x12+163x11 195x10+271x9 221x8 6 − − − − − +188x7 170x6+160x5 82x4+27x3+9x2 9x+5, − − − (x2+1)7P (x) = 14x18+12x17 80x16+94x15 176x14+212x13 188x12+247x11 7 − − − − 157x10+35x9 51x8+28x7+62x6 142x5+102x4 49x3 3x2+11x 7, − − − − − − and Q (x) =1, 0 (x2+1)Q (x) =(x2 1)(4x2 2x+1), 1 − − (x2+1)2Q (x) =(22x6 58x5+69x4 48x3+22x2 6x+1)(1+x)2, 2 − − − (x2+1)3Q (x) =(x 1) 100x12 18x11+323x10 507x9+491x8 182x7+52x6 14x5 3 − (cid:0) − − − − +46x4 34x3+19x2 5x+1 , − − (cid:1) (x2+1)4Q (x) = (1+x) 650x16 1880x15+5992x14 9143x13+13671x12 19666x11 4 − (cid:0) − − − +26606x10 28683x9+24771x8 16778x7+9158x6 3969x5+1385x4 374x3 − − − − +78x2 11x+1 , − (cid:1) (x2+1)5Q (x) =(1 x) 5000x21 4650x20+24624x19 25585x18+76987x17 95269x16 5 − (cid:0) − − − +127936x15 140244x14+169896x13 159580x12+119898x11 51878x10 − − − 84x9+26302x8 26778x7+17822x6 8604x5+3270x4 940x3+209x2 − − − − 31x+3 , − (cid:1)