二项式系数恒等式的q-模拟
|
摘要
B_n是n元集合{1,2,…,n}的所有子集组成的布尔格,V_n(q)是q元有限域GF(q)上的n维向量空间,L_n(q)是由V_n(q)的所有子空间构成的子空间格。布尔格B_n与子空间格L_n(q)之间的q-模拟是指把布尔格B_n上的一些性质和恒等式推广到子空间格L_n(q)上,在子空间格L_n(q)上找到它们的q-模拟形式,其中q是参量,当q→1时,q-模拟趋向于布尔格B_n上相应的性质。
恒等式的组合证明赋予了恒等式一定的计数意义,组合证明最常用的方法是通过构造两个集合之间的双射,这两个集合的个数分别表示恒等式的两端,从而根据双射的一一对应性证明恒等式。本文也正是采用了这种方法对恒等式进行组合证明。
本文给出了一些重要的二项式系数和高斯系数恒等式的组合证明,其中突出的成果是给出了三个求和公式的q-模拟及其组合证明。
文章主要内容可概括如下:
1.介绍了一些与二项式系数恒等式的q-模拟有关的基本知识,如:偏序集,格,组合证明,二项式系数等。
2.给出了一些经典的二项式系数恒等式及其组合证明。
3.引入q-模拟的概念,给出了一些二项式系数恒等式的q-模拟及组合证明,并介绍了子集-子空间模拟的一般方法及多重集上的Mahonian statistic。
4.给出了三个求和公式的q-模拟及组合证明。
Let B_n be the Boolean lattice of subsets of an n-element set {1,2,…,n},and V_n(q) a n-dimensional vector space over the finite field GF(q) with q elements,L_n(q) its lattice of subspaces.The q-analogue between L_n(q) and B_n means that some qualities and identities on the Boolean lattice B_n are extended onto the lattice of subspaces L_n(q),then their q-analogues are discovered on the lattice of subspaces L_n(q),where q is an parameter.While taking the limit q→1,the q-analogues become corresponding qualities on the Boolean lattice B_n.
By the combinatorial proof,the identity is equipped with certain count meaning.The most general way in the combinatorial proofs is to count two sides of the identity by two different methods.Generally,through building a bijection from one set to another one,the number of the two sets respectively represents the two sides of the identity.Because of the one-to-one property of bijection,the identity is proved.This thesis just applies this method to give the combinatorial proof of identities.
In the thesis some classical identities with binomial coefficient are given with their combinatorial proof,and the q-analogues of some identities are offered with corresponding combinatorial proofs on the lattice of subspaces.Especially,one remarkable result is that q-analogues of three binomial coefficient identities are obtained with their combinatorial proof on the vector space.
The main content of this thesis can be summarized as follows:
1.Introduce some basic knowledge about the q-analogue,such as poset,lattice,combinatorial proof,binomial coefficient and so on.
2.Some classical identitis are provided with their combinatorial proof on the Boolean lattice B_n.
3.Introduce the concept of q-analogue,q-analogues of some classical identities are given with their combinatorial proofs on the vector space.We also offer a general method of subsetsubspace analogy and introduce the multiset Mahonian statistics.
4.q-Analogues of three identities are obtained with its combinatorial proofs on the vector space.
恒等式的组合证明赋予了恒等式一定的计数意义,组合证明最常用的方法是通过构造两个集合之间的双射,这两个集合的个数分别表示恒等式的两端,从而根据双射的一一对应性证明恒等式。本文也正是采用了这种方法对恒等式进行组合证明。
本文给出了一些重要的二项式系数和高斯系数恒等式的组合证明,其中突出的成果是给出了三个求和公式的q-模拟及其组合证明。
文章主要内容可概括如下:
1.介绍了一些与二项式系数恒等式的q-模拟有关的基本知识,如:偏序集,格,组合证明,二项式系数等。
2.给出了一些经典的二项式系数恒等式及其组合证明。
3.引入q-模拟的概念,给出了一些二项式系数恒等式的q-模拟及组合证明,并介绍了子集-子空间模拟的一般方法及多重集上的Mahonian statistic。
4.给出了三个求和公式的q-模拟及组合证明。
Let B_n be the Boolean lattice of subsets of an n-element set {1,2,…,n},and V_n(q) a n-dimensional vector space over the finite field GF(q) with q elements,L_n(q) its lattice of subspaces.The q-analogue between L_n(q) and B_n means that some qualities and identities on the Boolean lattice B_n are extended onto the lattice of subspaces L_n(q),then their q-analogues are discovered on the lattice of subspaces L_n(q),where q is an parameter.While taking the limit q→1,the q-analogues become corresponding qualities on the Boolean lattice B_n.
By the combinatorial proof,the identity is equipped with certain count meaning.The most general way in the combinatorial proofs is to count two sides of the identity by two different methods.Generally,through building a bijection from one set to another one,the number of the two sets respectively represents the two sides of the identity.Because of the one-to-one property of bijection,the identity is proved.This thesis just applies this method to give the combinatorial proof of identities.
In the thesis some classical identities with binomial coefficient are given with their combinatorial proof,and the q-analogues of some identities are offered with corresponding combinatorial proofs on the lattice of subspaces.Especially,one remarkable result is that q-analogues of three binomial coefficient identities are obtained with their combinatorial proof on the vector space.
The main content of this thesis can be summarized as follows:
1.Introduce some basic knowledge about the q-analogue,such as poset,lattice,combinatorial proof,binomial coefficient and so on.
2.Some classical identitis are provided with their combinatorial proof on the Boolean lattice B_n.
3.Introduce the concept of q-analogue,q-analogues of some classical identities are given with their combinatorial proofs on the vector space.We also offer a general method of subsetsubspace analogy and introduce the multiset Mahonian statistics.
4.q-Analogues of three identities are obtained with its combinatorial proofs on the vector space.
引文
[1]I.Anderson,Combinatorics of Finite Sets,Oxford University Press,Oxford,1989.
[2]G.E.Andrews and D.Bressoud,Identities in combinatorics Ⅲ:Further aspects of ordered set sorting,Discrete Math.49 pp.223 1984.
[3]E.A.Bender,A generalized q-binomial vandermonde convolution,Discrete Math.l(2) 115-1191971.
[4]E.A.Bender and J.R.Goldman,On the applications of MSbius inversion in combinatorial analysis,Amer.Math.Monthly 82(1975),789-803.
[5]A.Benjamin,M.E.Orrison,Two quick combinatorial proofs of Σ=_(k=1)~n k~3=((?))~2,The College Math Journal,33(2002),406-408.
[6]L.Carlitz,Some inverse relations,Duke Math.J.40 893-901 1973.
[7]W.Y.C.Chen and G.C.Rota,q-analogs of the inclusion-exclusion principle and permutations with restricted position,Discrete Mathematics,104(1992),7-22.
[8]W.C.Chu and L.C.Hsu,Some new applications of Gould-Hsu inversions,J.Combin.Inform.System Sci.14(1)1-4 1989.
[9]L.Comtet,Andvanced Combinatorics,Reidel,Dordrecht,N-L,1974.
[10]H.Feng,The multiset Mahonian statistics,大连理工大学学报,42(2002),17-20.
[11]H.Feng,Z.Z.Zhang,Computational formulas for convoluted generalized Fibonacci and Lucas numbers,(2003),144-151.
[12]K.C.Garrett and K.Hummel,A combinatorial proof of the sum of q-cubes,Electron.J.Combin.11(2004),R9.
[13]J.R.Goldman and G.-C.Rota,The number of subspaces in a vector space,in "Recent Progress in Combinatorics"(W.Tutte,Ed.),pp.75-83,Academic Press,San Diego,1969.
[14]J.R.Goldman and G.-C.Rota,On the foundations of combinatorial theory Ⅳ,Finite vector spaces and Eulerian generating functions,Stud.Appl.Math.49(1970),239-258.
[15]B.Gordon,Some identities in combinatorial analysis,Quart.J.Math.Oxford Set.(2)12 285-2901961.
[16]H.W.Gould and L.C.Hsu,Some new inverse series relations,Duke Math.J.40 885-891 1973.
[17]I.P.Goulden,A bijective proof of Steniey's shuffling theorem,Trans.Amer.Math.Soc.288(1) 147-160 1985.
[18]D.E.Knuth,Subsets,subspaces,and partitions,J.Combin.Theory 10(1971),178-180.
[19]J.P.S.Kung,The subset-subspace ananlogy,in" Gian-Carlo Rota on Combinatorics"(J.Kung,Ed.),pp.277-283,Birkhauser,Basel,1995.
[20]J.Konvalina,Generalized binomial coefficients and the subset-subspace problem,Adv.in Appl.Math.21(1998),228-240.
[21]P.A.MacMahon,Combinatory Analysis,vol.1 Cambridge University Press,Cambridge 1915.
[22]M.Schlosser,q-Analogues of the sums of consecutive integers,squares,cubes,quurts and quints,??Electron.J.Combin.11(2004),R71. [23]S.C.Milne,Mappings of subspaces into subsets,J.Combin.Theory,Set.A 33(19s2),36-47. [24]R.P.Staaley,Enumerative Combinatorics,Vol.I,Wadsworth and Brooks/Cole,Monterey,CA,1986. [25]J.Riordan,Combinatorial Identities,John Wiley Sons Inc.,New York,1968. [26]J.Riordan,"Aa Introduction to Combinatorial Analysis,"Wiley,New York,1958. [27]G-C.Rota,"On the Foundations of Combinatorial Theory,I",Zeitschrift fur Wahrscheinlich-keitstheorie,Band 2,Heft4.5 340-368.1964.
[28]J.Wang,Quotient sets and subset-subspace analogy,Advances in Applied Mathematics 23(1999),333-339. [29]S.Ole Warnaar,On the q-analogue of the sum of cubes,Electron.J.Combin.11(2004),N13.
[30]G.Zhao,H.Feng,A new q-analogue of the sum of cubes,Discrete Math.307(2007),2861-2865.
[2]G.E.Andrews and D.Bressoud,Identities in combinatorics Ⅲ:Further aspects of ordered set sorting,Discrete Math.49 pp.223 1984.
[3]E.A.Bender,A generalized q-binomial vandermonde convolution,Discrete Math.l(2) 115-1191971.
[4]E.A.Bender and J.R.Goldman,On the applications of MSbius inversion in combinatorial analysis,Amer.Math.Monthly 82(1975),789-803.
[5]A.Benjamin,M.E.Orrison,Two quick combinatorial proofs of Σ=_(k=1)~n k~3=((?))~2,The College Math Journal,33(2002),406-408.
[6]L.Carlitz,Some inverse relations,Duke Math.J.40 893-901 1973.
[7]W.Y.C.Chen and G.C.Rota,q-analogs of the inclusion-exclusion principle and permutations with restricted position,Discrete Mathematics,104(1992),7-22.
[8]W.C.Chu and L.C.Hsu,Some new applications of Gould-Hsu inversions,J.Combin.Inform.System Sci.14(1)1-4 1989.
[9]L.Comtet,Andvanced Combinatorics,Reidel,Dordrecht,N-L,1974.
[10]H.Feng,The multiset Mahonian statistics,大连理工大学学报,42(2002),17-20.
[11]H.Feng,Z.Z.Zhang,Computational formulas for convoluted generalized Fibonacci and Lucas numbers,(2003),144-151.
[12]K.C.Garrett and K.Hummel,A combinatorial proof of the sum of q-cubes,Electron.J.Combin.11(2004),R9.
[13]J.R.Goldman and G.-C.Rota,The number of subspaces in a vector space,in "Recent Progress in Combinatorics"(W.Tutte,Ed.),pp.75-83,Academic Press,San Diego,1969.
[14]J.R.Goldman and G.-C.Rota,On the foundations of combinatorial theory Ⅳ,Finite vector spaces and Eulerian generating functions,Stud.Appl.Math.49(1970),239-258.
[15]B.Gordon,Some identities in combinatorial analysis,Quart.J.Math.Oxford Set.(2)12 285-2901961.
[16]H.W.Gould and L.C.Hsu,Some new inverse series relations,Duke Math.J.40 885-891 1973.
[17]I.P.Goulden,A bijective proof of Steniey's shuffling theorem,Trans.Amer.Math.Soc.288(1) 147-160 1985.
[18]D.E.Knuth,Subsets,subspaces,and partitions,J.Combin.Theory 10(1971),178-180.
[19]J.P.S.Kung,The subset-subspace ananlogy,in" Gian-Carlo Rota on Combinatorics"(J.Kung,Ed.),pp.277-283,Birkhauser,Basel,1995.
[20]J.Konvalina,Generalized binomial coefficients and the subset-subspace problem,Adv.in Appl.Math.21(1998),228-240.
[21]P.A.MacMahon,Combinatory Analysis,vol.1 Cambridge University Press,Cambridge 1915.
[22]M.Schlosser,q-Analogues of the sums of consecutive integers,squares,cubes,quurts and quints,??Electron.J.Combin.11(2004),R71. [23]S.C.Milne,Mappings of subspaces into subsets,J.Combin.Theory,Set.A 33(19s2),36-47. [24]R.P.Staaley,Enumerative Combinatorics,Vol.I,Wadsworth and Brooks/Cole,Monterey,CA,1986. [25]J.Riordan,Combinatorial Identities,John Wiley Sons Inc.,New York,1968. [26]J.Riordan,"Aa Introduction to Combinatorial Analysis,"Wiley,New York,1958. [27]G-C.Rota,"On the Foundations of Combinatorial Theory,I",Zeitschrift fur Wahrscheinlich-keitstheorie,Band 2,Heft4.5 340-368.1964.
[28]J.Wang,Quotient sets and subset-subspace analogy,Advances in Applied Mathematics 23(1999),333-339. [29]S.Ole Warnaar,On the q-analogue of the sum of cubes,Electron.J.Combin.11(2004),N13.
[30]G.Zhao,H.Feng,A new q-analogue of the sum of cubes,Discrete Math.307(2007),2861-2865.