Permutations with Prescribed Pattern. II. Applications

• Published on
15-Jun-2016

• View
218

Math. Xachr. 83,101-126 (1978) Permutations with Prescribed Pattern 11. Applications By L. CARLITZ of Durham (U.S.A.) (Eingegangen am 5.1.1976) 1. Introduction and summary. LetZM = { 1,2, . . . , n} and let 1~ = (ai, a2, . . . , a,) denote an arbitrary permutation of 2,. Let k, , k,, . . . , k, be positive integers such that (1.1) k l + k 2 + . . .+k,=n. Thepermutation ~d will be said to have the pattern [k,, k, . . . , k,] if the following conditions are satisfied : (1 4 al-=al102 Carlitz, Permutations with Prescribed Pattern For brevity put (k i , k2, . (k l+ka+. - - + k m ) ! - 9 k,) = k l ! kz! . . . k,! * Then m r = i A ( k i , kq, . . , k,)= C 8, 9 (1.4) where (1.5) ST = 2 ( s i , ~ 2 , * * * 9 8,) and (1.6) s , = k l + . .+kj i , sz=kji+i+- - *+kji+jz 3 . - 3 S r = k j i s ...+ j , - i+ i+* . .+ kii+ ...+ i, and the summation in the right member of (1.5) is over all ji, . . . , j, such that (1.7) j,+j,+. . .+j,=rn, j I > O , j2>0 , . , . , j , > O . This result theoretically enables one to compute A(ki, k2, . . . , kr) for arbit- rary ki. However i t is rather complicated and so not really satisfactory. Thus it seems of interest to see what can be done in special case?,. A number of examples are worked out in [Z]. In the first place it is shown that if f(n, m)= c A(k1, * - - f km) , E l + ...+ km=n kp- 0 (1.8) then f (n, m) is equal to the Eulerian number An,, which enumerates tho number of nEZ, with m rises. (1.9) Next put g(n, m)= A(kL, - . . , k,) . k1+ ...+ k,=n R p l It was proved that where a, /3 are the roots of x%--z+y=O. The EuLERian number An,, satisfies [4] ex - e - xyS r.s=O (r+si- i ) ! xeu-yex m c A ( ? , 8 ) where A (9 8) = A , +s+i,s+i =A, +s+i,r + I = A (8, ) * This suggests defining the array of numbers A(?, s) by means of Carlite, Permutations with Prescribed Pattern 103 It t,hen follows from (1.10) that ffl g (n,m)= E ( - I ) ~ - ~ - - - g(2m, m) = C ( - I ) " - ~ A(% -8, s) . A(n-s, 8) (2rnK.n) s=O ffl e = o (1.11) Finally it was proved in [2] that if A,(mk)=A,(k,k, . . . , k ) , then x d 1 (1.12) i A k ( m k ) - - f f l = O (mk)! E',(z) ' where Moreover if A, (mk+t)=A,+,(k, k , . . . , k , t ) ( t z l ) , then ( t Z 1 ) ' F,,t (4 - x7nk +t (1.13) A , ( m k f t ) -- - =--- f f l =o (mk + t ) ! FJT) For another proof of (1.12) and ( 1.13) see [ 11. types. In the present paper we give some additional applications. These are of two I. Let t be a fixed integer z2 and put ft(n, m ) = C A(k,, h, . . - hffl) , k l +... +t, =n kd Zt so that ft(n, m) is the number of permutations of 2, with m inclines and the number of nodes in each incline zt; also put - xn I?,(% y) = 1 + c -- 2 ft(n, m ) y" * ,=t n! o c t m s n We show that where d(x, y), D(z, y) are determinants of order t defined by A(z,y)=lai- ' l ( i , j = ~ , z , . . . , t ) , 104 Carlitz, Permut$tions with Prescribed Pattern D(x, Y) = e 9 x . . . UI uz . . . ut a: u; ...lg . . . . . . . . . . . . &' ut- l ut - 1 t 1 '' . . . and ul, uz, . . . , ut are the ro0t.s of z L z t - i + y = o . For t = 2 , it is easily verified that (1.14) reduces to (1.10). [ k j , k2, . . . , k,], where Also if fJn,m) denotes the number of permutations of 2, with pattern k i s t , . . . , k m - l S t , kmSS ( t ~ 2 , S Z ~ ) , we evaluate the generating function m The results are contained in Theorems 2 and 3 below. 11. P u t 9 t h m)= z k2, * * 9 km) 7 kl+ ...+ k , =n k i ~ 0 ( 1 ~ 1 o d t ) , k i > 0 so that ga(n, m ) denotes the number of permutations of 2, with m inclines and tho number of nodes on each incline is a multiple of t ; also put We shall show that ( t z 2 ) , I-Y (1.15) Gt(z , y) 1 -!I%@ (1 -Y)I") where W e also evaluate the generating function - ,nt-j n where g l t - j (nt - j , m ) denotes the number of permutations of Zn2-+ with pattern [k,, k2, . . . , k,], where ki=O (modt) ( l ~ i - = m ) ; k , r -j ( m o d t ) . See Theorem 5 . Carlitz, Perniutations with Prescribed Pattern 105 Xote that for t = l , the generating function on the right of (1.15) reduces to where, as above, the An,m are the EuLERian numbers. in$3 6, 7 below. Let We show that f(n, m ) , g(n, m ) satisfy the mixed recurrences The case t=2 of I1 is of special interest and is examined in greater detail f(n, m) = g h m), g(n, m ) =g2,J2n-- 1, m) . f(n, m)'=(n-m+1)g(n,m- l )+mg(n,rn) 1 g ( n f 1, m)= (n-m+ 2) f(n, - 2) + (n+ 1) f(n, m - 1) +mf(n, m ) , by means of which the enumerants can be computed. We show also that m 2 = O m ! g(n, n-m)= c (-l)Q&) A ( 2 n + m - j - l ) , X" - where 2 A(?%) -=see z+tan x n=O a ! and Pm,?(n), Q,n,j(n) are polynomials in n of degree j. Finally (Theorem 8) we obtain explicit formulas for f(n, m ) and g(n, m). 2. kj z t. As above let t z 2 and put (2.1) ft(n, m)= 2 kZ, - . , km) where the summation is over all ki satisfying (2.2) k l + k 2 + . . . + k m = n ; k i z t ( i = l , 2 , . . . , m ) . We also define (2.3) - Xn pt't(z, Y) = 1 + c 7 c f t h m ) I" n=t ~ < t m s n In order to evaluate Ft (2, y) we apply (1.4) and (1.5). Since the number of solutions k l , k,, . . . , kj of is equal to kl+k?+. . .+k j=s , k i z t , . . . , k i s t s - ( t - 1 ) j - 1 ( j - 1 i t follows that m 106 where Carlitz, Permutations with Prescribed Pattern j-1 The double sum where It follows from (2.8) that Now let ui, u2, . . , , ut denote the roots of (2.7) zt-zI-1 +y=O, so that 1 -z+y2=(1 -u& (1 -u22) . . . (1 -utz) . If we put where the A, are independent of z , then Alternatively ~~ a;- I (2.10) A.= 3 (q--J * * * ( U j - a j - { ) (cxi-uai+l). . . bj-4 - By (2.6) and (2.8), Carlitz, Permutations with Prescribed Pattern 80 that (2.14) d(xi, ... , x t ) = t j = 1 (2.11) @:'(y)= C Aja!. Substituting from (2.11) in (2.5) we get 1 1 . . . 1 ai a2 ... at . . . . . . . . . . . . ort-2 ut-2 '2 p . . . 1 I d (x,, . . . . xt) = c,zi + Cgx, + ... + c tx t . where cj denotes the cofactor of xi in r3(xt, . . . . xt). Then by (2.10) we have (2.15) A j = a : - ' C j d t ' , where A, is defined by (2.13). It follows from (2.11), (2.13) and (2.15) that Also and where (2.16) 107 t 1 ( l s k e t ) . j = 1 j = i . . . . . . . . . . . ... at-' I 3 08 Carlitz, Permutations with Prescribed Pattern Hence (2.12) becomes Substituting from (2.17) in (2.4)' we get = r=O i ( 1 """)Y')L-&. At To justify the last step note that A, =D,(O, y) and indeed This completes the proof of the following Theorem 1. The generating function i s evaluated by where D,(x, y) is defined by (2.16) and A,=Dt(O, y). Thus for example, for t = 2 , a, = u , a2=/3, (2.18) reduces to where a , f l are the roots of 22-2 +y = O . For t = 3 , ai=a, uz=B, u3=y, we get Carlitz. Permutations with Prescribed Pattern 1 1 1 Xi= z y 2 x2 y' 22 109 1 1 1 1 1 1 . N z = ex ey ez , N 3 = x y x x2 y' 22 ex er er The result for t = 3 suggests that the generat,ing functions D = x ez ey e' z2 y2 2 2 y z Consider the effect of removing the maximal element from 3t. If this element is not on the extreme right, n breaks into two pieces, of which the one on the left has pattern [kl, . . . , k i - l , ki- 11 and the one on the right has pattern [kj+i, . . . , km], for some j, 1 z j -=m. If however the maximal element of 3t is on the extreme right, the resulting permutation has pattern [k,, km-i, k,- 11. Now let f,,,-,(n, m ) denote the number of permutations of 2, with pattern [k,, k?, . . . km], where Also define (3.1) k i s t , . . . , k q n - l Z t , k , Z t - l . f , ( O , O ) = l , f& m)=O (m=-O) - We then have the following recurrence: It follows from (3.2) that Hence, if we put 110 Carlitz, Permutations with Prescribed Pattern Q t - , ( x , y ) = (3.7) we get (3.4) 1 1 . . . 1 a1 u2 . . . ut 1 u, ... . . . . . . . . . . . . . at-a t - 2 -2 t -. . ea2z Substituting in (3.4), we get It is easily verified, using (3.5), that Continuing this process, we remove the largest element from a permutation of Zn with pattern satisfying (3.1) and get + f t , & 2 ( % - L m ) (t=-.S) 9 where ft,Jn, m) denotes the number of permutations of 2, with pattern [k , , 4,. . , , km] such that (3.10) k i s t , . . . , k , - , ~ t , k m S s (1 5 s - d ) . By (3.8) w,t - 1(x, Y) (3.11) - { q - A x , Y ) P + q t - Z ( X , Y) ($=-a ax where Carlitz, Permutations with Prescribed Pattern (3.17) ot,t-j(~, y)= 111 . . . . . . . . . . . . . , . . . a:--? a;-2 ... at t - 2 a j - i ea12: j - Je=2Z . . . pests i a2 it follows from (3.5) and (3.11) that Then, by (3.14), Since (3.15) holds for j = 2 and j = 3, it follows that (3.16) It follows from (3.6) and (3.7) that where 1 1 ... 1 I "i a2 ... at (1 Sj4) . Thus (3.16) becomes This completes the proof of Theorem 2 . Let f,,,(n, m ) denote the number of permutations of ZN with pattern [ki, k2, . . . , k,], where Put ki z f, . . . , kwtk.,,_, ~ t , k, z s . Then, for 1 Ss-= t , where D,(z, y), Dt,Jx, y) are defined by (2.16) and (3.17). 112 Carlita, Permutations with Prescribed Pattern 1 1 ... 1 GI1 GI2 . . . Glt A , = . . . . . . . . . . . (.J-l or#--l &-i t ., . . . t t t (3.20) A,=C C j , D,(x, y ) = c Cieix j=1. j = j and, by (3.17), (3.21) Dt, t -e(z , y)=-- Cjc(eiXi (1 s s - = t ) . Thus, in place of (3.19), we may write l t Y ,=1 (3.22) F J x , ~ ) = j = ~ (1 s s c t ) . To remove the restriction s< t , we note first that (3.14) is in fact valid for all 8 ~ 1 . Then, by (3.5) and (3.14) with s = t - 1 , 2-Q It follows easily that as might have been anticipated. Generally, by (3.14) and (3.5), a (3.24) & (DtPt,8+J=DtFt,8 ( sg l ) We assume that where 8 - t ,r I n view of (3.23), (3.25) holds for s=t . C'arlitz, Permutations wit11 Prescribed Pattern 113 By (3.24) and (3.26), t Q+ DtD; , ,+ j=C Cj {Pm+l(jr)-e ft,,+l(n,.m)=O (n-=r+l) 9 } x:-'-' t K , ( y ) , j=i where K J y ) is independent of x. Since it follows that K,(y)=O. Therefore (3.25) holds for all s ~ t . Theorem 3. With the notation of Theorem 2, we kace. for all s g t This proves the following theorein complementary to Theorem 2. whew Cj i s the cofactor of the element in the first row and j-th column of A , and (qx) is defined by (3.26). 4. kj=O (mod t ) . Let t z - 2 and put (4-1) gt(n. ~ L ) = C kzt . . , kN2) t where the summation is over all positive kl such that (4.2) k l + k z + . . .+km=n, k j=O(modt) ( j = 1 , 2 , . . . , m ) . Thus gJn, m) is equal to the number of permutations of 2, with m inclines and the number of nodes on each incline is a multiple of t . Put Then, by (4.1), kit +... +kmt X - - A(kf f , . . . , k,t) - - (kit+. . . t k , t ) ! ' G,(IL., y) = 1 + c y" m = l Ep..,km=l We now apply (1.4) and (1.5). Since the number of solutions of k , + . . .+Tcj=s, k l ~ 1 , . . . , k j Z 1 is equal to (;I:) ' it follows that M sit +... +s,t where 8 Math. Bachr. Bd. 83 114 Carlitz, Permutations with Prescribed Pattern r = I m=O We have Hence (4.3) becomes Put Then so that We may state Theorem 4. The generating function - x"t - G&, ~ ) = 1 + ,.JJ __ C g t ( m t , m) 9" *=i (w!m=i ( t ~ 2 ) , is evaluated by (4.5) and (4.4). The result is in fact valid for t z 1. Cnrlitz, Permutations with Prescribed Pattern 115 5. kj=O (mod t)-continuation. Let n denot,e a permutation with psttern [ k , , k2, . . . , kml, where kj=O (mod t ) , j = 1 ,2 , . . . , m, and consider the effect of removing the largest element of n. lt.31. ~ If this element is not on Dhe extreme right, the given permutation breaks into two pieces, of which the one on the left has j t - I nodes and the one on t,he right has (m -j) t nodes, for some j, 1 sj sn. Let yt,t-I (nt- 1, m) denote the number of permutations of ZM-l with m inclines, in which the number of nodes in each incline, except the last, is divisible by t , while t.he last contains rt - 1 , for some r z 1. Also define g1(0, 0)=1, gt(0, m)=O (m=-O) * Then we have the recurrence It follows from (5.1) that Hence, if we put we get 116 Carlitz, Permutations with Prescribed Pattern Continuing this process, we remove the largest element from an admissible per- mutation of Zn, - and get, 1 , nt-k) +g t , ,_ ,W-% m) (t=-2) , where gt, t Jnt - r , m), 1 57- -=t, denotes the number of permutations of Z,, --r, with m inclines, in which the number of nodes in each incline is a multiple of t , while the last contains kt - T nodes. It follows from (5.6) that where of course It is convenient to put Then (5.7) gives 60 that Generally we have Crtl.litz. Permutations with Prescribed Pattern 117 This is equivalent to The left hand side of (5.13) is equal to p"(z) f ' (z) f ( t -1 ) f'(z"'t-'' (4 - Y __ (1 -Y) vt(x (1 - Y P t ) f(4 f(.) f b ) f ( x ) f ( 4 1 -YV& (1 - 9 ) Y +- - 1-Y f (4 --(1-y)+-. - 1-Y - - ( I - y ) + ___ 1 - y'Pt(x ( 1 - y)l't) Thus we have verified (5.13). To sum up the results of this section we state Theorem 6. The generating function - ,,at - j n satisfies (5.1 1 ) for 1 sj-=t. 6. The case t = 2. We shall now examine the case t = 2 in greater detail. It will be convenient to put F=P(x , y)=G,(x,y) G =G(x , 9 ) =G2,1(z, y) . (6.1) { It follows that (6.2) , -- y) 1 -y sinh (XI=) I G(z, y) = I 1 - y cosh (XI=) 118 Carlitz, Permutations with Prescribed Pattern This is equivalent to To facilitate the computation of partial derivatives we put (6.7) - y (1 -y) sinh x F, = -~ = P G , G, = + - 1 F = - + (1 -y Gosh x)2 1 - _. =-1+--F+@, - y cosh x y2 sinh2 x I -y cash x (1 -y cash x)Z 1 - Y (1 -y) cash x - P + F * - - 1 -y cosh x sinh x y sinh x cosh x FG I - -ycoshx+ (l-ycoshx)2 y ( 1 - y ) y sinh x (I -y cosh x) y ( I -y) II - 0, = - -~ Moreover, since y cosh x we have This gives 1 -y - 2P + (1 + y) P2= (1 - y) G2 , It follows from these relations that - (6.9) P z = Y (1 -9) q/ and (6.10) ( l - y ) Q z - y ( I - Y ~ ) F g = y F . In view of (6.7), (6.9) is equivalent to (6.11) f m = ~ (1 4 &(Y) Carlits, Permutations with Prescribed Pattern 119 while (6.10) is equivalent to 16-12) Hence, by ( 6 4 , (6.11) and (6.12) become (6.13) and (6.14) respectively. (1 -Y) gfls.1 -Y (1 --Y*)f;(Y)=Yf?l(Y) - f n ( Y ) = ~ Y g , ( Y ) +Y (1 -9) 92Y) S,+l(Y) = ( ( n + 1) Y + W 2 ) f ,(Y) +Y ( 1 -Y2) f 2 Y ) 9 Comparing coefficients of powers of y in (6.13) and (6.14), we get Theorem 6. The enumerants f (n, k ) , g(n, k ) satisfy the mixed recurrences (6.15) f ( n , k ) = ( n - k + l ) g ( n , k - l ) + k g ( n , k), (6.16) g ( n + l , k ) = ( n - k + 2 ) f ( n , k - 2 ) + ( n f l ) f ( n , k - l ) + k f ( n , E). It follows from (6.15) and (6.16) that fl It. is evident from the definitions that (6.19) f(n, n)=A(2n), g(n, % ) = A (212-1) , where A ( n ) denote8 the number of up-down perrnutat.ions of 2%. This is also implied by (6.2), as we shall now show. 120 Carlitz, Permutations with Prescribed Pattern 1 Replace y by y-4 and x by q T i n P(x, y) . Then For y=O this reduces to A (6.21) see x= 1 + f(n, n)- n=l (2n) ! in agreement with the first of (6.19). Making the same replacements in Q(x, y), we get For y=O this reduces to ca X?n - I (6.23) tan x= g(n, n) - , n = l ( 2 n - l ) ! in agreement with the second of (6.19). rent,iate (6.20) with respect to y and then put y = 0, we get (6.24) sec~x-secx:--xtanxsecx= Cf(n, f b - 1 ) -. This is equivalent to The relat,ion (6.25) is the case k=1z+l of (6.16). For k=n, (6.15) becomes Additional results of this kind can be obtained. For example, if we diffe- - 1 2 n = l (2n) ! f (n, n - 1 ) = A (2% + 1 ) - (n + 3 ) A ( 2 1 2 ) = g (n + 1, 12 + 1 ) - (n + 1) f (n, 7%) . f (n , n- l ) = g ( n + 1,n + 1) - (n+ 1) f (n , n) (6.26) s(n, n - 1) =fb, 12) - ng(n, n) , while (6.16) gives (6.27) g(n+ I , n) = 2f(n, - 2) + (n+ 1 ) f ( ~ , 12- 1) +nf(n, n) . Hence, by (6.25), (6.26) and (6.27), we get (6.28) 2f(n, 9%-2) =f(n+ 1, n+ 1 ) - 2 (n+ I ) ~ ( T L + 1, n+ 1) + (n2+n+ 1) f ( m , 12.). In terms of A(n) this is (6.29) 2f(n, n-2) = A (212+2) - 2 (n + 1 ) A (2n+ 1) + ( n ' + ~ + 1) A(2n) . For k = n - I , (6.15) reduces to 2g(n,n-%)=f(n ,n- - l ) - (n- - l )g (n,n-I) =g(n+ 1, n+ 1) - (n+ 1) f (n , 12) - (n- 1) f (n , 12) -ng(n,n) , Carlitz, Permuta.tions with Prescribed Pattern 121 that is, (6.30) 2g(?%, ?%-2)=g(?2+1, %+1)-2Rf(n, n)+n (n-I)g(n, R ) = A (2n+1)-2nA(2n)+n ( n - 1 ) A ( 3 n - 1 ) . Similarly we find tha t (6.31) md (6.32) 6g(n, 12-3)=A (2n+2)-3nA (2n+l ) Gf(n, n - 3 ) = A ( 2 n + 3 ) - 3 ( ? % f l ) A ( 2 n f 2 ) + (3n2+ 3% +4) A (2rt + 1 ) - (Iza+2n + 3) A(%) +(3n2-3n+l )A(2n) -n (n-1) (n-2)A (212-1). These results suggest that (0 .33) k ! f ( u , n - k ) = C ( - I ) ~ P ~ , ~ ( ~ ) A (2n-t-k-j) ( O s k < n ) and (6.34) k ! g ( n , n - k ) = z (-l)'f&&)A (2n+k-j-l) (Or!%-=%) , where Y,,?(n), &k,j(n) are polynomials in n of degreej. A! 1 =o k j = O In order to prove (6.33) and (6.34) we require the following Lemma. The enumerant A(n) satisfies no reczcrrence, of order independeqat of n, Proof. See [3]. Izut with coefficients that are polynomials in n. c.,$2" - \$2" + 1 - (6.35) secr x = s;, ~ - - sec' x tan x= C S!,n+l I_-- N = O (272) ! ' n=O (2n+ I ) ! so that P (6.36) f (n, n - k ) = 2 (-1)i j = O 122 Carlitz, Permutations with Prescribed Pattern I \ j l 0 1 2 3 k\ 1 1 2 4 1 3 16 20 1 4 720 736 56 1 _ _ _ _ Similarly, using (6.22), we get On the other hand, by differentiation of - X 2 n ca X2n f 1 secx= C ~ ( 2 n ) t a n x = C A (2n+i ) - - - ( 2 n + i ) ! n=O (2%) * n =O we get where c ~ , ~ , dk , j are independent of n and satisfy the recurrences %+l, i = c k , j - i + ( 2 k + l ) 2 C k , j , (6.39) { dk+i,j=dk,j-l+ ( 2 k ) 2 d k , j - The above Lemma is used in the derivation. It can be shown that (see [5 , p. 2211) A (6.42) ( k - l ) ! seckx= c-- 2 U ~ , ~ A ( 2 n f j ) . .n=o ('n)! j = o Carlitz, Permutations with Prescribed Pattern 123 Differentiat,ion gives (6.43) k! sect% tan x= Comparing (6.42) and (6.43) wit.h (6.35), we get - %2n--i k C a,,iA (2n- 1 +j) . n=l (2n--1)! j=o Hence, by Therefore, (6.44) (6.45) k - 1 J =(I (k-l)! k&= C a , , i A (2n+j) k ) =o Ic! S & + , = C a , , , A ( 2 n + l + j ) . (6.36) and (6.37), I i k! f(n, n - k ) = C A (2n+k- j ) C j = 1 8 =o k i k! g (n, n - k ) = C A (2n+k-j-1) C j =(I r=O (:)(:) '! ' k - r , k - j * by (6.33) and (6.34), we get I P,,&) = 2 ( - 1 y - g (":')(!) s! a k - s i l . k - i , QJn) = 2 ( - 1 y - 8 8 = ( I (:)(f) a k - s , k - i . 6=11 Clearly PJn) , Qp,?(n) are polynomials in n of degree j. Theorem 7 . The enunzerants f (n, k), g(n, k ) are ezpressible as linear combinations of A (2n+j ) : k k! f(n, k) = C ( - l)i Pk,i(n) A (2n+k- j ) 3 =(I k (0 5 k < n) ; k ! g ( n , k ) = C ( - l ) ' Q k , i ( n ) A ( 2 n + k - j - 1 ) I =o the coefficients P,,;(n), QI,j(n) satisfy (6.44) a?ad (6.45) and are polynomials in n of degreej. 7. Explicit formulas for f (n, A!), g(n, k) . We have - 1 - Y ___ ___ ~~ 1 -Y 1 - y cosh (z fT--i) 1 - y - y (coshx 1 1 -y - 1) 124 Oerlitz, Permutations with Prescribed Pattern Hence we get (7.2) n k = O f,(y)= C 2-"yk (I - Y ) " - ~ 8(2k, 212) . The right hand side of (7.2) is equal t o n n-k C 2 - 2 k 8 =o ( - l ) ' (nsk)ykt .d(2k , 2n) k=O - - 2 yk C ( - 1)s 2- -2k+ ' l8 ( " - k + s )S(2k-2*, 2%) k k = O s = o and therefore k 9-2k.f2S ( n - k + s )8(2k-Zs, 2n) f(n, k)- c (-1) a 8 = O (7.3) As for g(n, k), we have . -. - y 1 1 - y sinh x f r y - y 11 - y sin11 x 1- - -- -- 1-ycoshx 11-y 1-y-y (coshx ~ G J - 1 ) Carlitz, Permutations with Prescribed PR.tterii 125 C2-2h"+l y h (1 -y)"-k 0(2k- l ,212-1) , =c n = l ( 2 1 2 - 1 ) ! k = , where I t now follows irorn (6.2) and (ti.6) that (7.5) This yields n y ~ y ) = C 2 - 2 k + i y k (1 - Y ) " - ~ d(2k- 1,212- 1) . E = l lye may now state Theorem 8. The enurnerants f(n, k ) , g(n, k ) have the explicit evaluation k f ( n , k ) = c ( - l )k-s 2-'8 S =o where 2k j =o 8(2k, 2%) = c ( - l)i (7) (k- j )2n 6 ( 2 k - 1 , 2 n - I ) = C ( - I )? ( k - j ) 2 f i - 1 . 2 k - i j =O 126 Carlitz, Permutations with Presaribed Pattern In particular, for k = n, n A(2n) =f(n, a) = C ( - I ) ~ - ' 2-2s 6(2s, 2n) A (%-1)=g(n,n)= C (-1)n-s2-288f18(2s-1, 2%--1) . s=o n s = l We remark that S(s, n) can be exhibited a8 L central difference of zero (6, p. 13). References [l] L. CABLITZ, Generating functions for a special class of permutations, Proceedings of the [2] - , Permutations with prescribed pattern, Math. Nachr. 58, 31 -53 (1973). 131 - , Recurrences for the Bernoulli and Euler numbers, Math. Nachr. 29, 151 - 160 (1965). [4] L. CABLYTZ and RICHARD SCOVILLE, Generalized Eulerian numbers: combhatorial applications, [5] N. E. NORLUHD, Vorlesungen iiber Differenzenrechnung, Berlin 1924. [6] J. F. STEFFENSEN, Interpolation, Baltimore 1927. American math. Society, vol. 47, 251 -256 (1975). Journal fiir die rehe und angewandte Mathematik 266,110 - 137 (1974). Duke University Deprtnte9zt of dfathematics Durham, North Carolina 27706 U.S.A.