, ~ylv~tn1«yrl-F-l.~9f§, a . . THESIS {K 01/ Illlllll‘lllllllllllllllllllll 3 1293 01417 2013 This is to certify that the dissertation entitled SUBPOSETS OF THE BOOLEAN ALGEBRA presented by Ping Zhang has been accepted towards fulfillment of the requirements for Doctor pol-7‘31 degree in my Philosophy \ g \ Major professor Wei-Eihn Kuan Datejug.i 1 /7;{ August 1, 1995 MSU is an Affirmative Action/Equal Opportunity Institution 0-12771 LIBRARY Michigan fitate University PLACE ll RETURN BOX to remove We checkom from your record. TO AVOID FINES return on or More dete due. DATE DUE DATE DUE DATE DUE MSU leAn Atflnnetlve MONEquel Oppommlty Inetltulon , m m1 SUBPOSETS OF THE BOOLEAN ALGEBRA By Ping Zhang A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1994 ABSTRACT SUBPOSETS OF THE BOOLEAN ALGEBRA BY Ping Zhang This work deals with two important subposets of the Boolean algebra. The first subposet ka is called truncated Boolean algebra, which consists of all subsets, whose cardinality is at least I: together with the empty set. We first compute its Mobius function in various ways. Since ka can be consudered as the intersec- tion lattice of the k-equal subspace arrangements, we then compute its charateristic polynomial, x(Qn;k,t), by different methods. As a result, we obtain two different " expressions for x(Qn;k,t). One of them has a nice form in the terms of the basis (t — 1)i,z' _>_ 0, for the polynomial ring. The second subposet ink is called the k-divisible Boolean algebra, which consists of all subsets whose cardinality is divisible by k together with the whole set. The generalized Euler number Enlk is the absolute value of Mobius function of ink. So Enlk counts the number of permutations of an n-set with all the descents in the position m, where m is divisible by k. The well known classic Euler number is a special case when k = ‘2. we study the arithmetic properties of the generalized Euler numbers and their q-analogs. We derive two different expressions for their recursions and obtain their divisibilities. We also provide new proofs of previousely known results already in the literature. DEDICATION To my parents iii ACKNOWLEDGEMENTS I would like to take this opportunity to thank my advisor Professor Bruce Sagan. However, I simply do not know how to express my gratitude in words. This work is a very small return for much given. Special thanks to my mathematical uncle, Professor Edgar Palmer, for his en- couragement and kindness. I owe him a great deal. I would also like to thank my doctoral committee, Bruce Sagan, Ronald F intushel, VVei-Eihn Kuan, Edgar Palmer and Richard Phillips, for their time and support. Finally, I would like to thank, my mathematical brother, Chris Weiss, Ms. Dorothy Manderscheid, the head of math library, and my friends, Steven Plemmons and Laurie Church, for their generous help any time I asked. Contents Introduction 1 Definitions and Notation 2 The Truncated Boolean Algebra 2.1 The Mobius Function of the Truncated Boolean Algebra ....... 2.2 Subspace Arrangements and the Intersection Lattices ......... 2.3 The Characteristic Polynomial of the Truncated Boolean Algebra 3 The k-divisible Boolean Algebra 3.1 The Mobius Function of the k-divisible Boolean Algebra ....... 3.2 Old Numbers and New Numbers ..................... 3.3 The Generalized q-Euler numbers .................... 3.4 The Divisibility of the Generalized q-Euler Numbers .......... 4 Open Problems and Conjectures BIBLIOGRAPHY 29 29 37 47 57 64 66 Introduction The history of partially ordered sets, or posets, and lattices begins in the nine- teenth century. The subject was systematically developed in the 1930’s, first in G. D. Birkhoff’s work [4] and then by others. Although the Mobius function originated in several forms related to number theory, geometries, algebra, topology and combi- natorics, the first version of the Mobius Inverse Theorem for posets was due to L. Weisner [44] in 1935. Shortly after Weisner, P. Hall independently rediscovered this theorem [27]. In 1939, M. Ward was able to generalized the M6bius Inverse Theorem [43]. Then in 1964 Rota began the first systematic study the Mobius functions of the posets within combinatorics [32]. He also established the connection between the Mobius function and the efficient enumeration of objects represented by posets. The combinatorial properties of the Mobius function provide a great deal of information regarding the structure of posets and related enumerative problems. The characteristic polynomial of a lattice was also first considered by G. D. Birkhoff [5], and has been called the Birkhoff polynomial [39] and the Poincaré poly- nomial [13]. Since the characteristic polynomial of a lattice is the generating function for the M6bius function, much has been done to exploit the combinatorial and alge- braic properties of this polynomial. For example, Stanley has produced a factorization theorem for the modular elements in a finite geometric lattice [38] and has also shown that the characteristic polynomial of a supersolvable lattice has only nonnegative inte- ger roots [39]. In fact, much recent work has been related to finding conditions under 1 which this polynomial has only integral roots. Raising interest in this topic stems, in fact, from the fact that a polynomial with real roots has a log concave coefficient sequence. If, in addition, the coefficients are positive items, they are unimodal [37]. The topic of hyperplane arrangements has developed rapidly in recent years. The combinatorial implications of this subject arise from a simple fact: An affine hyper- plane cuts R" into two connected regions. By introducing several hyperplanes, R" can be partitioned into a number of bounded and unbounded regions. The problem of counting these regions dated back to to the mid-1800’s. However, no satisfactory explanation or general formulas were produced until 1975 when Zaslavsky [45] first used the Mobius function of the intersection lattice C(A) (defined in Chapter 2) to enumerate the regions of the complement of a hyperplane arrangement. Zaslavsky’s results illustrate the important roles played by intersection lattices, their Méibius functions, and their characteristic polynomials. Zaslavsky also established the theory of signed graphs and eXploited the connection between the chromatic polynomials of these graphs and the characteristic polynomials of certain arrangements [47, 48]. More recently Blass and Sagan were able to generalize one of Zaslavsky’s fundamental theorems [9] by demonstrating that both of these polynomials count a set of lattice points in Z", This gives a surprising relationship between these two polynomials and the Ehrhart polynomial of a polytope [110, 9]. We will use this result and many others to computer Mébius functions and characteristic polynomials for various subsposets of the Boolean algebra. The history of the Euler numbers can be traced all the way back to the eighteenth century. They posses many interesting number-theoretic properties that can also be interpreted in various combinatorial ways. D. André [1] showed that the coefficient of xn/nl in sec x + tan x, or the Euler number En, is the number of alternating permutations (1102 ~ -~a,1 of {1,2,-~,n}, where alternating means a1 < (L? > a3 < 2 a., > This result was extended by Carlitz [11] to generalized Euler numbers, Enuc, which count the permutations (1102 - --a,, of {1,2,---,n} such that a, > a,“ if and only ifi is divisible by k. In particular, the ordinary Euler number is the case when k = 2. Furthermore, Stanley [36] used a q-analog of the Euler number, to generalize this result. He has shown that they count the same permutations by weight, where the weight of a permutation with i inversions is (1'. The divisibility properties of these numbers have also received much attention over the years. It is well-known that [32,,“ is divisible by 2" and that (n + 1)E2n+1 is divisible by 22" but by no higher power of two [12, p.259]. The divisibility properties i of Stanley’s q~Euler numbers were studied by G. Andrews, 1. Gessel, G. Viennot and D. Foata [2, 26, 19]. The odd integer (n. + 1)E2n+1/22" is called a Genocchi number. D. Dumont, G. Viennot and J. Francon have given nice combinatorial interpretations for the Genocchi numbers and the Euler numbers [16, 20]. Moreover, a formal power series extension of these numbers has also been investigated by Ranrianarivony, J. Zeng, D. Dumont [33, 18] and others. We will generalize some of these results to the number Enlk in this thesis. Chapter 1 Definitions and Notation In this section, we set up some definitions and notation. We will follow Stanley [40] as much as possible. Any terms not defined can be found described in Stanley’s book. A partially ordered set, or poset, P is a set together with a binary relation S satisfying the following three axioms: 1. For all :1: E P,:r S as. (reflexivity) 2- If 517 _<_ y and y S 51:, then r = y. (antisymmetry) 3. If a: S y and y S z , then at S 2. (transitivity) Weusez Q whose inverse is also order—preserving; that is, :1: S y in P if and only if 71(23) S 77(y) in Q. A chain (or totally ordered set) C in P is a subset so that every two elements are comparable. So if the elements of C are {$0, 23,, . . . , :rk} with 9;,- S 51:]- when i S j, we can write C as C: :r0<:r1<---<:rk. The length of this chain is k. We say this chain C is saturated if we can write C as C: a?0- {0, 1,. . . ,n} such that 0 if :1: is a minimal element in P p(y):{p(:r)+l ifzr 0. ( ) It is well-known that if n : P —+ Q is an isomorphism between two finite posets P and Q, then ”(13) = 11(17(:1:)) for all :r E P. Also, the Mobuis function of the interval [:c,y] of P equals the restriction to [.r, y] of the Mobuis function of P. The following result is fundamental [44] and a proof can be found in [32]. Theorem 1.0.1 ( M6bius Inversion Theorem ) Let V be a vector space over a field K. Let P be a finite poset with 9.1ff and g .' P —> V satisfying condition that f($) = 23ny 9(y) for all It in P, then 9(0) = Dearth/”(y)- Let P be a finite graded poset with 9 and rank n. The characteristic polynomial ofPis ..\*(P,t) = Z #(i‘) t""”(”’- (1-2) xEP One uses the corank of :15, rather than its rank, as the exponent on t so that the polynomial will be monic. Since the characteristic polynomial is just the generating function for the Mbbius function, it is of fundamental importance. A lattice is a poset £ for which every pair x,y E E, has a least upper bound (or join ) :1: V y and a greatest lower bound (or meet ) a: /\ y. Clearly, all finite lattices have a 9 and a 1. For n E N, let Qn be the poset of all subsets of {1, 2,. . . ,n} ordered by inclusion; that is, :1: S y in Qn if and only if :1: Q y as sets. 6 Then :1: A y = :1: O y and :1: V y = :r U y for all a2,y E Qn. Hence Qn forms a graded lattice with the minimal element 0 = (b, the empty set, and the maximal element 1 = {1,2,...,n}. The rank function p of Qn is p(.r) = [:r], where I - I denotes the cardinality of :13. Then Qn is called the Boolean algebra of order n. It is well—known [40, 3.8.3] that Theorem 1.0.2 The Mb’buis function of Qn is 1,1(;1:):(_1)Irl for all a: E QW By the definition, the characteristic polynomial of Qn is new): Zeu'r'tr'r': Z (—1)*‘[’,:)t"-‘~‘=(t—1)". (1.3) ern |x|=k30 In this work, we study two classes of the subposets of the Boolean algebra Q": the truncated Boolean algebra and the k-divisible Boolean algebra. We denote these two subposets by ank and ink, respectively. We begin in Chapter 2 with the study of the truncated Boolean algebra. In the spirit of J. W. Moon [30], we first compute the mobius function of QM. in as many ways as possible. We then derive two forms of the characteristic polynomial of ank. In particular, after a review of the definitions and some premilinary materials related to subspace arrangements, we use a lattice point counting method due to Blass and Sagan to get this result. In Chapter 3, we study the k—divisible Boolean algebra. We start by determining the Mobius function of ink. We then define the corresponding generalized Euler number to be the absolute value of this Mébius function and study its combinatorial properties. We derive two different recursions for these numbers. By using these 7-; l recursions, we extend some well-known facts about Euler numbers ( the case I: = 2 ) to generalized Euler numbers. In Section 3, we introduce the q-Euler numbers defined by Stanley [40]. We establish combinatorially an explicit expression of the recursion for the q—Euler numbers. Using this recursion, we are able to obtain some nice divisibility properties of the q-Euler numbers and then generalize two q—divisibility theorems of Andrews and Gessel. Along the way, we also provide a few different proofs for known results already in the literature. This work ends with some comments on related results, open questions and various conjectures. Chapter 2 The Truncated Boolean Algebra 2.1 The Miibius Function of the Truncated Boolean Algebra For I: fixed, 1 S k S n, let ank be the set of all 3 Q {1,2,...,n} such that IS] 2 k or [S] = 0. Ordering ka by inclusion, we see that ka is a poset. In fact, ka is the subposet obtained from Qn by eliminating all elements that have ranks 1,2, . . . , k — 1. For this reason, ka is called the truncated Boolean algebra. The Mébius function of ka is well known. We first state the Mobius value 11(33) for elements from ka. Then we give various new algebraic and combinatorial proofs of this result. Our proofs illustrate various standard combinatorial techniques. Theorem 2.1.1 The Mo'bius function of ka is 1 utza f1.(IL') = { (_l)m—k+l (Tn—1 (2'1) k4) ifs; > 0 and [3:] = m where h S m _<_ n. First, we give an algebraic proof of Theorem 2.1.1 simply using the definition of the Mobius function and the following lemma. Lemma 2.1.2 Let P(:1:) be a polynomial of degree at most n with real coefficients. If P(:1:) has more than n distinct real roots, then P(:1:) :— 0. 9 First proof of theorem 2.1.1 : By the definition of the Mobius function of a poset, 11(0) = 1. Let a: E ka with |r| = k +i where 0 S i S n — h‘. We proceed by induction on i. For i = 0, the result is trivial since ,u(:r.) = —1 if [at] = 1:. Assume that the result holds for all 0 S i S I. Now let :1: E ka with Irl = k + I + 1. It is easy to see that [{yE ka: 0 < . > k+1 ’ k+l+1 ,,k+i—1 I3“: W<1+1) { 23(1—i+1lh4)+( i )l' () Let 1" It IS enough to show that P k) — :0. First note k+ a+1xk+I—n a+1n (L+J: (1+U! (2% and k+1+1 k+t—U__w+l+ixe+n~wk+i+nw+¢—1fnw+iw I—i+1 i _ (I—i+U!i' 93) are polynomials in k of degree I + 1. Hence if P(k) gé 0, then it is a polynomial of degree at most I + 1. Moreover, by equation (2.2), (7:11) : 0 for all 0 S j S I and (“1:11)“) = ([+1]) : (—1)’“. Also by equation (2.3), ’ _ al—j+1+1 —J+i—1 ___jn —j+1+1 —j+j—1 __ E] n . . _(1) . . _ 1 i=0 I—i-l—l z I-J'l'l J 10 for all 0 Sj S I and ’ ,, —(1+1)+l+1 —(1+1)+z'—1 _ Zl-1)+( l—i+1 )( i )‘0' It follows that P(—j) = 0 for all 0 S j S I + 1. By theorem 2.1.2, we have P(k) E 0 and the result follows. I The second proof of theorem 2.1.1 involves certain properties of Mobius functions of Eulerian posets which were originally studied by Stanley [41, Proposition 2.2]. A finite graded poset P with 0 and 1 is Eulerian if p(;z:,y) = (—1)’(x'y) for all a: S y in P, where l(-.1:,y) is the length of interval [any] in P; that is, the length of a maximal chain in [:r,y]. It is clear that the Boolean algebra Qn is Eulerian. The following theorem is due to Stanley [40, p.137]. Theorem 2.1.3 (Stanley) Let P be Eulerian afrank n, and let Q be any subposet ofP containing 6 and 1. Set Q = (P\ Q)U {0,1}. Then The second proof of theorem 2.1.1: By the definition of Mobius functions of posets, #meé) = 1. Let :1: E ka with [1| 2 m, where k S m S 12. Since the interval [(1, x] in ka is isomorphic to the poset ka, we can apply Theorem 2.1.3 to Qm and szk. Let 0 and 1 denote the minimal and the maximal element of Qm, respectively. It follows that szk = (Qm \ Qn,;k)U{(1,1} and then by Theorem 2.1.3, #(vak) = (‘1)m-1I‘(szk)- Moreover, if y E Qm;k,y ¢ 1, then #0....kfy) : ,uQm(y) = (—1)'y'. It follows that ”(Q—mi) : —Z#ka(y) y /\(a.',,:r,+1)} = S. Let P = 62,, the Boolean algebra of rank n and S Q {1,2, . . . ,n — 1}. If H < T, then let A(H,T) be the unique element of T \ H. So for any interval [33,31] in Qn, there is a unique increasing chain a: = x0 < 1:1 < < :61 = y defined by letting the sole element :13,- — 3.3--1 consist of the least integer contained in y — ar,_1. Hence /\ is an R—labeling of Qn and [3(Qn, S) is the number of maximal f) — 1 chains M in Qn such that Des()\(M)) = S. Let 8,, be the set of all permutations of {1,2, ..., n}. We define the descent set of 7r to be Des(7r) = {i : 7r,- > 7r,“ and 1 S i S n —1 }. Note that for each maximal 0 — 1 chain M : 1‘0 < .r1 < < a?" in Qn with Des()\(M)) = S, the sequence MM) determines a permutation 71' = /\(.’I:1,:l?0)/\(.’L‘2, 3:1) - ~ ' Mat", a:,,_1) 13 with Des(7r) = S. Conversely, for each 7r 2 7r17r2. - -7r,1 E 5,, with Des(7r) : S, we see that 7r determines a maximal 0 —- 1 chain M®< {7T1} < {711,713} < < {W1,772,---7T,,} with Des(/\(M)) = S. It is easy to check that it is a one to one and onto correspon— dence between the set of all maximal 0 — 1 chains M in Q, with Des()\(M)) = S and the set of all permutations 7T 6 8,, with Des(7r) = S. Hence /3(Q,,,S) = fln(S) is the number of permutations of {1, ‘2, . . . ,n} with descent set S. Now we are in the position to give another proof of Theorem 2.1.1 using the idea of the R-labeling of a poset. The third proof of theorem 2.1.1: Let P = (2,, and S = {A3,}: +1,...,n— 1}. Then P5 = ka and #(ankl = (—1)'S"1/3n(5)= (—1)"-k—lfin(5) where 3,,(5) is the total number of the permutations of {1, ‘2, . . . ,n} with the descent set S. So it is enough to show that n — 1 n S = . i ( ) (, _ 1) Let 71' = 7r17r2---7rn be a permutation of {l,2,...,n} with Des(7r) : S. Then 1r is built up as follows: 7r1<7r2<-~<7rk_1<7rk>7rk+1>7rk+2>--->7rn. Hence 7r,c = n. Since 7r, 7t 11 for all 1 S i S k — 1, there are ("-1) ways to choose k—l in < «2 < < 7rk_1. Having chosen 7n < m < < n-1, since there is only one way to order the rest numbers, we have only one way to choose 7n, > in.“ > - - - > an. It follows that 5,,(S) = ("‘1). k—l Let a: 6 ank with [ml 2 m. Since the interval [0, :13] in ka is isomorphic to QWk, p(.7:) = #(Qm;k) = (—1)""“""1 (72:11) as desired. I 14 2.2 Subspace Arrangements and the Intersection Lattices A central subspace arrmigement A 2 {K1, K2, . . . , Km} in the Euclidean space R" is a finite collection of linear subspaces K, of R". Then A is a hyperplane arrangement if codim K,- : 1 for all i. The intersection lattice of a subspace arrangement, .C = C(A), is the poset of nonempty intersections of these subspaces ordered by reverse inclusion; that is, :1: S y if and only if y g 3:. Thus in £, 0 corresponds to R" and 1 corresponds to (11".; A K. Given two arrange- ments A and B, we say A is embedded in B if A Q 13(3). The characteristic polynomial of L is x(£. t) = Z M17) tdi'ml- (2-6) IEE Note that this charateristic polynomial differs from the one in definition (1.2) since L may not be graded, and even if it is, then the dimension and corank of :1: may not be the same. However, using the dimension often gives more interesting polynomials. One of the most important combinatorial invariants of an arrangement is its char— acteristic polynomial. Zaslavsky has related the characteristic polynomials of certain arrangements to the chromatic polynomials of signed graphs [47, 48]. Blass and Sagan [9] have generalized one of Zaslavskly’s results by showing that these two polynomials both count a certain set of lattice points in Z", which provides us an efficient way to compute characteristic polynomials (see Theorem 2.7). let R" = {(;r1,;r2,---,.r,,)} be the Euclidean space of dimension n. For each 15 i,l S i S n, let H,- be the hyperplane CL‘,‘ = 0 and Q11:{I113H2a”'aHn}° This hyperplane arrangement is called the coordinate hyperplane arrangement and the intersection lattice of 9.2,, is lattice isomorphic to the Boolean algebra Qn. For this reason, we often write Qn in place of C(Qn) . Forfixed k, 1 SkSn, let [={1Si1 >_: , t . . 1 k—n—l : (t—1)n~k+ltkfll (1_ '2') : tn. Much work has been devoted to finding conditions under which the characteristic polynomial of a lattice has only integral roots. This is true for (2,, but not in general for ka, k 2 2. However, Theorem 2.3.1 shows that x(Qn,k, t) at least factors partially over Z, in particular that it is divisible by (t — 1)""‘+1 = x(Qn_k+1,t). Furthermore, Equation (2.7) shows that one gets a nicer form for the coefficients of x(Qn,k, if) when it is expanded using the basis 1, t — 1, (t — 1)2, - - - for the polynomial ring, rather than using the usual basis 1, t, t2, . - -. Since the truncated Boolean algebra can be considered as a subspace arrangement embedded in the coordinate hyperplane arrangement, we first give a combinatorial proof of Equation (2.7) using the Blass—Sagan interpretation of certain characteristic polynomials as counting a set of lattice points in Z" [9]. Theorem 2.3.2 (Blass-Sagan) Let 8n = {(172': i171), (33k = 0)}lSiSanJSkSn 17 and let A be a subspace arrangement such that A c_: £(Bn), Fort = 23 + 1, define has] = {-3,-(9 -1),---,-1,0,1,-.-,s} and c. = {—s.sr. The-n mam) = ICt \ Al. The significance of Theorem 2.3.2 is that it provides us an efficient way to de- termine certain characteristic polynomials without even computing any Mobius func- tions. Before proving this theorem, we would like to give the readers an example to show intuitively what is going on. Consider 82 in R2 and C5 in Z2. It is well-known [28] that x(£(l3n),t) = (t — 1)(t — 3) - - - (t — 2n +1). So x(£(82),5) = (5 —1)(5 — 3) = On the other hand, let A = 32 = {(x1 = is»), (2:1 2 0), (r2 = 0)}. We see that |C75 \ 82] = 8 and then |C5 \ 82' = X(£(Bz),5). The following proof is due to Blass and Sagan [9). I am including their proof here for completeness. Proof ( of Theorem 2.3.2 ): For X E £(A), let f(X): and 9(X) = llX 0 Ct) \ (UY>XY fl Ctll- Given X E £(A) Q C(Bn), there is a one to one correspondence between X 0 C, and - the cube of side t in Zdile) centered at 0. It follows that f(X) = X 0 Ct| = tdimlx). Clearly f(X) = 2:sz g(Y). So by Mobius Inversion Theorem 1.0.1 lCt \ Al — 9( (11") =Z:/t(Y =ZH(Y Utd'm‘Y =X(£(A),t) and this ends the proof. I A combinatorial proof of Equation (2.7): Since QM. g £(Bn), by the Blass- Sagan Theorem, it is enough to show that k—l IC. \ em = Z (:f)(t—-1r-‘. (2.9) i=0 Note that C; \ ka consists of all 1' = (3:1,:r2,...,:1:,,) E Z” where —s S 3:; S s for all i and the number of zeros in (.r1,:1t2, . . .,:1:,,) is at most I: — 1. This observation enables us to partition Ct \ QM. into 1: parts. For fixed i, 0 S i S k - 1, let S.- = {3: = (31,12, . . . ,17,,) E C, \ QM. : the number of zeros in (.r1,.r2, . . . ,rn) is i }. Then IS,| = (the number of ways to choose i elements from {171,172, . . .,.1:,,} as zero coordinates of 1:) -(the number of ways to choose the remaining n — i non-zero coordinates of :L‘ from [—s, s] \ {0}) = (?)(t — 1)"“. It is clear that {Sg}osisk_1 are mutually disjoint and k-l Cl \ ank = U 5,. i=0 Hence k—l A31 n . lCt \ ankl : Z lSII : Z (z)(t _ 1)n-1 i=0 {:0 as desired. I Next, we will give an algebraic proof of Equation (2.7) which only involves the use of binomial identities and the definition of the characteristic polynomial of a poset. 19 An algebraic proof of Equation (2.7) : We start from the right hand side of Equation (2.7): n—k+l k—l n! . , ti = Z {Z '1 )!(_1)n_z—J}'-_ i=0 z.(n — i —j j! Tl 11-j 71! . . tj + z {2. . ._j),(—1>n-J-*)f j:n—k+2 i=0 1- (”- ‘1 Jl n—k k_1 - . n-' i ("—Jll . t3 = Z (—1) J { (’1) -, . .' n(n — 1)...(n —] +1) 7 i=0 i=0 z.(n—z—J). ]. ( thej = n -— l: + 1 term in the first sum is the expansion of (1 — 1)""1 = 0 and thej = n term in the second sum is t") "‘k n— '— j = tn+ Z (_1)n—j {(_1)k-l( 133-11)} n(n— 1)...(n—j+1)% , = 0 (applying identity (1.5) in 22, p.1] to each term in the first sum and the expansion of (l — 1)"‘j = 0 to each term in the second one) n-j-k+1 n(n —1)...(n -j+1)(n ——j — 1)! fl (k-UHn—j—M! j! n—k = t"+ 2H) j = O 20 _ "+20- 1)(p+1" )-1---(k+p+1)(k+p—1)! tn-k-p ((9—1)! P! (n—k—p)! (letn—j—kzp) 11—h , ... ,. A : t"+:(—l)p+l( n )(k+p—1)...(k+1)k tn’k—p k+p p! k+p— __ : tn+ l)p-+-l(1>tnkp. §(k+Pl(-) p On the other hand, the left hand side of Equation (2.7) is X(Qn:ka t) Z #(xfldimtr) 1.6ka 11—1: ' . . . _, _1 _ t” + Z (J)(—1>':‘“ (" 1. i, )t’ ( using Theorem 2.1.1 and |{:1: E ka : dim(:1:) = j}| = (3‘) ) , k+p— 1 __ tn 1)P+l nkp +Z(k+r)(1( P it (letn—j—ltzp). Hence we have shown algebraically that Equation (2 7) holds. As for the proofs of Equation (2.8), we first give it a combinatorial proof using the Blass-Sagan Theorem; that is, count the number of elements in C, \ Q, 21 H m), as we did in the combinatorial proof of Equation (2.7) except that in this case we partition C; \ ka in a different way. A combinatorial proof of Equation (2.8) : For non-negative integers t and s witht=2s+1,welet E=[— .,s] and D: E\{0}. It IS clearthat |E|= 2s+1 =t and [DI = 2s = t — 1. Also we let A X B denote the product of two sets A and B and A“ denote the product of 772 copies A’s where m is a non-negative integer. By Theorem 2.3.2, it is enough to show that —k |<7:\.C%mkl== (t-1)" kid 2:3;(:1 +iz)tk i 1 (2 10) i First we give a outline of this proof. To prove equation (2.10), we construct a partition {.40, A1,... Ak_1} of C; \ ank such that each A.- is a disjoint union of (" H’) sets, say A“, Ai,2,...,Ai'(n—f+i) with |A,-,j| = tk""1(t — 1)""‘+l, where 0 S i S k — 1 and 1 S j g (“is“). In this way, we have k-l k—l ("_k+) C"! \ ank z: 6 Ai .: w w ’43.in (211) i=0 1:0 j=l where L+J denotes the disjoint union of sets. Then k—l k—l (ii—7+.) lCt \ ank1 = Z lAil = Z: Z lAiJI i=0 i=0 j=l k-l (him) _k ~....'_ 1)" +ltk l 1 i=0 j=l : _ 1)n—k+lZ(n —f‘+z)tk—i-l. 1 Now we start a detailed proof of equation (2.10) by constructing {.4,,j}l0 is the formal power series 2 anxn/nl. 7120 For information about generating functions, see Stanley’s book [40] 1f a1, a2, . . . , ap and (21,132, . . . , bq are constants, then we can form the hypergeomet- ric series al, ([2, ..., a 1),, ..., b 1) PFC} ._ (01)k((12)k-~(ap)k : at] .—kZZ% (b1)k"'(bq)k 1;! (2.13) q where (a);; = a(a + l)(a + 2) - - - (a + k — 1) is a rising factorial with respect to k. For information about such functions, see the books of Bailey [3] or Slater [34]. We also need the following result known as the Chu—Vandermonde Theorem [34, p.28]. Theorem 2.3.3 (Chu-Vandermonde ) If n is a positive integer. then —n, a (1 —b+a)n P ' : 9 211 [ —n + b[ I] (1 — 1))” (“'14) Proof. See [34, p.28]. I Now we are ready to give algebraic proofs of Equation (2.8) by hypergeometric series and generating functions, respectively. We assume that Equation (2.7) is given. First factor out (t — 1)"""+1 from 2:01 (2‘)“ — l)"“, and then expand (t — 1)k""1.' We find The coefficient of ii is Let k —j — 1 = h 2 0. We see that the coefficient of ti = tk’h‘l is h -n k—i— (—1)";(—1)'(i)( h—i 1)‘ h n '—-i— 00 .n “—i— 9(h) =;(—1li(i) (k h—i 1) =;(_1)i(i)(k h ”1). It remains to show that Now we let ' —k I g(/2) : (—1) (n I + l) for all h 2 0. (2.15) z 1. We first prove (2.15) by using hypergeometric series. To do this, we need first to express the binomial coefficients in terms of rising factorials: n _ ,(—n), k—i—l _(—1)"(—k+1),,(—h),- ('>’(_1) and ( h—i )‘ h!(—k+1),- ° go.) = 341(3) (k 1; 1) _ (—1)h(—k + 1)}, 00 (—72),‘(—h),‘1 _ {2:7, (4H1), 2i} _ (—1)h(—k+1)h —n, —h _ h! {2Fl[ —k+1[1[} ( by the definition of hypergeometric series) (—1)"(—k +1),,(—n + k — h), h! (—n+k)n ( using equation (2.14) with a = —h and b = n — k + 1 ) (—nnn_t+nh_ n—k+h h! —(-—1)( h ) 26 2. Next we prove (2.15) using generating functions. Consider the generating func— tion 0(1) of {g(/z)}hzu, C(I) = Z {/(llll'h [:0 i = (1 +1‘)k_l:(—1)i(7:) (1:1)! = (1+IV—l (1_ 1:17)” : (1 +1.1)n_k+1 = 2(12 -:+ h)(_1)hJ-h. It follows that g(h) = (—1)"("_:+h) for all h 2 0. Then the coefficient of t"”"1 is (—1)hg(h) = ("7:”) as desired. I We conclude this section by giving the exponential generating function of the characteristic polynomial of (2“,. Theorem 2.3.4 The exponential generating function of {X'(Qn;k,t)}n20 is k—l xi Gt(;r, t) : {Z 7} 6111-1) (2.16) i=0 2. where k is a fired non-negative integer. Proof. By the definition, we have 00 k—l ,n Gk(:r,t) : Z{ (7?>[t_1)n-g}l ...,. _m (t __ 1)Tl—1 n .2 {I|\ 22m H24.“ as desired. 8 9. Chapter 3 The k-divisible Boolean Algebra Let n and k be positive integers with 1 S k S n. Define ink be the set of all subsets a: Q {l,2,...,n} such that l: divides |.r| or [1| 2 n. Ordering ink by inclusion, we see that ink is a subposet obtained from (2,, by eliminating all elements that have ranks not divisible by k, except {1, 2,. . . ,n} if k ,[ n. So ink is called the k-divisible Boolean algebra. It is clear that inl = Q". 3.1 The Mobius Function of the k-divisible Boolean Algebra The main theorem in this section concerns the Mobius function of ink. To state this theorem, we let H and [[ denote the ceiling and floor functions (round up and round down), respectively. Clearly, ifa' E ink, then either [II 2 ml; for 0 S m S [f[, or [:1:| = n. Theorem 3.1.1 The Allobi'us function of ink is ' m ml; 2 —l r E , , , , i .r = mk ; ( ) (J1k,]2k,ooo,]rk) fl I j1+j2+...+jr:m 1.21 lSiSr f—- I! k l.— _ 71-13 J —1’+1 2: n ,7 = dlc . ( l ,. (we—Me,j1k,j21e....j.xel’ 'f '1' ""1" jl+j2+"+.lr=h 1.21 lSiSr r=0 :- ll We will give both algebraic and combinatorial proofs for Theorem 3.1.1. Our algebraic proof of this theorem simply uses the definition of the Mobius function, induction, binomial identities, etc. An algebraic proof of Theorem 3.1.1: For any x 6 ink, we see that either [:13] = ml: for some non-negative m, or [r[ = n with k I n. We will consider these two cases separately. Case 1: Suppose that [ml 2 ml: and induct on m. If m = 0, then .r = 0 and 11(0) 2 l by the definition. Also (—1)0(0!/p) = 1 where p is an empty product. So the result holds when m = 0. Next, by the definition, y 0, then 2 ( jlk, jgk, .. ., j...) .ll+.l2+"'+.lr=m 1.21 lSiSr is an empty sum and hence is 0. Case 2: Suppose that [ml 2 n with k I n. By the definition, #(i)=- E: #(y) y 0, then c0 = 0 and the sum is 0 since it is an empty sum. So the result holds when r = 0. Next assume that r > 0. Let C :0 = :170 < 131 < < 13.4 < .13, = .r bea0—11: chain with fixed |:1:,-| : hit: for all i. Clearly, 0 = I10 < 111 < < h,._1 < h,. = m and the number of such chains C with fixed h,’s is [[(the number of ways to choose 1?.) i=1 33 elements f1om a (1111: — 11,-- 11c)- element set _ H "715-111—119 111k _‘=1h,1f—hi—lk jlk, jgk, "'1jr—1k,j,.k s where we assume that tj 2h,- — h,_1 > 0 for all 1. Then Equation (3.3) follows by I! ii _d‘s irl( the number of ways to choose h k — 11,-111‘ ) taking sum over all possible 0 = jg < jl < --- < j, S 111 such that j1+j2+- - ~+j,. = m and all j.- > 0. Now suppose [:13] = n with k /[ n. Then c0 = 0 and a maximal 0 — 1 chain has length [[3]. By Theorem 3.1.2 , l l 1 11(1) : (_llrcr : (—11’i+lcr+lv 0 a—l: a-l: L— r l r where c,“ is the number of 0 -— 1 chains of length r + 1. It is enough to show that r— x-I: L— n Cr+l = Z < . . . > for all r . h=r _ 4 q n — 11k, glk, 1219,. . .,grk J1+J2+- - 4% = h J} 2 1 1S 1 S 7‘ Following the same lines as in the [1:] = 1111; case, we let C : 0 : .170 < 171 < < :rr_1 < :r,. < 1‘.“ = 1 be a 0 — 1 chain in ink with fixed [17,] = 11,11 for all 1. Then the number of such chains C is r n H(the number of ways to choose 1*.) = ( . . . . ) i=1 Jlk J2k$ "ajr-lka Jrk) n _hrk where each j.- = 11,- — 11,--1 > 0, r S 11. S [1}] and jl + j2 + + jr = 11,.. Now the result follows by substituting 11,. by 11 and taking sum over all possible such j1,- - - ,j,. and h. I The second combinatorial proof of Theorem 3.1.1 uses one of Stanley’s results which characterizes the Mobius function of a rank—selected poset in terms of the number of permutations with a certain descent set [42, Proposition 14.1]. 34 The Second Combinatorial Proof of Theorem 3.1.1: Let S: {k,2h,..., [311} <_: {l,2,...,n — 1}. Then ink is an S—rank-selected subposet of Q... By Theorem 2.1.4, we see that #(ink)=(412—1345)- where ,Bn(S) is the total number of the permutations of {1, 2, . . . , n} with the descent set 5. So it remains to find 13,,(5). Let 0,,(5) be the number of permutations 7r 6 Sn with Des(7r) Q S. Then 0.15) = 2 am. (3.41 Tgs By the Principle of Inclusion-Exclusion [32], we have 11,15): 21—1)|5-T|a,(r). Tgs If [T] = 0, then 01,,(T) = 1. If [T] = r 2 1, then let T:{1Slllk 0 and jl +j2 + - -- + j,.+1 = 111.. By Equation (3.4), we see that m—l 1 n S : __1m—1+ —l m-l-r (. . “I . . ) fi() ( 1 g 1 Z 1,1,J21,...,J.1,],...1 .11+.12+"'+.1r+l =7" 1121 151$r+1 Then it follows that #(ink) = (_11(m_l)—113n(51 m—l .1; : —1+ —1"+1 ( . m. . ) r;( ) Z Jlkfi .12ka°'°1.17‘k1.17’+1k 11+12+~~+1+=m .111 ”IV 1 |/\ .5" m 7111: : _1 r‘ _ . ‘ z( 1 Z (Jlka Jgk,..., Jrk) 11+12+"'+.1r+l =m 1.21 lgigr+1 (shifting the index r by 1 and then putting -1 as the r = 1 term ) m ml: = -1r . . . Z( ) . _ Z _ (311:, 32k,...,g,.1c) Jl +12+°~+1r=m .7121 13131“ ( adding the r = 0 term that is 0 if m > 0). 3G So the result holds in case 1. Case 2: Suppose 1c ,1 11. If 0 < n < k, then 11(ink) = 1. Also, the sum has only 1' = 0 term which equals to 1. So we are done. Now suppose n > 1:. Let m = [fl and then S = {k,21c,...,m} Q {l,2,...,n —1}.lfT Q S, then 71. where jl + jg + - -- +j,. = 11,. and r S h, S 111. It follows that m _ m _ m—l—r n 5.15) _g 1) Z Z (j11,j,1,...,j,.1, 11—1111 11,: _ . . r 11+n+m+1r = h. .11 Z 1 l S i S 1' Changing the notation 11. to 11, we have 7". — m _ r“ n #(ink) _ Z( 1) Z Z (jlkv ijv'Hajt‘k’ 71 — bk) r=0 h=r .11+12+---+jr=h 1.21 13131‘ We add the r = 0 term into the sum to include the 111 = 0 case. Let :1: E ink with [.1] = 1111:. Since the interval [0,11] in ink is isomorphic Q(mk)|k, 11(1) 2 ”(thka) and then the result follows from case 1. I 3.2 Old Numbers and New Numbers Let n(r) be the Mobius function of ink. We define 111(1)] 2 Enlk where I - I denotes the absolute value of a real number. 37 By Theorem 2.1.4, we see that Enlk is the number of all permutations of {1, 2, - - - ,n} with the descent set {11,211, . . ., [fi] 1;}. In particular, if k : 2, then Enl'z is the num- ber of alternating permutations in S”. The number Enp is well known as an Euler number. So we call Enlk a generalized Euler 111111111er for 11' > 2. Define VI 3111]}; : (_11LIJ Enlk” Ifk > 2, then E' , is called a (c11eralized si( ned Euler number and E’ . = —1 15,211 E, 2 71“» J J nlz I is a signed Euler number. The Euler numbers are classical numbers and have been thoroughly studied in the past century. So we consider them as old numbers. By comparison, the generalized Euler numbers will be our new numbers. The following results me \er1— known [12 , p.48 ] for the old Euler numbers . (1). The exponential generating functions of the En]? are 1,211 213071112 —..— — —S€ GCJ‘, 11>0 271.!) 2: E I 91.2”“ —tan:r (211+l)2(—— _ ’ 9 11>0 71+ 1)! 2 1.211 E; — = sech(.r). ”20 "(211)! For this reason, E(2n)|2 and Ennflm are sometimes called a secant number and a tangent number, respectively. Naturally, E(2n)|’2 and E(2n+l)]2 will be called a signed secant number and a signed tangent number, respectively. (2). The number Enlg satisfies the following recursion: for n 2 1, 2n — l E(2n)|2 : Z (9172 _ 1>E‘(‘2m—l)I2Ei(‘2n-—2m)|2 '1' E(2n—l)|2i m=l "‘ ' ' 38 " 2n E(2n+1)|2 = Z ( )E(2m—l)|2E(2n—2m+l)|2 i) _ "1:, ..m 1 with the boundary conditions E112 = 1 for all 0 g i S 2. (3). The number E(2n)|2 satisfies the following formula [10]: (E+1)m+(E—1)m=0 where Em = Em, such that E0 = 1 and Em = E(m)|2’ if m is even; Em : 0, if m is odd . (4). (n + 1)E(2n+1)|2 = 22"|G2n+2|, where G2,.” is called a Genocchi number, which is an odd integer. Thus it is clear that the tangent number E(2n+1)|2 is divisible by 2". It is worthwhile to mention that Lemma 3.2.1 (3) is equivalent to the following condition: (3’). The number El2n)|2 satisfies the following recursion: " 2n , , .120 " Proof. By the binomial formula, we see that (E+1)m + (E — 1)m z V: (3“)137'1-111 + (4)1] 320 m [L22] m m 2 l—J : 2 m— — 2 171 Z (j)E J j>02( 2j )E2ll2l-J) 120 — jeven 39 : 271:2 9(: ;)E(2n— 21H? (putting n = (%J ) .02 2] :2: (1;) It follows that (3) and (3’) are. equivalent. I (\3 [V Our goal here is to extend these well known results for Enlg to Enlk for k > 2. We first consider the exponential generating functions in (1). Stanley [36] has shown the following result. Theorem 3.2.2 Let n and Is be positive integers with k S n. Then the exponential - r. 4” I'd. generating function of Lnlkn is. E El __1 + 2:57;: 271:0 ‘TnkTi/(nk + Z)! (3 6) ”>0 "|k_ 11!: 2,120 arnk/(nk)! . ' Alternatively,, for 1 S i S k — 1, 2E .rnk“ _ _ano :r"k+f/('Iik+i)l . (71k+i)|k (fili‘l‘l ')! znzolJcn/(kn)! 9 n)0 2 E, .rkn — 1 n20 ("WW—lc—n). anoa‘"k/(1ik)li Proof. See [40, Proposition 3.16.4]. I By substituting :15" by -.rk in the exponential generating function for EL“: in Theorem 3.2.2, one can easily see that Theorem 3.2.3 For each fixed k 2 2, the exponential generating function of Enlk is 2 E 11. n 1+ 1:: z.zo(—1>"x"k+‘/(nk+zt>1 (3 7) n>0 n Engo(—1)"$""/(nl~‘)l Also,for1SiSk—1, 2 E ink-H ::n>0(—1)n l,nk+i/(71k +1)! ""‘+""_ We +1) 200(4)" *n/(Im)! 40 xk" 1 E nk k— = 7 ‘ , :22?) ( ll (kn)! Zn20(_l)n$nh/(nk)! Remark: If —- 2, we get the same exponential geneiating function of En]; and EL” in (1): __:....<—1>"r2"+1/<2n+1)!_ 31.1..) Z E(2n+1)|2(7— .T 2 . ' _ : tan(.r), n>0 71+ 1) Zn>0(—1)"1"/(2n). (705(1') (1:2" 1 1 E n — : z z .. Q , g (2 H2(2n)l 2,,20(—1)":r2"/(2n)l cos(at) sec(z) X: E $271 1 1 Cl ( ) = = — : se 1 :r . n20 (2")I2— (271)! 2,120 .172"/(2n.)l ch(a:) Next we give our first recursion for Enlk, which generalizes the recursion for Enlg in (2). Theorem 3.2.4 The number En“. satis 1es the recursion Ln/kl n E(n+1)Ik = 2 (km _ 1) E(km—l)|kE(n—km+l)|k + b(h I nlEnlk- (3.8) where b() is the bootean function defined by 1 if the condition c is true, b(c) = (3.9) 0 if the condition c is not true. The boundary conditions are Eng. 2 1 for all 0 S n S 13. Remark: If k = 2, we have the same recursions for Enlk in (2). As for the proof of this theorem, we leave it to the next section, since Theorem 3.2.4 is just a simple corollary of Theorem 3.3.2. Our second recursion for ELI): generalizes the recursion for ELI.2 in (3) or in (3’). 41 Theorem 3.2.5 Suppose that n 2 l and 1 S i S l: — 1. Then the number En|k satisfies the following recursion: ” . nlc (1) 21—1)] (kj) E(kj)|k = 0; )E(kj)|k + (-1)n+1E(kn+-i)|k = 0 with the boundary conditions Eilk = l for all 0 S i S ls — 1. By the definition, uc 866. that. suppose n > 1 and l S i S k —1. 7/7677. En lk satisfies the following recursion: nk (1') :(kj)E(kj)lk: 0 220 " kn +i . I I I (3) Z ( kj )E(kj)|k = Eat-Mink 1:0 with the boundary conditions Elf“: = 1 for all 0 S i S k — 1. Remark: If k = ‘2, we have the same recursion for EL” in (3’) and (3). We will give Theorem 3.2.5 an algebraic proof as well as a combinatorial proof. Our algebraic proof uses exponential generating functions. An Algebraic Proof of Theorem 3.2.5 To prove (I), it is equivalent to Show that n 1 kn E(kn)lk - l"+1 2(1)J(kj)E(k-j)lk (3-10) j>0 We have " 1V:72)E( wk" 7; [(4) )Jz>(:)() (Jll (hilly _ n_J (kn)! ‘ fun-J) lgkj _ — Z {ZN—l) [Mn - JillUCJ)! EMMA. (kn)! }+1 n21 jZO 4‘2 Z Z < 1 J‘————""“”"" E —'— : - —1 n- . —1 k' L- . +1 1‘20 n-jZO [k(n —])l! (m (15])! —1 1:“ at“ = - Ek'k—. -1 Ek'k—. +1 E E 1.1g 2 E xii-j = —1 + k k—— +1 = ‘ k' k—. . j>0 (1H (kj)! jZO (1H (kj)! Equating the coefficients of—- T: ),, the result follows. To prove (2), it is equivalent to show that n " kn + z . E(kn+i)|k = (—1) :(—1) ( k )EWHA for all z. j:0 J By Theorem 3.2.3, we have Tnk+i 137M7i k— 71:20 ( +ll (”k-ft)! = Z(—l)"fifi— 2E k ”kn/(kw "20 (nl; + i)! "20 (n )l . . _ n - kn +i JJMH = —1 n —1 J E .- . _— nZO ij Ink+a (— Ai+ ),, the result follows. I Equating the coefficients of— We now give a combinatorial proof of Theorem 3.2.5. To do this, we need some preliminary materials related to signed sets and the involutions of such sets. A signed set S is a set with a function e : 5' —> {+1. —1}. An involution f on S is a function f : S —) S such that f2 = id, where id is the identity map of S . A function f on a signed set S is sign-reversing if sign {f(a)} : —sign {f(a)} for all a E S 43 A point a E S is called a fixed point of f if f(a) = a. The set of all fixed points of f in S is denoted by F]; that is, F] = {a E S : f(a) : a}. Then the following theorem will play a crucial role in our proof [40, 2.6]. Theorem 3.2.6 Let S be a signed set with a sign function e. Iff is a sign-reversing involution on S with the fired point set F]. Then X: 6(a) = Z 6(a) = lFfl- (3.11) 065 06F, A combinatorial Proof of Theorem 3.2.5 : First, we construct a. signed set S as follows: we let 7r0 represent the O permutation for convenience of notation. 5(0) = {”0}, 5(72 +1) {7r 2 7T17T2"'7Tkn+,‘ 651.“,- : Des(7r) = {k,‘2k,---,kn}}, i # O; (0. i: 0. Let 1 S j S n and O S i S k —1 . For fix i and j, let J be any kj-subset of {1,2, - - - ,kn + i} and 5(J) be the set of all permutations of J with descent set {k,2k,-- - ,(j — 1)k}. Then let 5(j) = L—lj 5(J), where J runs over all kj-subset of {1,2, - - - , kn + i}. J By the definition of Enlk, one can easily see that |5'(.0)|=1~ lsUll = (kit?) E(kj)|k, ifl SJ S 71 and 0 S i _<. k — 1a E(nk+i)|ka if 'i # 0; |5(n +1)| = 0, ifi = 0. 44 we now contruct a signed set S by n+1 s = L+J 5,- i=0 with a signed function e : S -—7 {+1, —1} defined by e(7r) = (—1)J‘ if 7r 6 5,. Secondly, we define a sign reversing involution f on S as follows: if 7r 6 S, then 71’ E S,- for some 0 Sj S n + 1. there are three cases: Case 1: Ifj = 0, then 7r 2 71'0. Define f(7r0)=1‘23-~-k. Case 2: lfj = n + 1 and i > 0 and then 7r 2 mm ' - - 7mm“. Define “71'1"? ° ' ’ TVA-n+1) = 7717M ' ' ' Trim- Case 3: If 0 < j < n + 1, then 7r = 7r17r2 - - - 77k)” we let {1,2,...,kn+i}\{m,7r2,...,7rkj}={a1< (12 < ...} and define 7r17r2 - --7r1.J-(11(12-~ak E 5141, ifa1< Tl’kj and 1 Sj < n; 7r17r2 - unnalag - --a,- 6 5n“, if a1 < 7mm and j = n; f(vr) =< (3-1‘2) 7r17r2---7r1.J-_1;€Sj_1, i'fa1>7rkj and17rkjandj=1 Remark: Note that f is a well defined map on S. Moreover, if 71' E 5'], then either f(7r) E 51-“ or f(7r) 6 51-1. It follows that 1. f is sign reversing. 2. f has no fixed point; that is, F, 2 (ll. It remains to show that f is an involution on S. 1. If 71 6 5(0), then f‘zlrro) = f(1‘2-°-k) = 7T0, since {1,2,...,nk+i}\{1,2,...,k} ={Ic+1 o("1)n$nk+i/(ank+e E ‘n i ‘ = T 3.13 71:20 (h + )lk(q) (q)kn+i Zn20(—l)nxnk/(q)nk ( ) 47 forlSiSk—land kn 1 . 1? E: Elkn)lk(‘1)_ = 3. n20 ((llkn Zn20(—1)"Ccnk/(q)nk ( 14) where (q)m = (1 -— q)(1 — qz)...(1 — q"‘) = (1 — q)'"[m]l for any positive integer 7n. We call En|k(q) a generalized q-Euler number. In particular, E,,|-2(q) is an ordinary q—Euler number and a natural q-tangent number is given by $2n+l Z E(2n+1)|2((1) 7120 (q)2n+l anol—l)n4F2'lH/(‘ll2nfl _ sinq(:r) anol—1)”$2"/(Q)2n ‘ cosqm z ”“0“” Also, it is clearly that En|k(1) = EnIk. The main theorem in this section is concerned with a recursion for Enlk(q), from which we derive the first recursion for Enlk- Once we have established this theorem, we can more efficiently study the divisibility properties of Enlk- First, the following preliminaries are needed. Let $1,:r2,...,a:n be a set of variables. Then the elementary symmetric function of degree r in n variables is the sum of all square-free monomials of degree r in $1,332, ...,:rn. More formally, for all r 2 0 and n 2 0, e,.(.r1,.r2, .r,,) = Z anagram“. (3.15) Isi1 b. We define [(P1,P2) = |{(a,b) : a 6 P1, l) 6 P2 and a > b}| Lemma 3.3.1 Let {131,132} be a partition of{1,2, ...,n} with IP1| = r. Then 2 qI(P1.P2) : [7:]. (3.17) {P11P2} Proof. This lemma is well known. But I am including a proof for completeness. Let P1 = {i1 < i2 < < ir} g {1,2,...,n} and P2 = {l,2,...,n} \ P1. It is clear that ij causes ij —j inversions for all 1 S j S r. Then 1(P1,P2) = in; ~11 = i 713. We let the number of inversions ofrr to be inv(7r) : |{(7r,~,7rJ-): i 7rj }| Recall that we defined the descent set of 7r by Des(7r)={i:7r,->7r.-+1 and 1 SiSn—l }. 4'9 Theorem 3.3.2 Let n and k be any non-negative integers. Then En|k(q) satisfies the following recursion: li—‘J n n— ‘m E(n+1)|k((I) =Z[k JG A +1EMm-l)|k((l)E(n-km+lHit-((1)'l' Mk ll ")En|k((1) (3-19) 1 771—1 where b(-) is the boolean function defined by (3.9). Proof. R. P. Stanley has shown [40, Proposition 3.16.4] that E71|k((]) = Zqinvh') (3.20) where the sum is over all 71' 6 Sn with the descent set Des(vr — —{k, 2k,..l"—;1-J., k}. So it is enough to show that En|k(q) defined by equation (3.20) satisfies (3.19). Let 5,.“ = {7r: 7r 6 Sn“ and Des(rr) : {k,2k,... ,(%J k} } If 7" = 7T17T2m7rn+1 6 511+“ then either 72 + 1 = at," for some 1 S m S lfij or n + 1 2 an“ where k ,l n. One. easily sees that n + 1 : an“ can happen if and only if k ,l' n. Now define 571+, _ -:{7r 7r 6 8,,“ and mm = n +1} for 1 Sm S (L) and ESH— — {7r : 7r 6 5,.“ and an“ : n+1}. It IS clear that 5n+1— — UL“; _J05,’,’3H. Note that k divides n if and only if 83+1 = 0. Hence E(n+l)|k(£[) : Zq inv(1r )_ _Z :(I inv(7r) +b(k If" ) Z qinv(1r). (321) 6‘") .50 Now consider the first summation in equation (3.21). For fixed 7n, 1 S 7n S lfl , and write m 71’ = 7r17r2...7rkm_lj(n + 1) akm+1...7rn+£ E 5,,“ v f T 0' where mm = n + 1. Then inv(7r) = inv(T) + inv(a) + (n — km + 1) + i(7',0) where n—km+1=|{(n+1,7rj):km+1San+1}| and i(T,0) = |{(7r,-,7rJ-) : 7r,- > Tl’j,1 S i S km— 1 and km+1 Sj S n+1}|. Suppose {P1,P2} is a partition of {1,2,...,n} with [Pl] = km — 1. Define 8(P1) to be the set of all permutations of P1 with the descent set {k,2k, . . . , (m — 1)k}. Then there is a one-to-one order-preservmg correspondence between 5( P1) and 81m.“ and Similarly for 5(P2) and 8,,_1.,,,+1. For any 7' = 7172...7'km_1 E 5(P1) and any a : 0102..-0n_k111+1 E £(P2), i(‘r,o) = |{(T,-,aJ-): Ti>aj,lSiSkm—1and1San—km+1}| = |{(a,b):a€P1,b€P2 anda>b}| = I(P1,P2). For any partition {P1, P2} of {1,2, ...,n} with [Pl] 2 km — 1, Z qi11v(7)+ir1v(o) 7' E €(P1)o E 50%) ___. Z qinv(7)+inv(a) T E tkyn—la E gn—km-l-l 51 =1: 1111 2111 1653ka aesn—km-{d = E11..-1)11((1)E1n-km+11IA-((I)- If r is replaced by km — 1 in Lemma 3.3.1, then 2 .11....) = z 2 .11111 weer“ (P115) T E 5(P1) 068(132) 77’ T}.- .771 : lkm—l l q A +1Evan-UIk‘M)Eln-kmflllbiq)‘ It follows that l m arl: l J J I Tl l ‘1" I 2 : inV 71 . (I 1; _ + k 1 «653+, kw M 3 _l_|‘ So we are done if k divides 71. Suppose that k A n. Then there is an extra term 2,653“ qinvm in equation (3.21). Note that the correspondence 7r : alag...7rn(n +1) <=> if = magma" between 52+} and 8,, is one-to—one and order-preserving. Hence Z qi11v(1r) : Z (linv(7r) : En|k(q)- ”683+! "657: This completes the proof of Theorem 3.3.2. I Remark: Observe that when q = 1, we have the recursion for Enlk as in Theo- rem 3.2.4 Theorem 3.3.2 and Theorem 3.2.4 are very useful in further studying the divis- ibility properties of En“. and E,,l1.(q), which will be seen in the next section. To 52 demonstrate this point, we will end this section by a direct application of Theo- rem 3.2.4. We know that (n + 1)E(2n+1)|2 = 22"|ng+2| where 02,.” is the Genocchi number. It can be verified using the exponential generating functions of E(2,,+1)|2 and [GEM-2| as follows: it is well- known [12 ., p. 48- p. 49 ] that. Qt t2n+2 G t = — t G n -——— (1 6+, 1;) 2.21,, +2), and 2 E t2n+l T t = 1+ n —— (l 62" +1 "22% (2 -1-l)|2(2n+ 1)!- Let 2t = s and then t = 5/2. On one hand, .’)t H e2‘+1 tTU)= 2714-2 :1 E, 2- 2————- +71% (2 +1)I2( n + )(277. +2)! _ Z E(2n+1)|2(7l + 1) 82n+2 ‘ 8+ r1 mn+mz' n>0 On the other hand, It follows that (n + 1)E(2n+l)|2 = 22"|ng+2|. Since Genocchi numbers are odd, we see that following theorem is true. Theorem 3.3.3 Let n be a non-negative integer. Then 53 1. 22" divides (n + 1)E(2n+1)|2; 2. (TI. ‘1' 1)E(2n+1)|2/22n i8 Odd. Proof. Using the recursion for Bulk when k = 2, we can now give a direct proof of this theorem without using their generating functions. For brevity, we first define Ei2n+1112 = (71 +1)E(2n+11l2- We first prove (1): Induct on n. The case n = O is trivial. Suppose n > 0 and then ,. ” 2n E(2n+l)|2 = Z ("1 +1)( 1)E(2m-1)|2E(2n-2m+1)|2 "1:, 2m — 1 (11+ 11(25'1.) .. . :. Z 771(77' _ m + 1) E(2m-I)I2E(2n-2m+1)|2 771:1 2 " 2n + 2 . ,, = 2n + 1 "12:; ( 2m )E(2m-l)|2E(2n—2m+l)|2' It follows that ,, , " 2n + 2 _ y (271. + 1)l(:’(2n-{1-1)|2 : ‘2 Z ( 97,” ) E(2m-1)I2E(2n—2m+l)l2' m=1 "' By the induction, we have . 271—2 . . 1t "‘ 2 d1v1des E(2m_1)|2 (2n—2m+l)12 where 1 S m S n. Since 2n + 1 is odd, it is enough to show that " 2n + 2 ‘ _ Z ( )E('2m—1)|2 (2n—2m+l)|2 (3.22) ‘) m=l ..7n 22”"1. Note that for fixed 7n, 1 S m S n, we see that 2n+2 _ 2n+2 _ 2n+2 2m — 2n+2—2m _ 2(n—m+1)° 54 is divisible by Moreover, since 72 — (n — 7n + 1) +1 2 m, 2(n — m + 1) ——1 : 2n — 2m +1 and 2n—2(n—m+1)+1= 27n—1, Also sincel S 7n S n implies that IS n—m+1 S n, it follows that the m-th term equals to the (n — m + 1)-th term in sum (3.22). It follows that sum (3.22) is «7|: 1 2 m 1.1.11.1. Odd) (251141-12) lil Evin-11121"— lgl + ll Eon-21111112 where b() is the boolean function. By the induction, 2m 1 2n + 2 ,_ . ( )E(2m—1)|2E(2n—2m+1)|2 1 2m 71— - - 2n+2 n- :1: . n 22 1 d1V1des 2( ) (2m-1)|2E(2n—2m+1)|2 where 1 S m S l§l° So we are done if n is even. If n is odd, there is an extra term. Now let n = 21 + 1 for some non—negative integer l and then 2n+2 _(2(21+1)+2 __ 2(21+2) (2M)- 2(1+1) )_(21+2) which is divisible by 2, since that the number of carries in adding 21 + 2 to (41 + 4) — (2l + 2) 2 2l + 2 in 2-ary arithmetic is at least 1. Hence the extra term is also divisible by 2271—1 and the result follows. We next prove (2): Induct on n. The n = 0 case is trivial. Now suppose n > 0 and consider Ef2n+1)|2 ___ in: 71 + 1 271 EF2m-1)l2 (Ef2(n-m)+1)|2 22" 22m(n — 7n + 1) 2m — 1 22(m‘1l 22("‘m) 771:1 : 1 En: 2(n + 1) Ef2m—1)|2 Ef2(n—m)+1)|2 2(2n + 1) 2m 221m‘ll 22("‘ml i m=l O = M (2(n-m)+1)|2 m 22(m—1) 22(n—m) 55 Let and then 9271 E‘, 1 n 2 1 (271 +1)——_‘2 “1'2 = 5 ( (n + l) 0.... 1 1 By the induction, Om is an odd number for all Since 2n + 1 is odd, it is enough to show that 1 " 2(n + 1) V = — m (n) 2 7.12::1( 2m ) O is odd for all n 2 1. Note that, by the induction, Om — 1 :— 0 (mod 2) for all 1 S 771 S 71. By [22, (1.91)], we see that "+1 (2n + 2 = 92(n+1)—1 = 22n+l 2m m=0 n .) .) %{Z(~71+~)}=;(2271+l—2)=22n_1 m=l .. 2771. It follows that [v is odd. Now it is enough to show that n (2n+2) V(n)—(22"—1)=Z 2’" (Om—1) m=l is even, since then V(n) must be odd and the result follows. Note that 0... = 0..-...“ for all 1 S m S n. It follows that 111 31:2 = 2 _ (2; )(Om —1)+b(n isodd )£_l_22_l_)_ (0%] —1). It is clear that for 1 S 7n S (€21), (237:2)(0m — 1) is even since each (0... — 1) is even and (237:2) is an integer. Moreover, we have the extra term in the odd-n case is also (2....) even since _2l_:_:fl_ is an integer and 0%.] — 1 is even. Hence V(n) — (22" — 1) is even and then V(n) is odd. I 56 3.4 The Divisibility of the Generalized q-Euler Num- bers G. E. Andrews and I. Gessel have shown [2, Theorem 1 and Theorem 2 ] that 1. E(2n+1)|2(q) is divisible by (1+ q)(1+ q2)...(1+ q”) = [2]]2]2[2]3...[2]n. 2. E(2n+1)|2(q) is divisible by (1 + q)" = [2]". It follows that 2" divides E(2n+1)|2 by letting q 2: 1. We adopt the techniques which G. E. Andrews and I. Gessel have used in their work and extend their results to E(,,k+,-)lk(q) for all prime k 2 2 and 1 S i S k — 1. First, we study some related divisibility properties of certain binomial coefficients and q-binomial coefficients . Lemma 3.4.1 Let k be prime. Then (:53) is divisible by k for all 0 S i S k — 2. Althought Lemma 3.4.1 is just a special case of Theorem 3.4.3 and Theorem 3.4.4, we include a proof here to show a special method used in proving such a problem. Proof. By Kummer’s Theorem [15, p.270, item 71], it is enough to show that the number of carries when adding km — 1 to kN + i — (km — 1) in base k is greater than orequal to 1. Now kN+i-—(km—1) = k(N—k)+(i+1)where1 S(i+1) S k—l and km — 1 = k(7n — 1) + (k — 1). So these two numbers have one’s digit i + 1 and k — 1 in base k. Since (i + 1) + (k — 1) 2 k, we have a carry out of the one’s digit and are done. I In general, q-analogs of these binomial coefficients have the similar divisibility. To show it , we first need the following lemma [24]. 57 Lemma 3.4.2 Up is a primitive ktlz roots of unity, then p is a simple root ofl — qM if and only if kllW. Remark: Note that Lemma 3.4.2 requires the condition that k is prime. Since our proofs are based on Lemma 3.4.2, the condition that k is prime can not be omitted. Also, it is easy to find a counter example to show that this condition is nesessary. Lemma 3.4.3 Let prime k 2 2 and 0 S i S k — 2. For any nonnegative integers n and m, the expression [ kn + i J [k][k]2...[k]m_1 km — l [k]n[k]n_1...[k]n_m+1 is a polynomial in q. Clearly, when q = 1, we have Lemma 3.4.1. Proof. The expression in question is a rational function and the roots of the de- nominator are roots of unity. To prove Lemma 3.4.3, we need only show that each zero of the denominator appears with at least as large multiplicity in the numerator as in the denominator. kn + i km — 1 1 S j S km —— l, j must divide at least (Enf—IJ of the numbers kn + i,kn + i — We know that that [ ] is a polynomial in q. By Lemma 3.4.2, for each 1, ..., k(n — l) + 1, k(n — 1), k(n — l) — 1, ..., kn — km + i + 2 (otherwise this q-binomial coefficient would not be a polynomial). Now kn +2 — (1 _ an+i)(1_ qkn+i-l)...(1_ qkn—km+i+2) (3 23) km —1 — (l — qk""1)(1— (1km—2)---(1 ‘ (12)“ “ (I) i . Since [k],- = (1 — qjk)/(l — q’), we have 1— k 1— 2k... 1— WM) [k][k]2...[k],,,_,=( q“ q l ( ‘1 l (3.24) (1 - q)(1- q2)---(1- qm“) and (1_ an)(1_ qk(n—1))(1_ qk(n-2))u.(1_ (1k(n—m+l)) (1-q")(1-(1"")~-(1-q"‘"‘+‘) ' 58 [klnlkin-l-“ikln—m-l-l : (325) As a result, we have [kllklzmlklm-l [klnlkln—l---[kln—m+1 (1 - (1")(1- (12")...(1 - qk‘m‘”)(l - <1")(1 - (1"“‘).-.(1— q"”"‘+‘) (1 - q"“)(1 - q*(""’)-~(1 - qk‘"'"‘+”)(l - q)(1- q2)-~(1- qm“) Now we get [kn-ti] [ka]2...[k]m—1 _Ql(‘I) (3.26) km —- l — [k]n[k]n_1...[k]n_m+1 Q2(q)’ where Q1(q) and Q2(q) are as follows: (21(0) = (1-qk”+‘)(1 - (1""+“‘) ~-(1-(1k"“)(1-q")(1-qk"“) m(1_qkl’1‘1)+1)(1_qn—l)(1_qk(n—l)—l) ...(1 _ ([k(n—m+l)+l )(1_qn—m+l )(1 _qk(n—m+1)—l) (1_ qk(n-m+1)-2).H(l_ qk(n—m)+i+2) ’ Q2(([) : (1_ qkm—l)(1 _ qkm—2) ...(1 — ([k(7n_l)+l)(1_ qm-l)(1_ qk(m—l)—l) ...(1... (1k(m-2)+l)(l _ (1(m-2))(1_ qk(m—2)-l) ...(1— q*‘+‘)(l — q)(1- q“) -(1— qk'2)---(1— (12)(1— (1)- kn. + i Note that Q1(q)/Q2(q) is almost. same as [ km _ l ] except that the factor (1_ (Ikn)(1_ qk(n—l))”.(1 _ qk(n—m+l)) (1 - (Ik‘m‘l’fil - qk‘m'z’l-(l - (1“) 59 . kn+i 1n km—l ] is replaced by (1 - q")(1- q"“)---(1 - q"‘"‘“) (1 — q)(1- q2)---(1- qm‘l) More precisely, Q1(q)/Q2(q) is same as [ 2:21:21 ] except that each kN exponent in the numerator and denominator has been divided by k. Suppose that 1 S j S km - 1 and jIkN. If k /[ j, then jIkN implies that le. If klj, then flN. Hence we still have that each zero of the denominator of Q1(q)/Q2(q) appears with at least as large multiplicity in the numerator as in the denominator. Thus the divisibility properties previously described are preserved since the only change dose not affect whether a denominator exponent divides a numerator exponent. I Lemma 3.4.4 Let k _>_ 2 be aprime and 0 S i S k—2. For any nonnegative integers kn +i J n and m,[k] is a factor of [ km _ 1 Clearly, when q = 1, we also have Lemma 3.4.]. Proof. For all non-negative integers n and m, we see that [kn +2 J _ (1_ an+i)(1_ qkn+i—l).'.(l _ qk(n-m+1))".(1_ qkn—km+i+2) (3 27) km —1 <1— ,...-,,(1_ qkm-2)...(1— qk)...<1- q2><1— q) By Lemma 3.4.2, for any integer M, 1 — qM has one and only one factor [k] if and only if M is divisible by k. There are n — (n — m) = m factors of [k] in the numerator kn+i and m — 1 factors of [k] in the denominator of[ km 1 ]. As a result, there is one - . kn+i factor [k] m [ km _1 ] . Now we are in the position to prove the divisibility properties of the generalized q-Euler numbers. 60 Theorem 3.4.5 Let k be any prime and 1 S i S k — 1. We have E(nk+,-)Ik(q) is divisible by [k][k]2[k]3...[k]n. Remark: When k = 2, we have the Andrews and Gessel’s first result about the divisibility of the q-tangent numbers in [2]. Proof. Induct on n. For n 2: 0, the result is trivial. Suppose the result is true up to but not including N. By Theorem 3.3.2, we have two cases. Case 1: lfi = 1, then E(k-N+ 1m. (‘11 EN [W U, h - ’— 7 l : [.771 —1]q 1+ EM";-l)|k_(([)E(kN-km+l)]k(q)3 771:] Case 2: HQ S i S k — 1, then E(IW+ .' ) [k ((1) N . ICN+ Z— l . r__ 7,, : 2:[ I.~m(—1)]‘1m i +119(1‘m-1)Ik(‘01—qu—km+i)Ik-(q)“l" Emmi-nah) We first consider case 1. By the induction hypothesis, for all 1 S m S N, E(km—l)|k((l) = [kllkl'zlklsu-lklm—ipi((1) and E(kN-km+l)|k((l) = [k][ls]2[k]3...[k]N-,,.P2(q) where P1(q) and P2(([) are different polynomials in q. Then W [k ]E(A~.m—l)lk((1)E(kN-km+i)|k((ll m —l =[W l MHMQWML’” [kllklzlklsmlklwflWWW)- km — l [k]N[k]N_.1...[k]N_m+1 61 By Lemma 3.4.3, [Iv/V ] [kllk]2.-~[klm_1 km - 1 [k]N[k]N_1...[k]N_m+1 is a polynomial in q. We have that [k][k]2[k]3...[k]N is a factor of LIN km — 1 JE(km—l)|k((1)E(kN—km+l)|k((I) for all 1 S m S N and then a factor of N [ AW "12:; km -1 ] qW—bn-HE(km-1)Ik(q)E(kN—km+i)|k((I)- So the result holds in case 1. For case 2, we see that [k][k]2[k]3...[k]N divides the extra term by an induction on i, where i = l is done in case 1. So the result also holds in case 2. I Theorem 3.4.6 Let k be prime and 1 S i S k — 1. E(k,,+,)lk(q) is divisible by [k]" . Remark: When k = 2, we have the Andrews and Gessal’s second result about the divisibility of q-tangent numbers in [2]. Proof. Induct on n. For n = 0, the result is trivial. Suppose the result is true up to but not including N. By Theorem 3.3.2, we consider the two same cases as in Theorem 3.4.5. Case 1: Ifi = 1, then Emmm-(Q) N W at... 2 Z k (I E(km-l)|k(qlE(kN—km+l)lk(q) Case 2: If? S i S k— 1, then E