恒等式的q-模拟及组合证明
|
摘要
恒等式的组合证明或组合解释赋予了恒等式一定的计数意义,组合证明最常用的方法是分别用两种不同的方法对恒等式的两端进行计数,一般通过构造两个集合之间的双射,这两个集合的个数分别表示恒等式的两端,从而根据双射的一一对应性证明恒等式。本文也正是采用了这种方法对恒等式进行组合证明,从而揭示组合证明的一般方法。
在组合恒等式中,q-恒等式是一类特殊的恒等式,其中一大部分是关于离散变量恒等式的q-模拟,这里q是一个参数,它具有很多的计数意义,因此对q-恒等式的证明受到人们的广泛关注。人们用各种各样的方法进行研究,本文主要采用分拆的方法来给出一些q-恒等式的组合证明。
本文给出了一些重要的二项式系数恒等式的组合证明或组合解释,并从分拆的角度给出了一些q-恒等式的组合证明,其中突出的成果是给出了平方和恒等式的一个直接的组合证明并给出了偶数平方和与奇数平方和的q-模拟及组合证明。
文章主要内容可概括如下:
1.介绍了一些与q-模拟有关的基本知识和基本概念,如:分拆,Ferrers图,偏序集,格,组合证明,二项式系数等。
2.给出了一般布尔格上一些重要的恒等式及其组合证明或组合解释。
3.引入q-模拟的概念,从分拆的角度给出了一些q-恒等式的组合证明。
4.给出了恒等式∑_(k=1)~n(k~2))=1/4((?))的一个直接的组合证明。并从分拆的角度分别给出了恒等式∑_(k=1)~n(2k~2)=((?))和∑_(k=1)~n((2k-1)~2)=((?))的q-模拟及组合证明。
By the combinatorial proof or combinatorial interpretation, the identity is equipped with certain count meaning. The most general way in the combinatorial proof is to count two sides of the identity by two different methods. Generaly, 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 1-1 property of bijection, the identity is proved. This thesis just applies this method to give identities their combinatorial proof. As a result, a general approach to combinatorial proof is illustrated.q-Identity is a certain class identity in combinatorial identity. Most q-identities are q-analogues of indentities with discrete variable, where q is a parameter. q-Analogue of identity has much count meaning. So giving combinatorial proof of q-identity is vary meaningful. In the thesis , we give combinatorial proof of some q-identities using integer partition.In the thesis some vital identities with binomial coefficient are given with their combinatorial proof, and the q-analogues of some identities are offered with corresponding combinatorial proof using integer partition. Especially, one remarkable result is that a new combinatorial proof of the square-sums identity is obtained. We also give combinatorial proof of the sums of even squares, odd squares and their q-analogues using integer partition.The main content of this thesis can be summarized as follows:1. Introduce relevant basic knowledge and concept about integer partition , such as Integer partition, Ferrer graph, Poset, Lattice, Combinatorial Proof, Binomial coefficient and so on.2. Some important identitis are provided with their combinatorial proof or combinatorial interpretation on the Boole Lattice B_n.3. Introduce the concept of q-analogue. q-Analogues of some important identities are given with their combinatorial proof using integer partition.4. We give a new combinatorial proof of the identity 。 We also give combinatorial proof of the sums of even squares, odd squares and their q-analogues using integer partitions.
在组合恒等式中,q-恒等式是一类特殊的恒等式,其中一大部分是关于离散变量恒等式的q-模拟,这里q是一个参数,它具有很多的计数意义,因此对q-恒等式的证明受到人们的广泛关注。人们用各种各样的方法进行研究,本文主要采用分拆的方法来给出一些q-恒等式的组合证明。
本文给出了一些重要的二项式系数恒等式的组合证明或组合解释,并从分拆的角度给出了一些q-恒等式的组合证明,其中突出的成果是给出了平方和恒等式的一个直接的组合证明并给出了偶数平方和与奇数平方和的q-模拟及组合证明。
文章主要内容可概括如下:
1.介绍了一些与q-模拟有关的基本知识和基本概念,如:分拆,Ferrers图,偏序集,格,组合证明,二项式系数等。
2.给出了一般布尔格上一些重要的恒等式及其组合证明或组合解释。
3.引入q-模拟的概念,从分拆的角度给出了一些q-恒等式的组合证明。
4.给出了恒等式∑_(k=1)~n(k~2))=1/4((?))的一个直接的组合证明。并从分拆的角度分别给出了恒等式∑_(k=1)~n(2k~2)=((?))和∑_(k=1)~n((2k-1)~2)=((?))的q-模拟及组合证明。
By the combinatorial proof or combinatorial interpretation, the identity is equipped with certain count meaning. The most general way in the combinatorial proof is to count two sides of the identity by two different methods. Generaly, 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 1-1 property of bijection, the identity is proved. This thesis just applies this method to give identities their combinatorial proof. As a result, a general approach to combinatorial proof is illustrated.q-Identity is a certain class identity in combinatorial identity. Most q-identities are q-analogues of indentities with discrete variable, where q is a parameter. q-Analogue of identity has much count meaning. So giving combinatorial proof of q-identity is vary meaningful. In the thesis , we give combinatorial proof of some q-identities using integer partition.In the thesis some vital identities with binomial coefficient are given with their combinatorial proof, and the q-analogues of some identities are offered with corresponding combinatorial proof using integer partition. Especially, one remarkable result is that a new combinatorial proof of the square-sums identity is obtained. We also give combinatorial proof of the sums of even squares, odd squares and their q-analogues using integer partition.The main content of this thesis can be summarized as follows:1. Introduce relevant basic knowledge and concept about integer partition , such as Integer partition, Ferrer graph, Poset, Lattice, Combinatorial Proof, Binomial coefficient and so on.2. Some important identitis are provided with their combinatorial proof or combinatorial interpretation on the Boole Lattice B_n.3. Introduce the concept of q-analogue. q-Analogues of some important identities are given with their combinatorial proof using integer partition.4. We give a new combinatorial proof of the identity 。 We also give combinatorial proof of the sums of even squares, odd squares and their q-analogues using integer partitions.
引文
[1] I. Anderson. Combinatorics of Finite Sets(Oxford University Press, Oxford, 1989).
[2] G. E. Andrews. The theory of partitions. Cambridge Univ. Press, 1976.
[3] G. E. Andrews. A simple proof of Jacobi's triple product identity, proc. Amer. Math. Soc, 1965, 16(2): 333-334
[4] G. E. Andrews. Sieves in the theory of partitions. Amer. J. Math, 1972, 94: 1214-1230.
[5] G. E. Andrews. Identities in combinatorics. Ⅰ: On sorting two ordered sets. Discrete Math, 1975, 11: 97-106.
[6] G. E. Andrews. Partitions and the Gaussian sum. In: The Mathematical Heritage of C. F. Gauss, G. M. Rassias Ed.. World Scientific Publ. Co.. Singapore, 1991: 35-42.
[7] M. Aigner. Whitney numbers, in "Combinatorial Geometries" (N. White, Ed). Cambridge Univ. Press, Cambridge, UK, 1987: 139-160.
[8] W. N. Bailey. A note on certain q-identities. Quart. J. Math, 1941, 12: 173-175.
[9] E. A. Bender. A generalized q-binomial vandermonde convolution. Discrete Math, 1971, 1(2): 115-119.
[10] E. A. Bender and J. R. Goldman. On the applications of Mobins inversion in combinatorial analysis. Amer. Math. Monthly, 1975, 82: 789-803.
[11] A. Benjamin, M. E. Orrison. Two quick combinatorial proof of ∑_(k=1)~n k~3=(?)~2. The College Math Journal, 2002, 33: 406-408.
[12] L. Carlitz and M. V. Subbarao. A simple proof of the quintuple product identity. Proc. Amer. Math. Soc, 1972, 32(1): 42-44.
[13] L. Carlitz. Some inverse relations. Duke Math, 1973, 40: 893-901.
[14] William. Y. C. Chen and G. C. Rota. q-analogs of the inclusion-exclnsion principle and permutations with restricted position. Discrete Mathematics, 1992, 104: 7-22.
[15] William. Y. C. Chen and Qinghu Hou. An involution for the alternate summation of Gauss coefficients. Electron. J. Combin, 2004.
[16] Wen. C. Chu and L. C. Hsu. Some new applications of Gould-Hsu inversions. J. Combin. Inform. System Sci, 1989, 14(1): 1-4.
[17] L. Comtet. Andvanced Combinatorics. Reidel, Dordrecht, NL, 1974.
[18] Hong Feng. The multiset Mahonian statistics. 大连理工大学学报, 2002, 42: 17-20.
[19] Hong Feng,Guangjun zhao.向量空间上恒等式的q模拟及组合证明,大连理工大学学位论文,2005.
[20] K. C. Garrett and K. Hummel. A combinatorial proof of the sum of q-cubes. Electron. J. Combin, 2004, R9(11).
[21] A. M. Garsia and J. Remmel. A combinatorial interpretation of q-Laguerre numbers. Eur. J. Combin, 1980,1:47-59.
[22] Ira M. Gessel. Finding identities with the WZ mathod. J. Symbolic Comput, 1995,20:537- 566.
[23] J. R. Goldman and G.-C.Rota. The number of subspaces in a vector space. in "Recent Progress in Combinatorics"(W. Tutte, Ed.), San Diego: Academic Press, 1969:75-83.
[24] J. R. Goldman and G.-C. Rota. On the foundations of combinatorial theory IV. Finite vector spaces and Eulerian generating functions, Stud. Appl. Math, 1970,49:239-258.
[25] I. J. Good. Proof of some binomial identities by means of MacMahon's 'Master Theorem'. Proc.Cambridge Philos.Soc, 1962,58:161-162.
[26] B. Gordon. Some identities in combinatorial analysis. Quart. J. Math. Oxford Ser, 1961,12(2):285-290.
[27] H. W. Gould "Combinatorial Identities. A Standardized Set of Tables Listing 500 binomial Coefficient Summations", West Virginia University, 1959.
[28] H. W. Gould and L. C. Hsu. Some new inverse series relations. Duke Math, 1973,40:885- 891.
[29] I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. John Wiley Sons, Inc, 1983.
[30] I. P. Goulden. A bijective proof of Stenley's shuffling theorem. Trans. Amer. Math. Soc, 1985,288(l):147-160.
[31] R. Graham, D. Knuth, and O. Pateshnik, "Concrete Mathematics: A Foundation for Computer Science," Addison-Wesley, Reading, MA, 1989.
[32] M. Haines and S. Shahriari. On the f-vectors of cutset in the Boolean lattice. J. Combin. Theory, Series A, 2001,93(l):177-181.
[33] D. E. Knuth. Subsets, subspaces, and partitions. J. Combin. Theory, 1971,10:178-180.
[34] J. P. S. Kung. The subset-subspace ananlogy, in"Gian-Carlo Rota on Combinatorics"(J. Kung, Ed.), Birkhauser, Basel, 1995:277-283.
[35] C. I. Liu. Introduction to Combinatorial Mathematics. McGram-Hill, New York, 1968.
[36] G. Mackiw. A Combinatorial Approach to Sums of Integer Powers. Mathematics Magazine, 2000,73:44-46.
[37] Michael Schlosser. q-Analogues of the sums of consecutive integers, squares, cubes, quarts and quints, Electron. J. Combin. 11 (2004),R71.
[38] S. C. Milne. Mappings of subspaces into subsets. J. Combin. Theory, Ser. A, 1982,33:36-47.
[39] R. B. Nelson. Proofs Without Words. MAA Washington DC, 1993.
[40] A. Nijenhuis, A. E. Solow and H. S. Wilf. Bijective amthods in theory of finite vector spaces. J. Combin.Theory Ser.A, 1984,37:80-84.
[41] R.Nowakowski. Cutsets of Boolean lattice. Discrete Mathematics, 1987,63:231-240.
[42] Richard P. Stanley. Enumerative Combinatorics. Vol.1, Wadsworth and Brooks/Cole, Mon- terey, CA, 1986.
[43] J. Riordan. Combinatorial Identities. John Wiley Sons Inc., New York, 1968.
[44] G-C. Rota. "On the Foundations of Combinatorial Theory. I", Zeitschrift fur Wahrscheinlich-keits-theorie,Band 2,Heft4.5,1964:340-368.
[45] Jun Wang. Quotient sets and subset-subspace analogy. Advances in Applied Mathematics, 1999, 23: 333-339.
[46] S. Ole Warnaar. On the q-analogue of the sum of cubes. Electron. J. Combin, 2004, 11: N13.
[47] H. S. Wilf. Generating functionology. Acad. press, 1990.(中译本《发生函数论》,清华大学出版社,2003)
[2] G. E. Andrews. The theory of partitions. Cambridge Univ. Press, 1976.
[3] G. E. Andrews. A simple proof of Jacobi's triple product identity, proc. Amer. Math. Soc, 1965, 16(2): 333-334
[4] G. E. Andrews. Sieves in the theory of partitions. Amer. J. Math, 1972, 94: 1214-1230.
[5] G. E. Andrews. Identities in combinatorics. Ⅰ: On sorting two ordered sets. Discrete Math, 1975, 11: 97-106.
[6] G. E. Andrews. Partitions and the Gaussian sum. In: The Mathematical Heritage of C. F. Gauss, G. M. Rassias Ed.. World Scientific Publ. Co.. Singapore, 1991: 35-42.
[7] M. Aigner. Whitney numbers, in "Combinatorial Geometries" (N. White, Ed). Cambridge Univ. Press, Cambridge, UK, 1987: 139-160.
[8] W. N. Bailey. A note on certain q-identities. Quart. J. Math, 1941, 12: 173-175.
[9] E. A. Bender. A generalized q-binomial vandermonde convolution. Discrete Math, 1971, 1(2): 115-119.
[10] E. A. Bender and J. R. Goldman. On the applications of Mobins inversion in combinatorial analysis. Amer. Math. Monthly, 1975, 82: 789-803.
[11] A. Benjamin, M. E. Orrison. Two quick combinatorial proof of ∑_(k=1)~n k~3=(?)~2. The College Math Journal, 2002, 33: 406-408.
[12] L. Carlitz and M. V. Subbarao. A simple proof of the quintuple product identity. Proc. Amer. Math. Soc, 1972, 32(1): 42-44.
[13] L. Carlitz. Some inverse relations. Duke Math, 1973, 40: 893-901.
[14] William. Y. C. Chen and G. C. Rota. q-analogs of the inclusion-exclnsion principle and permutations with restricted position. Discrete Mathematics, 1992, 104: 7-22.
[15] William. Y. C. Chen and Qinghu Hou. An involution for the alternate summation of Gauss coefficients. Electron. J. Combin, 2004.
[16] Wen. C. Chu and L. C. Hsu. Some new applications of Gould-Hsu inversions. J. Combin. Inform. System Sci, 1989, 14(1): 1-4.
[17] L. Comtet. Andvanced Combinatorics. Reidel, Dordrecht, NL, 1974.
[18] Hong Feng. The multiset Mahonian statistics. 大连理工大学学报, 2002, 42: 17-20.
[19] Hong Feng,Guangjun zhao.向量空间上恒等式的q模拟及组合证明,大连理工大学学位论文,2005.
[20] K. C. Garrett and K. Hummel. A combinatorial proof of the sum of q-cubes. Electron. J. Combin, 2004, R9(11).
[21] A. M. Garsia and J. Remmel. A combinatorial interpretation of q-Laguerre numbers. Eur. J. Combin, 1980,1:47-59.
[22] Ira M. Gessel. Finding identities with the WZ mathod. J. Symbolic Comput, 1995,20:537- 566.
[23] J. R. Goldman and G.-C.Rota. The number of subspaces in a vector space. in "Recent Progress in Combinatorics"(W. Tutte, Ed.), San Diego: Academic Press, 1969:75-83.
[24] J. R. Goldman and G.-C. Rota. On the foundations of combinatorial theory IV. Finite vector spaces and Eulerian generating functions, Stud. Appl. Math, 1970,49:239-258.
[25] I. J. Good. Proof of some binomial identities by means of MacMahon's 'Master Theorem'. Proc.Cambridge Philos.Soc, 1962,58:161-162.
[26] B. Gordon. Some identities in combinatorial analysis. Quart. J. Math. Oxford Ser, 1961,12(2):285-290.
[27] H. W. Gould "Combinatorial Identities. A Standardized Set of Tables Listing 500 binomial Coefficient Summations", West Virginia University, 1959.
[28] H. W. Gould and L. C. Hsu. Some new inverse series relations. Duke Math, 1973,40:885- 891.
[29] I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. John Wiley Sons, Inc, 1983.
[30] I. P. Goulden. A bijective proof of Stenley's shuffling theorem. Trans. Amer. Math. Soc, 1985,288(l):147-160.
[31] R. Graham, D. Knuth, and O. Pateshnik, "Concrete Mathematics: A Foundation for Computer Science," Addison-Wesley, Reading, MA, 1989.
[32] M. Haines and S. Shahriari. On the f-vectors of cutset in the Boolean lattice. J. Combin. Theory, Series A, 2001,93(l):177-181.
[33] D. E. Knuth. Subsets, subspaces, and partitions. J. Combin. Theory, 1971,10:178-180.
[34] J. P. S. Kung. The subset-subspace ananlogy, in"Gian-Carlo Rota on Combinatorics"(J. Kung, Ed.), Birkhauser, Basel, 1995:277-283.
[35] C. I. Liu. Introduction to Combinatorial Mathematics. McGram-Hill, New York, 1968.
[36] G. Mackiw. A Combinatorial Approach to Sums of Integer Powers. Mathematics Magazine, 2000,73:44-46.
[37] Michael Schlosser. q-Analogues of the sums of consecutive integers, squares, cubes, quarts and quints, Electron. J. Combin. 11 (2004),R71.
[38] S. C. Milne. Mappings of subspaces into subsets. J. Combin. Theory, Ser. A, 1982,33:36-47.
[39] R. B. Nelson. Proofs Without Words. MAA Washington DC, 1993.
[40] A. Nijenhuis, A. E. Solow and H. S. Wilf. Bijective amthods in theory of finite vector spaces. J. Combin.Theory Ser.A, 1984,37:80-84.
[41] R.Nowakowski. Cutsets of Boolean lattice. Discrete Mathematics, 1987,63:231-240.
[42] Richard P. Stanley. Enumerative Combinatorics. Vol.1, Wadsworth and Brooks/Cole, Mon- terey, CA, 1986.
[43] J. Riordan. Combinatorial Identities. John Wiley Sons Inc., New York, 1968.
[44] G-C. Rota. "On the Foundations of Combinatorial Theory. I", Zeitschrift fur Wahrscheinlich-keits-theorie,Band 2,Heft4.5,1964:340-368.
[45] Jun Wang. Quotient sets and subset-subspace analogy. Advances in Applied Mathematics, 1999, 23: 333-339.
[46] S. Ole Warnaar. On the q-analogue of the sum of cubes. Electron. J. Combin, 2004, 11: N13.
[47] H. S. Wilf. Generating functionology. Acad. press, 1990.(中译本《发生函数论》,清华大学出版社,2003)