Annals of Combinatorics 5 (2001) 305-318
c Birkh¨auser Verlag, Basel, 2001
0218-0006/01/040305-14$1.50+0.20/0
Annals of Combinatorics
Multiset Structures Derived from Vector Spaces Tung-Shan Fu1∗ and Zhe-Xian Wan2,3 1National Pingtung Institute of Commerce, 51 Min-Shen E. Road, Pingtung 900, Taiwan
[email protected] 2Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080,
P.R. China 3Department of Information Technology, Lund University, Box 118, Lund 22100, Sweden
[email protected] Received December 4, 2000 AMS Subject Classification: 05A05, 05A19, 05E20, 06A07
Dedicated to the memory of Gian-Carlo Rota for his great contributions in combinatorics Abstract. Let Dn be an n-dimensional vector space over a division ring D and let a1 , . . . , am be positive integers such that a1 + · · · + am = n. Denoted by T (a1 , . . . , am ; D) the subgroup of GLn (D), consisting of upper triangular block matrices of the form
A11 A12 · · · A1m
0 A22 · · · A2m .. . . . . .. , . . . .
0
···
0 Amm
where Aii ∈ GLai (D), i = 1, . . . , m, and Ai j is an ai × a j submatrix over D, 1 ≤ i < j ≤ m. How the subspaces of Dn are partitioned into orbits under the action of T (a1 , . . . , am ; D) is determined. An isomorphism between the lattice of these orbits and the lattice of submultisets of the multiset {1a1 , 2a2 , . . . , mam } is established. The length of each orbit is also enumerated in case D = GF(q). Moreover, a combinatorial interpretation of a multiset Mahonian statistics is given and two identities of the q-multinomial coefficients are obtained. Keywords: multisets, vector spaces, lattice isomorphism, Mahonian statistics
∗
The first author was supported by National Science Council, Taiwan under grant NSC 89-2115-M251002.
305
306
T.-S. Fu and Z.-X. Wan
1. Introduction Let GF(q)n denote an n-dimensional vector space over GF(q). In 1970, Goldman and Rota [4] initiated a systematic study of the enumerative analogy between the lattice L (GF(q)n ) of subspaces of GF(q)n and the lattice L (B) of subsets of an n-element set B. They asked for a combinatorial interpretation of the phenomena that the q-analog identities obtained from enumeration of subspaces in L (GF(q)n ) always tend to their ordinary ones in L (B) as q tends to 1. Recently, based on the order-preserving map, proposed by Knuth [5], from k-dimensional subspaces into k-subsets, Wang [9] established a lattice isomorphism between certain quotient lattice of L (GF(q) n ) and the lattice L (B), which contributed an insight to such a subset-subspace analogy. This isomorphism is generalized to the extent of multisets in the present paper. Let a1 , a2 , . . . , am be positive integers with a1 + a2 + · · · + am = n and let M = {1a1 , 2a2 , . . . , mam } denote the multiset of cardinality n consisting of ai copies of i for i = 1, 2, . . . , m. Let D be any division ring and let Dn = { (x1 , x2 , . . . , xn ) | xi ∈ D, i = 1, 2, . . . , n} be the n-dimensional row vector space over D. Let A11 A12 · · · A1m 0 A22 · · · A2m T = . . . . . . . . ... .
0 · · · 0 Amm
,
(1.1)
where Aii ∈ GLai (D), i = 1, . . . , m, and Ai j is an ai × a j submatrix (or block) over D, 1 ≤ i < j ≤ m. Clearly, the set of all such a matrix T , denoted by T (a1 , . . . , am ; D), forms a subgroup of GLn (D). How the subspaces of Dn are partitioned into orbits under the action of T (a1 , . . . , am ; D) is investigated (Proposition 2.2), and a lattice isomorphism between the lattice of these orbits and the lattice L (M) of submultisets of M is established (Theorem 2.5) in Section 2. Meanwhile, the length of each orbit is also enumerated in case D is a finite field. A Mahonian statistics over permutations of multisets is also considered. A permutation of M is an ordering z1 z2 · · · zn of all the elements it contains. Let S (M) denote the set of all permutations of M. Clearly, n , (1.2) |S (M)| = a1 , a2 , . . . , am n where a1 , a2n,...,am = n!/(a1!a2 ! · · · am !) is the multinomial coefficient. Note that 1, 1,...,1 = n! and S (M) coincides with the symmetric group Sn if M = {1, 2, . . . , n}. For a permutation π = z1 z2 · · · zn of M, define inv(π) := | {(zi , z j )| i < j and zi > z j } | to be the inversion number of π. For example, if π = 2313121, a permutation of the multiset {13 , 22 , 32 }, then inv(π) = 11. The inversion number inv is a typical example
Multiset Structures Derived from Vector Spaces
307
of (multiset) Mahonian statistics (see [6] or [7, p. 26]), namely
∑ qinv(π) = [n]!,
(1.3)
(1.4)
π∈Sn
and
∑
π∈S (M)
q
inv(π)
n = , a1 , a2 , . . . , am
where [n]! = [1][2] · · · [n], [i] = 1 + q + q2 + · · · + qi−1 , and
[n]! n = [a1 ]![a2 ]! · · · [am ]! a1 , a2 , . . . , am
is the q-multinomial coefficient. Note that (1.3) tends to the identity |S n | = n! and (1.4) tends to (1.2) as q tends to 1. The q-multinomial coefficient is shown to coincide with the index of the subgroup T (a1 , . . . , am ; GF(q)) in GLn (q) in Section 3. A combinatorial interpretation of the term qinv(π) in (1.3) was given by Wang [9, Theorem 3.1]. His argument is extended to interpret the term qinv(π) in (1.4) (Theorem 3.3). Finally, using the multiset Mahonian statistics and the combinatorial interpretation of the term q inv(π) in (1.4), two identities involving q-multinomial coefficients are derived in Section 4. 2. Quotient Lattices Derived from Vector Spaces over Division Rings In this section, we study the lattice formed by the orbits of subspaces of D n under the action of T (a1 , . . . , am ; D). Let P be a k-dimensional subspace of Dn and denote also by P a matrix representation of the subspace P, i.e., P is a k × n matrix over D the rows of which span the subspace P. Let R(P) denote the reduced row echelon form of the matrix P, i.e., if we write v1 . R(P) = .. , vk
where v1 , . . . , vk are the rows of R(P), then (i) the first nonzero entry of each row is 1 (called pivot 1); (ii) the pivot 1 of vi+1 appears in a column to the right of the pivot 1 of vi , i = 1, . . . , k − 1; and (iii) each pivot 1 is the only nonzero entry in its column. Knuth [5] observed that each subspace of GF(q)n has a unique canonical basis. We prove a similar result over Dn .
Lemma 2.1. The map P → R(P) from the set of subspaces of Dn to the set of reduced row echelon forms is bijective. Proof. First, we show that the map is well-defined. Let P1 and P2 be two matrix representations of the subspace P and let R(P1 ) and R(P2 ) be the corresponding reduced row
308
T.-S. Fu and Z.-X. Wan
echelon forms. Assume that dim P = k and let v1 u1 . . R(P1 ) = .. and R(P2 ) = .. . vk
uk
Suppose that the pivot 1 of vi (and ui ) is in the si -th column (resp. the ti -th column), i = 1, 2, . . . , k. Then s1 < s 2 < · · · < s k
and t1 < t2 < · · · < tk .
Without loss of generality, we assume that sk ≥ tk . Since R(P1 ) and R(P2 ) span the same subspace, vk = λ 1 u 1 + · · · + λ k u k , (2.1) for some λi ∈ D, i = 1, . . . , k. Comparing the coordinates of both sides of (2.1), we have λ1 = · · · = λk−1 = 0,
λk = 1,
and sk = tk .
Hence vk = uk . Similarly, we assume that sk−1 ≥ tk−1 . Therefore, vk−1 = µ1 u1 + · · · + µk−1 uk−1 + µk uk ,
(2.2)
for some µi ∈ D, i = 1, . . . , k. Comparing the coordinates of both sides of (2.2), we have µ1 = · · · = µk−2 = 0, µk−1 = 1, and sk−1 = tk−1 . It follows that vk−1 = uk−1 + µk uk .
(2.3)
Observe that both the sk -th coordinate of vk−1 and the tk -th coordinate of uk−1 are 0’s since the only nonzero entry in the sk -th column of R(P1 ) (and the tk -th column of R(P2 )) is the pivot 1 of vk (resp. uk ) and sk = tk . Comparing the sk -th coordinates of both sides of (2.3), we have µk = 0. Consequently, vk−1 = uk−1 . Proceeding in this way, we obtain successively si = ti and vi = ui for i = k − 2, k − 3, . . . , 1. Hence R(P1 ) = R(P2 ) and the map P → R(P) is well-defined. That the map P → R(P) is bijective is easy to prove. The following proposition shows how the subspaces of Dn are partitioned into orbits under the action of T (a1 , . . . , am ; D). Proposition 2.2. Let P be a k-dimensional subspace of Dn and let R(P) be the reduced row echelon form of P. Then there exists a matrix T ∈ T (a1 , . . . , am ; D) such that (Ib1 0) (Ib2 0) R(P)T = (2.4) , .. . (Ibm 0)
where 0 ≤ bi ≤ ai , i = 1, . . . , m, b1 + · · · + bm = k, and (Ibi 0) is a block of size bi × ai . Moreover, b1 , . . . , bm are uniquely determined by P.
Multiset Structures Derived from Vector Spaces
309
Proof. Write R(P) in block form
R(P) =
B11 B12 · · · B1m
0 B22 · · · B2m , .. .. . . . . . . . .
0 · · · 0 Bmm
where Bii is of size bi × ai and rank bi . Clearly, 0 ≤ bi ≤ ai and b1 + · · · + bm = k. There is an ai × ai permutation matrix Pi such that Bii Pi = (Ibi ∗). Let
T1 =
P1
0
P2 ..
0
. Pm
Then T1 ∈ T (a1 , . . . , am ; D) and
R(P)T1 =
(Ib1 ∗)
∗
.
∗ ···
∗
(Ib2 ∗) ∗ · · ·
∗
.. .. . .
.. .
∗ (Ibm ∗)
.
Clearly, there is a T2 ∈ T (a1 , . . . , am ; D) such that R(P)T1 T2 is of the form (2.4). To prove the uniqueness, assume that
R(P)T 0 =
(Ib01 0) (Ib02 0) ..
. (Ib0m 0)
,
where (Ib0i 0) is a b0i × ai block, 0 ≤ b0i ≤ ai and b01 + · · · + b0m = k. Then
(Ib1 0) (Ib2 0) ..
. (Ibm 0)
−1 0 T T =
(Ib01 0) (Ib02 0) ..
. (Ib0m 0)
.
(2.5)
310
T.-S. Fu and Z.-X. Wan
Comparing the ranks of the first a1 + · · · + ai columns of both sides of (2.5) gives b1 + · · · + bi ≥ b01 + · · · + b0i for i = 1, . . . , m since each column of which on the right-hand side is a linear combination of the ones on the left-hand side. Multiplying T 0−1 T on both sides of (2.5) yields b01 + · · · + b0i ≥ b1 + · · · + bi , i = 1, . . . , m. Hence bi = b0i for i = 1, . . . , m. The sequence (b1 , . . . , bm ) above is called the type of a subspace the reduced row echelon form of which is equivalent to (2.4) under T (a1 , . . . , am ; D). Corollary 2.3. (i) Two subspaces of Dn belong to the same orbit under the action of T (a1 , . . . , am ; D) if and only if they are of the same type. (ii) The number of orbits of subspaces in Dn under the action of T (a1 , . . . , am ; D) is m
∏(ai + 1). i=1
(iii) In case D is the finite field GF(q), the length of the orbit consisting of subspaces of type (b1 , . . . , bm ) is ! ! m ai bi (a j −b j ) . ∏ bi ∏ q i=1 1≤i< j≤m Proof. (i) is easily obtained by Lemma 2.1 and Proposition 2.2. (ii) follows immediately by (i) and counting the number of sequences (b1 , . . . , bm ) with 0 ≤ bi ≤ ai for i = 1, . . . , m. (iii) By Lemma 2.1, each subspace P of type (b1 , . . . , bm ) corresponds to a unique reduced row echelon form of the form P11 P12 · · · P1m 0 P22 · · · P2m R(P) = . . . , . . . . . .. . . 0 · · · 0 Pmm
where Pii is a reduced row echelon form of size bi × ai , i = 1, . . . , m, and Pi j is a block of size bi × a j , 1 ≤ i < j ≤ m. To compute the length of this orbit, count the possibilities for R(P). Observe that by Lemma 2.1, all of the possibilities of Pii constitute the set of bi -dimensional subspaces contained in an ai -dimensional subspace, i = 1, . . . , m. Moreover, there are qbi (a j −b j ) possibilities for Pi j , 1 ≤ i < j ≤ m, since all entries of Pi j are arbitrary but the entries lying in the same column with each of the b j pivot 1’s of Pj j are 0’s. Corollary 2.4. Let D = GF(q). Then (i)
∑
(b1 ,...,bm ) 0≤bi ≤ai b1 +···+bm =k
! n ai bi (a j −b j ) = . ∏ bi · ∏ q k 1≤i< j≤m i=1 m
(2.6)
Multiset Structures Derived from Vector Spaces
(ii)
∑
(b1 ,...,bm ) 0≤bi ≤ai b1 +···+bm =k
311
! ai n ∏ bi = k . i=1 m
(2.7)
Proof. Observe that the union of the orbits consisting of subspaces of type (b 1 , . . . , bm ) with b1 + · · · + bm = k constitutes the set of all k-dimensional subspaces of GF(q)n . Thus we have the identity (2.6). Clearly, (2.7) is an immediate consequence of (2.6) as q tends to 1. It is worth mentioning that when m = 2, (2.6) and (2.7) reduce to the following well known identities, respectively: k a1 a2 a1 + a 2 b(a2 −k+b) q = (cf. [1, p. 225]), ∑ k−b k b=0 b a1 a2 a1 + a 2 = ∑ k−b k b=0 b k
(cf. [2, p. 27]).
Define an equivalence relation ∼ in L (Dn ). For any P, Q ⊆ Dn , define P ∼ Q if and only if P and Q belong to the same orbit under the action of T (a 1 , . . . , am ; D). Let [P] denote the equivalence class containing P. For any P, Q ⊆ Dn , define [P] ≤ [Q] if and only if there are T1 , T2 ∈ T (a1 , . . . , am ; D) such that PT1 ⊆ QT2 . If P is of type (b1 , . . . , bm ) and Q is of type (b01 , . . . , b0m ), then [P] ≤ [Q] if and only if bi ≤ b0i for i = 1, . . . , m. It is easy to verify that L (Dn )/ ∼ is also a lattice. Let P be a kdimensional subspace of Dn . By Lemma 2.1, R(P) is uniquely determined by P, and by Proposition 2.2, (2.4) is uniquely determined by R(P). Thus the map
L (Dn ) −→ L (M) (2.8) P 7−→ {1b1 , 2b2 , . . . , mbm } is well-defined and order-preserving. Moreover, by Corollary 2.3(i), we have Theorem 2.5. The map (2.8) induces an isomorphism of lattices
L (Dn )/ ∼ −→ L (M) [P] 7−→ {1b1 , 2b2 , . . . , mbm } where b1 , b2 , . . . , bm are determined by [P] in Proposition 2.2. Remark. The case M = {1, 2, . . . , n}, i.e., a1 = · · · = am = 1 and m = n, in Theorem 2.5 is the Structure Theorem of Wang [9]. 3. An Interpretation of a Mahonian Statistics From now on, we specialize the division ring to GF(q) and denote T (a 1 , . . . , am ; GF(q)) simply by T (a1 , . . . , am ; q). The index of T (a1 , . . . , am ; q) in GLn (q) can therefore be evaluated.
312
T.-S. Fu and Z.-X. Wan
Proposition 3.1. We have [GLn (q) : T (a1 , . . . , am ; q)] =
n . a1 , a2 , . . . , am
Proof. It is well known [8, p. 5] that n
|GLn (q)| = qn(n−1)/2 ∏(qi − 1) = [n]!(q − 1)nqn(n−1)/2. i=1
To compute |T (a1 , . . . , am ; q)|, count the possibilities of the blocks Ai j in (1.1) for members of T (a1 , . . . , am ; q). Clearly, there are |GLai (q)| possibilities for the diagonal blocks Aii , i = 1, 2, . . . , m, and there are qai a j possibilities for the blocks Ai j , 1 ≤ i < j ≤ n, since all entries of Ai j are arbitrary. Hence ! ! m
| T (a1 , . . . , am ; q) | =
∏ |GLai (q)| i=1
∏
q ai a j
1≤i< j≤m
= [a1 ]![a2 ]! · · · [am ]!(q − 1)nqn(n−1)/2, as required. We shall identify each right coset of T (a1 , . . . , am ; q) in GLn (q) with a specific matrix it contains, which is called the normal form defined below, and then show that qinv(π) corresponds to the number of normal forms related to π. Let X ∈ GLn (q) and write x1 . X = .. , xn
where x1 , . . . , xn are the rows of X. Let the row-indices of X be partitioned into the m segments [1, s1 ], [s1 + 1, s2 ], . . . , [sm−1 + 1, sm ], where si = a1 + · · · + ai , i = 1, . . . , m. Observe that the right coset T (a1 , . . . , am ; q)X containing X is invariant under the following elementary row-operations since each row-operation is a transformation T X for some T ∈ T (a1 , . . . , am ; q): (I) replace the row xk by λxk for any nonzero constant λ and 1 ≤ k ≤ n; (II) replace the row xk by xk + λx j if either j > k, or j and k belong to the same segment; and (III) interchange any two rows x j and xk if j and k belong to the same segment.
A matrix Y ∈ GLn (q) is called a normal form with respect to (a1 , . . . , am ) if the following conditions (i) to (iii) are satisfied: (i) The first nonzero entry in each row and each column of Y is 1, i.e., the pivot 1. (ii) Suppose that the pivot 1 of the i-th row of Y occurs in the ci -th column. Then c1 c2 . . . cn is a permutation of {1, . . . , n} such that csk−1 +1 < csk−1 +2 < · · · < csk for k = 1, 2, . . . , m, where we agree that s0 = 0.
Multiset Structures Derived from Vector Spaces
313
(iii) Suppose that the pivot 1 of the j-th column of Y occurs in the r j -th row. Then r1 r2 · · · rn is a permutation of {1, . . . , n} and for each i > r j , yi j = 0 if i 6∈ {r1 , r2 , . . . , r j−1 }. Proposition 3.2. Each right coset of T (a1 , . . . , am ; q) in GLn (q) contains a unique normal form. Proof. Let X ∈ GLn (q). First, we locate a normal form of the coset T (a1 , . . . , am ; q)X. (0) Initially, put X = X0 = (xi j ), and select the last nonzero entry in the first column of X0 , (0)
(0)
say xr1 1 . Normalize xr1 1 to 1 and eliminate the entries above it using row-operations of (1)
type (I) and (II). Denote the new matrix by X1 = (xi j ). Next, select the last nonzero (1)
(1)
entry, say xr2 2 , in the second column of X1 such that r2 6= r1 . Then normalize xr2 2 to (1)
1 and eliminate the entries above it and the entries xi2 if i and r2 belong to the same (2) segment. Denote the new matrix by X2 = (xi j ). Repeat this process column by column ( j−1)
under the criteria that the last nonzero entry in the j-th column of X j−1 , say xr j j , ( j−1)
is selected and normalized to 1, where r j 6∈ {r1 , r2 , . . . , r j−1 }, and the entries xi j in the j-th column of X j−1 are eliminated if either i < r j , or i and r j belong to the same segment for j = 3, . . . , n. Finally, applying a series of row-operations of type (III) on Xn , we eventually obtain a matrix Y in T (a1 , . . . , am ; q)X satisfying conditions (i) to (iii). Now, let us prove the uniqueness. Suppose that both Y and Z are normal forms of the coset T (a1 , . . . , am ; q)X. That is, there is a T ∈ T (a1 , . . . , am ; q) such that TY = Z. Write T in the form of (1.1), where Aii ∈ GLai (q), i = 1, . . . , m and Ai j is an ai × a j block over GF(q), 1 ≤ i < j ≤ m, and write Z1 Y1 . . Y = .. and Z = .. , Zm
Ym
where Yi and Zi are ai × n blocks over GF(q). Clearly, AmmYm = Zm .
(3.1)
Let Ym = (yi j ) and Zm = (zi j ), 1 ≤ i ≤ am and 1 ≤ j ≤ n. Suppose that the pivot 1 of the i-th row of Ym occurs in the ti -th column, i = 1, . . . , am . By (ii), t1 < t2 < · · · < tam . Write 1 0 0 0 1 0 .. Y 0 0 Y Y Y · · · Y Ym = m2 m3 m, am . m, am +1 m1 . . .. .. 0 0
and
0
1
Zm = Zm1 z1 Zm2 z2 Zm3 · · · Zm, am zam Zm, am +1 ,
314
T.-S. Fu and Z.-X. Wan
where both Ym1 and Zm1 have t1 − 1 columns, both Ymi and Zmi have ti −ti−1 − 1 columns for i = 2, . . . , am , both Ym, am +1 and Zm, am +1 have n − tam columns, and zi ’s are column vectors. Since Y is a normal form, Ym1 = 0. From (3.1) we deduce Zm1 = AmmYm1 = 0 and z1 = Amm t (1, 0, . . . , 0) 6= 0. Since Z is a normal form, z1 = t (1, 0, . . . , 0). Hence Amm t (1, 0, . . . , 0) = t (1, 0, . . . , 0), which implies
Amm =
1
. .. ∗ .
0
0
Since Y is a normal form, Ym2 is of the form
Ym2 =
y1,t1 +1 · · · y1,t2 −1 0
···
0
.. .
..
.
.. .
0
···
0
.
It follows that Zm2 = AmmYm2 = Ym2 and z2 = Amm t (0, 1, 0, . . . , 0) 6= 0. Since Z is a normal form, z2 = t (0, 1, 0, . . . , 0). Hence Amm t (0, 1, 0, . . . , 0) = t (0, 1, 0, . . . , 0), which implies 10 01 0 0 ∗ . Amm = . . .. .. 00
Proceeding in this way, we obtain finally Zm = Ym and Amm = Iam . From TY = Z we deduce Am−1, m−1Ym−1 + Am−1, mYm = Zm−1 . (3.2) Since Y and Z are normal forms and Zm = Ym , the ti -th columns of Ym−1 and Zm−1 are zero vectors for i = 1, . . . , am . From (3.2) it follows that Am−1, m = 0 and hence Am−1, m−1Ym−1 = Zm−1 .
(3.3)
Applying the above argument and (3.3), we obtain Zm−1 = Ym−1 and Am−1, m−1 = Iam−1 . Repeat the process block by block, we have Zi = Yi , i = 1, . . . , m and hence Z = Y . Let [X] denote the right coset of T (a1 , . . . , am ; q) containing X. A permutation π([X]) ∈ S (M) is associated with [X], which is derived from r1 r2 . . . rn , obtained in the proof of Proposition 3.2, by converting ri to the number k if ri belongs to the k-th
Multiset Structures Derived from Vector Spaces
315
segment, i.e., sk−1 + 1 ≤ ri ≤ sk . Let Ω(a1 , . . . , am ) denote the set of all normal forms with respect to (a1 , . . . , am ). Then GLn (q)/T (a1 , . . . , am ; q) = { [Y ] | Y ∈ Ω(a1 , . . . , am )} and GLn (q) =
[
[Y ].
Y ∈Ω(a1 ,...,am )
Hence we obtain a map φ : Ω(a1 , . . . , am ) → S (M) by Y 7→ π([Y ]). Theorem 3.3. Let M = {1a1 , 2a2 , . . . , mam } be a multiset of cardinality n and let π be any permutation of M. Then the number of normal forms Y with respect to (a 1 , . . . , am ) satisfying φ(Y ) = π is qinv(π) . Proof. The set φ−1 (π) of normal forms can be retrieved in the following way: convert π to a permutation b π = r1 r2 . . . rn of {1, . . ., n} by replacing the ak k’s in π with sk−1 + 1, sk−1 + 2, . . . , sk from left to right for k = 1, . . . , m, where sk = a1 + · · · + ak . Let Ybπ = (yi j ) be the permutation matrix with respect to b π, i.e., yi j = 1 if i = r j , and 0 otherwise. Clearly, Ybπ ∈ Ω(a1 , . . . , am ) and φ([Ybπ ]) = π. Then replace the zero entries yi j in the j-th column of Ybπ by an arbitrary number if i > r j and i ∈ {r1 , r2 , . . . , r j−1 } for j = 2, . . . , n. Observe that ∑nj=2 | { ri | ri > r j and 1 ≤ i ≤ j − 1} | = inv(π). Hence |φ−1 (π)| = qinv(π) . For example, if π = 2313121, then b π = 4617253 and the normal forms in φ−1 (π) ⊆ Ω(3, 2, 2) are of the form 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 * 0 * 0 * , 0 0 0 0 0 1 * 0 1 * 0 * * * 0 0 0 1 * * *
where ∗ denotes an arbitrary element of GF(q).
Remark. The case M = {1, 2, . . . , n}, i.e., a1 = · · · = am = 1 and m = n, in Theorem 3.3 is due to Wang [9, Theorem 3.1]. From Propositions 3.1, 3.2 and Theorem 3.3 we deduce the multiset Mahonian statistics anew. Theorem 3.4. ([6] or [7, p. 26]) Let M = {1a1 , 2a2 , . . . , mam } be a multiset of cardinality n, i.e., a1 + a2 + · · · + am = n. Then n inv(π) . q = ∑ a1 , a2 , . . . , am π∈S (M)
316
T.-S. Fu and Z.-X. Wan
4. Two Identities of q-Multinomial Coefficients In this section, we give combinatorial proofs of the identities (4.4) and (4.5) below by counting the number of normal forms defined in Section 3. Let a1 , . . . , am be positive integers with a1 +· · ·+am = n. Recall that Ω(a1 , . . . , am ) ⊆ GLn (q) denotes the set of all normal forms with respect to (a1 , . . . , am ) and the rowindices of members of Ω(a1 , . . . , am ) are partitioned into the m segments [1, s1 ], [s1 + 1, s2 ], . . . , [sm−1 + 1, sm ], where si = a1 +· · · + ai , i = 1, . . . , m. By Propositions n 3.1 and 3.2, we have |Ω(a1 , . . . , am )| = a1 ,...,a . m Theorem 4.1.
(i) We have
m n n−1 =∑ qa1 +···+ai−1 . a1 , . . . , am a , . . . , a , a − 1, a , . . . , a 1 i−1 i i+1 m i=1
(4.4)
(ii) For any positive integer k with k < n, we have
n = a1 , . . . , am
∑
(b1 ,...,bm ) 0≤bi ≤ai b1 +···+bm =k
k b1 , . . . , bm
n−k a1 − b 1 , . . . , am − b m
∏
qb j (ai −bi ) .
1≤i< j≤m
(4.5) Proof. (i) Let Y ∈ Ω(a1 , . . . , am ). Suppose that the pivot 1 of the first column of Y occurs in the (si−1 + 1)-th row for some i, 1 ≤ i ≤ m, i.e., the first row of the i-th segment. Observe that the (n − 1) × (n − 1) matrix Yb obtained from Y by deleting the first column and the (si−1 + 1)-th row is a normal form in Ω(a1 , . . . , ai−1 , ai − 1, ai+1 , . . . , am ) ⊆ GLn−1 (q). Moreover, there are qa1 +···+ai−1 possibilities of Y ∈ Ω(a1 , . . . , am ) the induced submatrices Yb of which coincide with the same member of Ω(a1 , . . . , ai−1 , ai − 1, ai+1 , . . . , am ). Hence (i) follows. (ii) Given a matrix Y ∈ Ω(a1 , . . . , am ), we write Y = (PY QY ), where PY is the n × k submatrix of Y consisting of the first k columns of Y and QY is the n × (n − k) submatrix of Y consisting of the other n − k columns of Y . Define the matrix Y to be of type (b1 , . . . , bm ) if there are bi pivot 1’s of Y occurred among the ai rows of the i-th segment of PY , where 0 ≤ bi ≤ ai , i = 1, . . . , m, and b1 + · · · + bm = k. Clearly, there are ai − bi pivot 1’s of Y occurred among the rows of the i-th segment of QY . Observe that the k × k matrix PbY formed by the nonzero rows of PY is a normal form in bY formed by the n − k rows Ω(b1 , . . . , bm ) ⊆ GLk (q) and the (n − k) × (n − k) matrix Q of QY containing pivot 1’s is a normal form in Ω(a1 − b1 , . . . , am − bm ) ⊆ GLn−k (q). Moreover, given a pair of normal forms A ∈ Ω(b1 , . . . , bm ) and B ∈ Ω(a1 − b1 , . . . , am −bm ), there are ∏ qb j (ai −bi ) normal forms Y ∈ Ω(a1 , . . . , am ) of type (b1 , . . . , bm ) 1≤i< j≤m
bY of which coincide with A and B, respectively. the pair of induced submatrices PbY and Q Hence (ii) follows.
Multiset Structures Derived from Vector Spaces
317
For example, take n = 7, k = 4 and normal forms Y ∈ Ω(3, 2, 2) of the form 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 Y = 1 0 * 0 * 0 * . 0 0 0 0 0 1 * 0 1 * 0 * * * 0 0 0 1 * * *
Observe that Y is of type (1, 1, 2) and the induced submatrices bY ∈ Ω(2, 1, 0) of Y are Q 0 0 1 0 1 0 1 0 * 0 b PbY = 0 1 * 0 and QY = 0 0 0 1 0 0 0 1
PbY ∈ Ω(1, 1, 2) and 0
1 . *
As q tends to 1, the identities (4.4) and (4.5) tend to the following well known identities of multinomial coefficients, respectively (cf. [2, pp. 33–34]). m n−1 n , = ∑ a1 , . . . , am i=1 a1 , . . . , ai−1 , ai − 1, ai+1 , . . . , am n k n−k = . ∑ a1 , . . . , am b1 , . . . , bm a1 − b 1 , . . . , am − b m (b1 ,...,bm ) 0≤bi ≤ai b1 +···+bm =k
Acknowledgments. The first author would like to thank Professor J. Wang for informing him that Feng [3] obtained the same results in Section 3 independently. The second author would like to thank the National Center for Theoretical Sciences (Mathematics Division), Hsinchu, Taiwan for their financial support and hospitality for his visit to the Center. The present work was finished during the visit.
References 1. 2. 3. 4.
G.E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976. C. Berge, Principles of Combinatorics, Academic Press, New York, 1971. H. Feng, The Mahonian statistic, manuscript. J.R. Goldman and G.-C. Rota, On the foundations of combinatorial theory IV: finite vector spaces and Eulerian generating functions, Stud. Appl. Math. 49 (1970) 239–258. 5. D.E. Knuth, Subsets, subspaces, and partitions, J. Combin. Theory 10 (1971) 178–180. 6. P.A. MacMahon, Combinatory Analysis, Vols. 1 and 2, Cambridge Univ. Press, Cambridge, 1915, reprinted by Chelsea, New York, 1955.
318
T.-S. Fu and Z.-X. Wan
7. R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, Monterey, California, 1986. 8. Z. Wan, Geometry of Classical Groups over Finite Fields, Studentlitteratur, Lund, 1993. 9. J. Wang, Quotient sets and subset-subspaces analogy, Adv. Appl. Math. 23 (1999) 333–339.