Permutations with prescribed pattern

  • Published on
    15-Jun-2016

  • View
    220

  • Download
    0

Transcript

Permutations with prescribed pattern *) By L. CARLITZ, Durham (U.S.A.) (Eingegangen am 17. 3. 1972) 1. Introduction. LetZ, = (1, 2, . . . , n> and let n = (a l , a 2 , . . ., a,) denote an arbitrary permutation of Z,L. Let k, , L,, . . . , kfib be positive integers such that (1.1) k, + k2 + + k, = n. We shall say that the permutation n has pattern [k17 k , , . . ., k,] if the following conditions are satisfied : (1.2) and UI < a2 < . * < akI; a k l + l < nklt2 < * - . < ak l+kZ; . * .; akl+ ... + E , - i + l < * * * < a, (1.3) ukf akl+l akl+k2 > a k l + k a + l , * . We may represent z graphically: Thus for example the graph represents the pattern [4, 1, 4, 1, 1, 21. The graph with pattern [2, 2, 2 , 2 , 21 represents a so-called up-down permutation. We let A ( k i , k 2 , . . ., k,) denote the number of permutations of 2, with pattern [k, , k,, . . . , k,]. The first main result of the present paper follows : Put (k l + b + * * * + k m ) ! ki! kz! * * * k,! (hi, k,,. . ., Ic,) = 1) Supported in part by NSF grant GP-17031. 32 Carlitz, Permutations with prescribed pattern Then 112 A ( k 1 , h , . . ., k,) == C (- l ) " -"Sr , r = l (1.4) where E m = ('1, h, . . .> km) f 4 - l = ( k , + k , , k , , * . . > k,) + (h, 4 + k , , k,, . . ., k, + . , . i- k l , k?, * . - > k7n-2, km-1 + km) and generally (1.5) 8, = c (81 , 8 2 , . . . > S , ) . s1 = k, + where + k,,, 82 = kj l+ l + * * * + kj2, . . . , 8" = k,r-l+l + * * ' i- kjr and the summation in (1.5) is over all j , , j , , . . . , j , satisfying 1 5 j , < j , < - * - < j , = 92%. While t.his result theoretically enables one to compute A (k i , k , , . . . , km) in all cases, i t is unfortunately rather complicated. The remainder of the paper is concerned with the construction of generating functions in certain special cases. I n the first place, if f(n, nl) C A ( h , k2, . . ., k , ) , ki+ . . . +BW-?i (1.6) kt >o we show that It follows that f(n, m) is equal to the EULERian number A,,,, which enu- merates the number of permutations of 2, with m rises [3, Ch. 81. Thus this result can be thought of as a partial check of the general formula (1.4). I n the next place, if we put g ( n , 9%) = 2 A ( k 1 , k2, . . - , k m ) , kit ... +kwL=7t kt>l (1.8) then where M, B are the roots of x2 - x + y = 0. Now the EULERian number An,k can also be defined by Carlitz, Permutations with prescribed pattern 33 where - A(') 8) = A r + s + i , s + i - A r + s + i , r + i == A(', '1. This suggests that we define the array of numbers A(r, s) by means of Then n - 2 s n - m - s m g ( n , m) = C (- I),-' - A(n - 8,s) s = o n - m - s ( m - s ) (2 m < n), m g ( 2 m, m) = c (- 1)"-SA(2 m - 8, s) . s = o The numbers A ( r , s) and A(', s) are closely related; see (8.9) and (8.10) below. Finally we consider the case Then we show that 00 -.mk J, (1.10) 2 A,(m k) - = {F,(x))-l, ?n=O (m I c ) ! where M -FI,(X) = c (- 1)' r(, j = O ( j k ) ! . Moreover if we put where 00 ..ik+t &-- Fk, t (x) = C (- I)' ___- j = O ( j k + t ) ! * These results, (1.10) and (1.1 1), evidently generalize the known results for up-down permutations [J], [ 2 , pp. 105-1121. 3 Math. Nachr. 1973, Bd. 58, H. 1-6 34 Carlitz, Permutations with prescribed pattern 2. M \Te begin with the case ? ) L = 2. Froin the pattern it is clear that (2. 1) since the ele~nent 12 is situated at one of the peaks. Moreover it is evident that A (k1, k.) = (kl 1 1 + A ( k , , k 2 - 1) (k2 > I ) , (2.3) A ( k , , 1) = k, ( k , 2 l ) , since there are precisely k , elements that may be placed i n the extreme right hand position. For a like reason we have also Indeed (2 .1) also holds when k , = 1. 12.3) A(1, k2) = k2 (k2 2 1). In the next place we have, for 7 ) ~ 2 3, k, + k, - (2.5) A(k1, k , , k3) = (I + k ; + k , l ) k J + ( k 1 - k 2 - k 1 - ) A ( k , , k 2 - 1) + A ( k , , k 2 , k , - 1) ( k , > l , k 3 > 1 ) . Indeed if the element rL is at the left hand peak, we get the first product on the right of ( 2 . 5 ) ; if it is at the second peak, we get the middle product; if it is at the extreme right, we get the third term. Then, by (2.4), A ( k , , k2, k,) - A(li1, k ? , kj - 1) k , + k2 + k , - = ( k2 -+ k3 h.9 + k3 - 1) [ ( h + k z - 1) - 1] k , Carlitz, Permutations with prescribed pattern 35 Simplifying we get (2.6) (k + k2 + b)! k,! kl! kj! A ( k , , k,, k3) = - ~ -~ - 36 Carlitz, Permutations with prescribed pattern It will be convenient to use the notation We have seen above that - (k l+ kz) = ( k , . k,, 1) - ( k , , x.2 + 1) - (k, + k , , I ) + 1, so that (2.8) holds for k2 > 1, k,; = 1. For k, = 1, in place of (3.5) we iiare + kJ k , + A ( k l , 1, k , - 1) (k, > 1). (B, 1 ) (2.9) A ( k , : 1, k,) = Hence = (4 , 1, k3) - $ 1 , k3 + 1) - (El + 1, 4) + 1. It follows that (2.8) holds for all positive k l , k 2 , k,. Carlitz, Permutations with prescribed pattern 37 3. We now take m = 4. Then, to begin with, we have the recurrence 38 Carlitz, Permutations with prescribed pattern 4. Carlitz, Permutations with prescribed pattern 39 We show first that where sl, s2 , . . ., s, are defined by (4.2) and (4.3). the general case. Thus we shall prove It will suffice to prove (4.5) when m = 3 as the method is the same in (4.6) where of course (kl, k2 > k3) = A (kl k2 > k3) + A (kl 9 k, + k3) + A (kl + k2 9 k,) + 4 k i + k; + JCd. A(kl + kz + k3) = 1. To prove (4.6) we partition 2, = (1, 2,. . ., n} (n = k1 + k2 + k3) into three sets Ii, = (al > . * . > u2 = (b, 9 . * . > bk2)' u3 = (%, . * - > ckJ) * This can be done in (k,, k2, k3) ways. We assume that the elements of U 1 , U 2 , U3 are numbered so that < a2 < ' ' ' < a k l ; b , < b, < ' . ' < b&; c1 < c2 < ' ' < ckJ. If akl > b l , bkz > c l , the partition corresponds to a permutation with pattern [ki . k 2 , k3]. If ak, > bt , bka < cl, we have the pattern [k,, k, + hJ. If ak, < bl , b k Z > c2 we have [kl + k2, k3]. Finally if ak, < b, , bkl < c, we have [k, + k, + k3]. Moreover in each case the correspondence is one to one. This evidently proves (4.6). It should be noted that (4.5) holds for (4.7) k, 2 1, k2 2 1,. , . , E m 2 3 It remains to show that (4.5) implies (4.i). To do this we prove the following gn (x, , . . . , 2,) be arbitrary (real-valued) functions. Define emm ma. Letf1(x,), f%(XI,X2), . . . , f r l ( x , , . . . , x,J, g i ( x l ) , g ~ ( ~ ~ , x p ) , . . . , j1,j2,. . .?jr; 8 1 ~ ~ 2 , . . ., 8, by means of (4.2) and (4.3). Then m r = l q(k1, . . ., k,) = 2 f (si, . . . , s,) (nz = 1, 2 , . . . ,n) (5.1) 40 Carlitz, Permutations \I itli prescribed pattern It is easily verified that ( 3 . 6 ) and ( 5 . 6 ) are equivalent. For the general case we require some additional notation. Let ( 5 . 7 ) 1 I - t , < t , < * * < t , = r and put GI = 8, + . * * , St, , 51 = St,> 1 + - * * + Stz' (5.8) . . ., 0-fi = S ( l I - I L 1 + - * * + Stn , so that G, , . . . , G~ are related t o ,sl, . . . , s, as s J , . . ., s, are related to k , > * . * , k,,$. Carlitz, Permutations with prescribed pattern 41 Now it is easily verified that the number of r-tuples (sl, . . ., sr) is ). Similarly t,he number of R-tuples (bl, . . . , bR) obtained m - 1 r - 1 equal to ( from (5.7) and (5.8) is equal t o (L 1 ). In order to show that (5.1) implies (5.2) we substitute from (5.1) into (5.2). Then for a fixed R-tuple (u i , . . . , uB) we get the coefficient The sum on the right vanishes unless m = R. This completes the proof of the implicat,ion (5.1) + (5.2). The proof of (5.2) r==. (5.1) is exactly the same. As a variant of the above proof, we define (5.9) 1 > ~ r ) > (5.10) G r ( k , , - . ., = C g ( s , , . . ., S T ) , Fr (ki > . * . > k,) =z CfCsl> . where the summations are over all (sl, . . ., sr) that satisfy (4.2) and (4.3). It can be verified that which is the same as It is familiar that (5.11) is equivalent to For r = m, we have Fm = f ( k t , * . - 9 km), 2 g(kr, - - 9 km) and the equivalence of (5.1) and (5.2) follows at once. 6. We shall now discuss some applications of (4.1). It will be convenient to change the notation slightly. Put nz A ( k l , kp, . . . ) k,) = C (- I),-, 'r7 r = 1 (6.1) 42 Carlitz, Permutations with prescribed pattern where ( 6 . 2 ) 8, = c (s1,s?_, . . ., s,), SI = kl -+ . . * + kj . , , = kj ,+i + * * + + kj ,+ ia , . . . > S, == kjl+ ... + j , - l + l + . * + kj ,+ . . .+j , , and the summation is over all j , , . . . ~ j , such that j , + j ? + - . * + j , = m, j , > 0 , j, > 0, . . . , j, > 0 . As a first application we consider the sum f(n, nz) = c A(X.1. k ? . . . ., k,, ,) , !I ,I = I 1 kl -. . .- (6.3) where the summation is over all positive k, , . . . , k,, such that kt>0 k , + * * f k,,, = 7 1 . We construct the generating function Then by (6.3) I\;ow apply (6 .1) . Since the number of positive solutions of x., + . . + k . = Carlitz, Permutations with prescribed pattern 43 Hence so that We recall that the so-called EuLERian numbers may be defined by Moreover is the number of permutations of 2, with k rises [3, p. 2141. By a rise in the permutation (a l , a 2 , . . . , a,) is meant a pair aj, ul+ with u j < aj+i; also a conventional rise is counted to the left of ai. Comparison of (6.6) with (6.7) gives (6.8) f(n, m) = Returning t o (6.3), the function f ( n , m) is equal to the number of per- mutations with k , + * - * + k , = n. Clearly the number of rises (plus the conventional one) in a permutation of pattern [ k , , . . ., k,] is equal to m I + z ( k j - l ) = n - m + I i=i Since An,, = A n , n - r n + i 7 we again get (6.8). the general formula (6.1). Thus the known result concerning A,,m furnishes a, partial check on 7. As a second application of (6.1) we take 9(% m) = 2 A ( k , : . . - 3 k?).J? kl+.. . + k , = n ki>l (7.1) where now each E , > 1. Thus the pattern has the appearance 44 Carlitz, Permutations with prescribed pattern P u t ,& f. ' . +k, M C c = /JJ y"L r A (K,, . * . , k,,,) - - _ _ _ _ - ~ ( k , + * * * + k,) ! * 2 l l L = I t l , . . ., k , 5 2 Since the number of solutions of is equal to me get c= c . (S) s1,. . . , S r = 2 We rexrite ( 7 . 2 ) as Clearly Cnrlitz, Permutations with prescribed pattern 45 If we put it is easily verified that M i Since - 1 ___- - l - z f y x 2 x2 - x + y = 0, where u, are the roots of it follows that Thus and ( 7 . 3 ) becomes Finally therefore Now it can be shown that the EuLERian numbers An.k defined by (6 .7 ) also satisfy 46 Carlitz, Permutations with presrribed pattern where A ( r , s ) A r + s + l , s - i = A r , s c l , r + 1 = A(s, r ) . This suggests that we define an array of numbers B(r, s) by means of Clearly d ( r , s) =A(& T ) . By (7.6) and (7.8) Since it follows that Thus (5.9) becomes Carlitz, Permutations with prescribed pattern 47 S48 Uarlitz. Permutations with presrrlbed pattern This can be described l.)y saying that TC has only I-inclines and 2-inclines. More precisely if x has 712 inclines then z has exactly 7% - 1 1-inclines. It follows that the number of periiiutatioiis with t 1-inclines and s %inclines is equal to g ( r + 2 s. r - 1). 8. Put and let H,. H , denote partial derivatives. It can be verified that n y ( . ~ - y) ( e r - e) (.r e - y e r ) 2 T H , ~ f y H , -1 and so that (8.2) (8.3) It is clear frolii (7.8) thnt r ( 1 - y) H,r 2- y ( l - 2 ) H , = .LyH. d ( r . 8 ) = r q r , s - 1) A . s d ( r - 1, s ) Compariiig (8.2) with (7.8) we get the ierurrence - + (1. + s - I ) & r - 1, s - 1) ( r 2 1, s 2 1). (8.4) A ( r , 0) =A((); r ) = 0 ( r > O ) , while J ( 0 , 0) = 1. For s = 1, (8 .3) reduces to so that (8.5) A(r, 1) = d ( l , r ) = 1 ( r 2 1). The first few values of &$(r. s) are easily computed by means of (8.3). d ( r , 1) = A ( , - 1 . 1) + r 3 ( r - 1, 0 ) ( 7 1 11, - 1 1 1 1 2 1 7 1 9 1 21 21 1 44 1 51 161 51 1 265 The numbers in the right hand column are obtained by summing in the rows. Since Carlitz, Permutations with prescribed pattern 49 where is the number of derangements of Z,, i t follows that n , rA(n - s, s) = Dn. s = o (8.6) I n the next place, i t we take y = - x, (8.1) becomes where En denotes the EULER number. On the other hand, by (7.8), M xr + s H ( x , - x) = 2 ( - 1)8A(r, s) ~- r ,s=O ( r + s)! r(i = c - P (- I)sA(n - s, s ) n=O n ! s% so that n 2 (- i)'B(n - S, S) = E,. s =o (8.7) Therefore, by (7.11) and (8.7), we get (8.8) g(2 m, m) = (- E2m. This is a known result for the number of up-down permutations of Zlr,& The number A(r, s) can be expressed in terms of EuLEItian numbers. PI, PI. Indeed by (7.7) and (7.8) we have It follows that and (8.10) A ( r , s ) = (- l)'-j( r + s ) A ( r , j - 1 ) . j=i 4 Math. Nachr. 1973, Bd. 58, H. 1-6 50 Carlitz, Permutations with prescribed pattern 9. The numbers A(r, s ) defined above were introduced by ROSELLE [4] in an entirely different setting. A succession in a permutation (a,, a2 , . . . , a,) is apair a,, witha,_, = n, + 1. Forexample23145 hastwo successions. Let P(n, r: s) denote the number of permutations of 2, with r rises and s successions. It js proved that n - I (9.1) P(n , r , s ) = ( ) P(n - s, I' - s, 0) . Put, P(n, r ) = P(n, r , 0) . Clearly r - I (9.2) 2 P(., r , s) = A,,, , s =o the EULERIAX number. Coinbining (9.1) with (9.2) we get which is equivalent to Also i t is proved that (9.5) P ( n + 1: r ) = rP(vb: r ) + (n - r + I ) P(n , r - 1) + (?L - 1) P(n - I, r - I ) . If we define P* (12, r ) by iiieans of i t follows from (9.5) that (9.7) P * ( ~ L + I; Y) = rP*(n, r ) + ('R, - r + I) P*((n, P - i) .+ ?ZP*(?L - 1, r - 1). Comparing (9.7) with (8.3), we get (9.8) B(r, s ) = P*(I' + s, r ) . Finally we may state the following conibinatorial interpretation : P* (n, r ) is the number of permutations of Z,, with r rises, no successions and ai > I. Carlitz, Permutations with prescribed pattern 51 10. Returning to (6.1), we now consider the case (10.1) It is convenient to put (10.2) Then by (6.1) we have k I - - * . . = k, = k. A, (m k) = A, (k, Ic, . . . ) k) . A,(m k) = 2 (- m (10.3) C (jl k) j , k . . . j , 4 . r = l j l + . . . + j , = m j S > O It follows from (10.3) that Therefore (s k) ! M Xmk M (10.4) 1 + 2 A, ( m k ) ~ = {c (- 1)' m=l (m A ) ! s = o For k = 2 , (10.4) is in agreement with (8.8). For k = 1, (10.4) beconies -1 m=O Do m = l so that (10.5) Al(m) = 1 (m = 1, 2 , 3) . . .). This is also evident from the definition of A , (1, 1, . . . , I ) . 4* 52 Carlitz, Permutations with prescribed pattern By (6.1), (10.5), is equivalent to the identity m (10.6) C (- l),-' C (.A, j,, . . . , j r ) = 1 (m 2 1). r = l jl + . . . + j T = m j ,>O We remark that (10.7) 2 2 1 = 2"-' (m 2 1). r = 1 j l + . . .+jr =m j c - 0 In the next place we consider permutations with pattern (10.8) k 1 - - = km = k, km+l = t (k 2 1, t 2 1) (10.9) A,(mk + t ) = Am+i (k, * * ., h, t ) . A,(m k + t ) = c (- l ) m - r + l x c ( j l k , . . . , j r - l k , ( j r - W + t ) ' By (6.1) we have m + l r = l jL+. . . + j r=m+ 1 j,>O This holds for m 2 0. Then m Xmk+t C A , (m k + t ) m=O (m k + t ) ! 00 ,mk+t m + l and therefore ca xmk + 1 (m k + tj7 (10.10) (m k + t ) m=O Carlitz, Permutations with prescribed pattern 53 This result can be written more compactly by making use of the OLIVIER functions Do &k+t Fk) (x) = c (- 1)j -7- -- ( t = 1, 2, 3, . . .). (3 k + t ) ! t j= 1 Then (10.10) becomes while (10.4) is simply Do ,.mk rl, (10.12) c A, (m k) ~- = k (P) (.))-I. ?n = 0 (rn k) ! As a numerical check, when k = 3, (10.12) gives A3 (6) = 19. The permutations with pattern [3, 31 are the following 124356 145236 246135 125346 146235 256134 126345 156245 345126 134256 234156 346125 135246 235146 356124 136245 236145 456123 245136 References [l] R. C. ENTRINGER, A combinatorial interpretation of the EULER and BERNOULLI [2] E. NETTO, Lehrbuch der Combinatorik, Leipzig und Berlin, 1927. [3] JOHN RIORDAN, An Introduction to Combinatorial Analysis, New York, 1958. [4] D. P. ROSELLE, Permutations by number of rises and successions, Proc. Amer. Math. numbers, Nieuw Arcbief voor Wiskunde (3), 14, 241-246 (1966). SOC. 19, 8-16 (1968).

Recommended

View more >