On the maximum of r-Stirling numbers

On he maximum o -S i ling numbe s Is ´an Mez˝o 1 Depa men o Algeb a and Numbe Theo y, Ins i u e o Ma hema ics, Uni e si y o Deb ecen, Hunga y Abs ac De e mining he loca ion o he maximum o S i ling numbe s is a well de eloped a ea. In his pape we gi e same esul s o he so-called -S i ling numbe s which a e na u al gene aliza ions o S i ling numbe s. Key wo ds: S i ling numbe s, -S i ling numbe s, unimodali y, log-conca i y 2000 MSC: 11B73 1 In oduc ion The S i ling numbe o he i s kind hn migi es he numbe o pe mu a ions o nelemen s o med by exac ly mdisjoin cycles. They sa is y he ecu ence ela ion "n 0#=δ0n,"n m#= (n−1)"n−1 m#+"n−1 m−1#,(1) As an equi alen de ini ion, he numbe s hn kin k=0 a e he coe icien s o he nex polynomial: n X k=0 "n k#xk=x(x+ 1)(x+ 2) ···(x+n−1).(2) The S i ling numbe o he second kind, deno ed by nn mo, enume a es he num- be o pa i ions o a se wi h nelemen s consis ing o mdisjoin , nonemp y Email add ess: [email p o ec ed] (Is ´an Mez˝o). URL: h p://www.ma h.kl e.hu/algeb a/mezo.h m (Is ´an Mez˝o). 1P esen add ess: Uni e si y o Deb ecen, H-4010, Deb ecen, P.O. Box 12, Hunga y P ep in submi ed o Ad ances in Applied Ma hema ics 18 Janua y 2008 se s. The ollowing ecu ence ela ion holds (n 0)=δ0n,(n m)=m(n−1 m)+(n−1 m−1).(3) An al e na i e de ini ion can be gi en by he o mula xn= n X k=0 (n k)x(x−1)(x−2) ···(x−k+ 1).(4) An excellen in oduc ion o hese numbe s can be ound in [9]. A sequence a1, a2, . . . , anis said o be unimodal [25] i i s membe s ise o a maximum and hen dec ease, ha is, he e exis an index ksuch ha a1≤a2≤ ··· ≤ ak, and ak≥ak+1 ≥ ··· ≥ an. A s onge p ope y, called log-conca i y, implies he unimodali y. The se- quence a1, a2, . . . , anis called log-conca e when a2 k≥ak+1ak−1(k= 2, . . . , n −1),(5) and i is called s ongly log-conca e when he e is s ic inequali y in he abo e exp ession. New on’s inequali y [18] gi es a simple es o e i y he s ong log-conca i y. Theo em 1 (New on’s inequali y) I he polynomial a1x+a2x2+···+anxn has only eal oo s hen a2 k≥ak+1ak−1 k k−1 n−k+ 1 n−k(k= 2, . . . , n −1). This immedia ely implies he s ic e sion o (5). Conside ing (2), an immedia e consequence is ha he sequence hn kin k=1 is s ic ly log-conca e o all n. Acco ding o he wo k o Hamme sley [11] and E d˝os [8], much mo e is ue. Namely, he index Kno he maximal S i ling numbe o he i s kind is unique o all ixed n > 2: "n 1#<"n 2#<··· <"n Kn−1#<"n Kn#>"n Kn+ 1#>··· >"n n#. 2 Mo eo e , he maximizing index is de e mined by Kn=  log(n+ 1) + γ−1 + ζ(2) −ζ(3) log(n+ 1) + γ−3 2 +h log(n+ 1) + γ−3 22  , whe e [x] deno es he in ege pa o x,ζis he Riemann ze a unc ion, γ= 0.5772 . . . is he Eule -Masche oni cons an and −1.1< h < 1.5. As E d˝os ema ked, his can be simpli ied when n > 188: log n−1 2< Kn<[log n].(6) The si ua ion changes o S i ling numbe s o he second kind. The e is no exac closed o m o he maximizing index Kn. Wha is mo e, we do no know whe he i is unique o no . Al hough K2is no unique, since n2 1o=n2 2o= 1, in 1973 Wegne [23] conjec u ed ha o all n≥3 he index Knis unique. Acco ding o he pape [4], he e is no coun e example o 3 <n<106. One hing is ce ain, he S i ling numbe s o he second kind o m a s ongly log-conca e sequence [4,7,18,20]. The pape s [10,12,14–16,23] con ain a numbe o es ima ions o Kn. The mos exac (wi hou any app oxima i e e m) was gi en by Wegne [23]: Kn<n log n−log log n(n≥3),(7) n log n< Kn(n≥18). Asymp o ic p ope ies o he maximizing index we e p o ed in [19,21] and e en by s a is ical ools in [13]: Kn∼n log n, in he sense ha hei quo ien ends o 1 as n ends o in ini y. We ema k ha his app oxima ion can be gi en using he esul in [4]. I is shown ha Kn∈ {be (n)−1c,de (n)−1e}, whe e (n) was de ined implici ly by he equa ion (n)e (n)=n. 3 Since (n) is known as he Lambe W unc ion [5] we can use i s app oxima- ion [5, p. 349]: W(z) = log z−log log z+log log z log z+O log log z log z!2 (z > 3). This means ha e (n)=eW(n)=n log nelog log n log n··· ∼ n log n. 2 No ion o -S i ling numbe s In he p e ious sec ion we ha e in oduced he p oblems on he maximum o S i ling numbe s and p esen ed he solu ions. Now we ex end he p oblem o he na u al gene aliza ion o S i ling numbe s as ollows. Fo any posi i e in ege he symbol hn mi deno es he numbe o hose pe mu- a ions o he se {1,2, . . . , n} ha ha e mcycles such ha he i s elemen a e in dis inc cycles. The ecu ence ela ion is he same ha o o dina y S i lings "n m# = 0, n < , "n m# =δm , n = , (8) "n m# = (n−1)"n−1 m# +"n−1 m−1# , n > . A double gene a ing unc ion is gi en in [3]: ∞ X n=0 n X k=0 "n+ k+ #xk!zn n!=1 (1 −z) +x.(9) Le us in oduce he -S i ling numbe s o he second kind. nn mo deno es he numbe o hose pa i ions o he se {1,2, . . . , n} ha ha e mnonemp y, disjoin subse s, such ha he i s elemen s a e in dis inc subse s. The 4 usual ecu ence is again he same. (n m) = 0, n < , (n m) =δm , n = , (10) (n m) =m(n−1 m) +(n−1 m−1) , n > . The iden i y (4) u ns o be (x+ )n= n X k=0 (n+ k+ ) x(x−1) ···(x−k+ 1).(11) One can iden i y he o dina y S i lings o -S i lings ia "n m#="n m#0 ="n m#1 , (n m)=(n m)0 =(n m)1 . A nice, in oduc o y pape was w i en by B ode [3]. The ques ion a ises immedia ely: wha is ue om he esul s o he i s sec ion wi h espec o -S i ling numbe s? In he ollowing sec ions we gi e he answe . 3 Resul s o -S i ling numbe s o he i s kind Theo em 2 The sequence hn+ k+ in k=0 is s ongly log-conca e (and hus uni- modal). P oo . Le us de ine he ollowing polynomial: Pn, (x) := n X k=0 "n+ k+ # xk.(12) I is wo h o shi he indices by o a oid he edundan ze os, since hn ki = 0 i n< . The exponen ial gene a ing unc ion o Pn, (x) is gi en in (9), whence 1 (1 −z) +x= ∞ X n=0 +x−1 + n n!zn= ∞ X n=0 Pn, (x) n!zn. 5 Compa ing he coe icien s, Pn, (x) = n! +x−1 + n n!= (x+ )(x+ + 1) ···(x+ +n−1).(13) The e o e he oo s o Pn, (x) a e eal. Applying New on’s inequali y, he p oo is comple e. 2 In wha ollows le K1 n, deno e he maximizing index o he sequence hn ki n k=0 ( he uppe index 1 e e s o he kind). To ind he es ima ion o K1 n, we ha e o ema k ha he numbe s hn ki o a ixed n, a e he elemen a y symme ic unc ions o he numbe s 1, . . . , n, while he numbe s hn ki a e he elemen a y symme ic unc ions o he numbe s , . . . , n (see [3,8]). Tha is, o a ixed n, he (0-)S i ling numbe s a e he sums o he p oduc s o he i s nna u al numbe s aken ka a ime and -S i ling numbe s a e he sums o he p oduc s o he , . . . , n na u al numbe s aken ka a ime. This was de ailed in [3]: "n n−k# =X ≤i1<i2<···<ik<n i1i2···ik(n, k ≥0).(14) Now we ci e a heo em o E d˝os and S one [8]: Theo em 3 (P. E d˝os and A. H. S one) Le u1< u2<··· be an in ini e sequence o posi i e eal numbe s such ha ∞ X i=1 1 ui =∞and ∞ X i=1 1 u2 i <∞. Deno e by Σn,k he sum o he p oduc o he i s no hem aken ka a ime and deno e by Kn he la ges alue o k o which Σn,k assumes i s maximum alue. Then Kn=n−"n X i=1 1 ui− n X i=1 1 u2 i1 + 1 ui−1 +o(1)#. I is ob ious om (14) ha "n k# = Σn− ,n−k(15) wi h he sequence u1= , u2= +1, . . . . As a consequence, we ge he pa allel esul o (6): Theo em 4 The la ges index o which he sequence hn kin k=0 assumes i s 6 maximum is gi en by he app oxima ion K1 n, = +log n−1 −1−1 +o(1). P oo . I we choose u1= , u2= +1, . . . hen, by (15), he maximizing index K1 n, equals o +"1 +1 + 1 +···+1 n−1− ∞ X i=1 1 ( +i−1)( +i)+o(1)# = +log n−1 −1−1 +o(1), since i is well known ha 1 1+1 2+···+1 n= log n+γ+o(1). The addi i e e m comes om he ac ha he i s nonze o symme ic unc ion belongs o he index k= in he sequence hn kin k=0.2 Example 5 We gi e an elemen a y applica ion: he maximal elemen o he sequence h30 ki330 k=0 belongs o he index K1 30,3= 3 + log 30 −1 3−1−1 3+o(1)= 5. Indeed, "30 5#3 = 1.259 ·1031 is maximal, as one can see wi h any compu e algeb a sys em using he ecu - ence ela ions (8). 4 Resul s o -S i ling numbe s o he second kind To o mula e ou esul s, we p o e he ollowing heo em. Theo em 6 The sequence nn+ k+ o n k=0 is s ongly log-conca e. P oo . As be o e, we de ine he polynomial Bn, (x) := n X k=0 (n+ k+ ) xk.(16) 7 Using he ecu ence ela ion (10), Bn, (x) = n X k=0 (k+ )(n−1 + k+ ) xk+ n X k=0 (k+ )(n−1 + k−1 + ) xk =1 x −1 n−1 X k=0 (k+ )(n−1 + k+ ) xk+ −1+xBn−1, (x) =1 x −1 ∂ ∂x (x Bn−1, (x)) + xBn−1, (x). F om his we ge a ecu ence ela ion o he polynomials Bn, (x): Bn, (x) = x ∂ ∂xBn−1, (x) + Bn−1, (x)!+ Bn−1, (x).(17) This equa ion implies he iden i y exx Bn, (x) = x∂ ∂x (exx Bn−1, (x)) .(18) Mo eo e , by he de ini ion (16), Bn−1, (x)>0 i x≥0. We p o e he emain- ing pa by induc ion. Since B1, (x) = x+ , i s oo is eal (and nega i e). Now assume ha all o he oo s o Bn−1, (x) a e eal and nega i e. So Rolle’s heo em gi es ha on he igh hand side o (18) he e a e n−1 nega i e oo s beside he oo x= 0 wi h mul iplici y . Because he unc ion on he le hand side mus ha e exac ly n+ ini e oo s, he missing one can no be complex. Since Bn, (x)>0 i x≥0, i mus be nega i e, oo. New on’s heo em comple es he p oo . 2 Rema k 7 The Bell polynomials a e de ined as Bn(x) = n X k=0 (n k)xk. The Bell numbe s a e Bn=Bn(0). The e o e he de ini ion (16) can be con- side ed as a gene aliza ion o hese numbe s and polynomials in he special case Bn(x) = Bn,0(x). We con inue wi h he ollowing lemma which is a pa ial gene aliza ion o he so-called Bon e oni-inequali y (see [23,24]). Lemma 8 We ha e (m+ )n m!−(m−1 + )n (m−1)! <(n+ m+ ) <(m+ )n m!, 8 o all n≥m > 0. P oo . Equa ion (11) yields ha (m+ )n= m X k=0 (n+ k+ ) m! (m−k)!. Hence (m+ )n m!= m−1 X k=0 (n+ k+ ) 1 (m−k)! +(n+ m+ ) , he e o e he inequali y on he igh hand side is alid. Applying (11) again, we ge (n+ m+ ) >(m+ )n m!− m−1 X k=0 (n+ k+ ) 1 (m−1−k)! =(m+ )n m!−(m−1 + )n (m−1)! . 2 Since he sequence nn ko n k= is s ongly log-conca e, he e exis an index K2 n, o which ··· <(n K2 n, −1) ≤(n K2 n, ) >(n K2 n, + 1) >··· Now we gi e es ima ions o he maximizing index K2 n, o -S i ling numbe s o he second kind. Theo em 9 Le K2 n, be he g ea es maximizing index shown abo e. Then K2 n, <n− log(n− )−log log(n− )(n≥ + 3), n− log(n− )< K2 n, (n≥ + max {18,log 2/log (1 + 1/ )}). P oo . I is con enien again o shi he indices. To p o e he uppe es ima ion, we apply equa ion (32) o [3]: (n+ k+ ) = n X j=0 n j!(j k)1 n−j, 9 [21] B. C. Rennie, A. J. Dobson, On S i ling numbe s o he second kind, J. Combin. Theo y 7 (1969) 116-121. [22] A. Rucinski, T. Luczak, S. Janson, Random G aphs ol. 2., John Wiley, New Yo k, 1992, 215-231. [23] H. Wegne , H. ¨ Ube das Maximum bei S i lingschen Zahlen zwei e A , J. Reine Angew. Ma h. 262/263 (1973) 134-143. [24] H. Wegne , S i ling numbe s o he second kind and Bon e oni’s inequali ies, Elem. Ma h. 60 (2005) 124-129. [25] H. S. Wil , Gene a ing unc ionology, Academic P ess, Ha cou B ace Jo ano ich, 1994. 16