论文部分内容阅读
【摘要】 本文通过建构概率模型证明了一些组合恒等式，使组合恒等式的证明直观简洁.
【关键词】 组合恒等式；概率
【中图分类号】 O211 【文献标志码】 A
引 言
近年来，组合恒等式的研究正越来越受到人们的关注，它已成为组合数学中的一个新的分支.1972年H.W.Gould教授[1]在《Combinatorial Identities》一书中收集了550个组合恒等式，而且将证明方法归为9类，这无疑是组合恒等式研究上了不起的工作.众所周知，许多组合恒等式的证明存在一定的困难，有的证明还很繁琐.概率方法有时使得组合恒等式的证明简便且极易掌握.石焕南，范淑香[2]给出了两个组合恒等式的概率证明.黄丹，周学松[3]则得到了四个新的组合恒等式.本文利用概率方法证明了一些组合恒等式，值得一提的是利用随机变量的独立性证明组合恒等式.
1.用古典概型证明组合恒等式
引理 1.1 若{A1，A2，…，An}构成一个完备事件组，即A1，A2，…，An两两互斥，∪ n i=1 Ai=Ω，则∑ n i=1 P（Ai）=1.
定理 1.1 ∑ m k=0 CkmCr kn=Cm rm n.
证明 考虑随机试验：从m件正品和n件次品中随机地取m r件产品，设事件Am-k表示“其中恰有m-k件正品”，k=0，1，…，m.Am，Am-1，…，A0两两互斥，且∪ m k=0 Am-k=Ω，由概率的有限可加性有
1=P（∪ m k=0 Am-k）= ∑ m k=0 Cm-kmCr kn Cm rm n .
又由对称性有Cm-km=Ckm，于是∑ m k=0 CkmCr kn=Cm rm n.
定理 1.2 Cnn m-1=C1mC0n-1 C2mC1n-1 …CnmCm-1n-1.
证明 建构概率模型：把n只没有区别的球放入m（m≤n）个标了号的盒子中.Ak表示事件“从1到m中选取任意的k个盒子，n只球放到k个盒子中，且没有盒子空着”，k=1，2，…，m.由古典概率计算公式得
P（Ak）= CkmCk-1n-1 Cm-1n m-1 = CkmCk-1n-1 Cnn m-1 .
A1，A2，…，Am两两互斥，∪ m i=1 Ai=Ω，则
1=P（Ω）=P（A1∪A2∪…∪Am）=∑ m k=1 P（Ak）=∑ m k=1 CkmCk-1n-1 Cnn m-1 .
从而证得Cnn m-1=C1mC0n-1 C2mC1n-1 …CnmCm-1n-1.
2.用乘法定理证明组合恒等式
引理 2.1 设A1，A2，…An 为n个事件，n≥2，且P（A1A2…An-1）>0，则有
P（A1A2…An）=P（An|A1A2…An-1）P（An-1|A1A2…An-2）…P（A2|A1）P（A1）.
定理 2.1 1=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim ni！（2k-i）！ .
证明 建构摸球模型：设袋中装有m只白球，n只红球，自袋中取k（k≤min{m，n}）只球，若取出1只红球，则计为1只球；若取出1只白球，则相应取出1只红球，白球不计数，只算取出1只球.然后接着再取，直到总共取出k只球为止.Bi表示事件“实际取出i只球”，i=k，k 1，…，2k-1Bk，Bk 1，…，B2k-1两两互斥，∪ 2k-1 i=k Bi=Ω，Aj表示事件“实际第j次取球取得红球”，则第i次取得红球，前面i-1次有k-1次取得红球，其余取得白球.考虑在指定的k-1次取得红球，不妨设前2k-i次取得红球，后面先是取得白球后是取得红球，其概率为
P（A1A2…A2k-iA2k-i 1 A2k-i 2…Ai-1 Ai）=P（Ai|A1A2…Ai-1 ）…P（A2|A1）P（A1）= n（n-1）…（n-k 1）m（m-1）…（m-（i-k） 1） （m n）（m n-1）…（m n-i 1） .
这种指定的方式有Ci-kk种，则有
P（Bi）=Ci-kk n（n-1）…（n-k 1）m（m-1）…（m-（i-k） 1） （m n）（m n-1）…（m n-i 1） = （k！）2Ckn Ci-km Cim ni！（2k-i）！ .故有
1=P（Ω）=P（∪ 2k-1 i=k Bi）=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim ni！（2k-i）！ .
3.用随机变量的独立性证明组合恒等式
定义3.1[4] 负二项分布亦称“帕斯卡（Pascal）分布”，它有如下基本模型：
设p为伯努利试验中每次试验成功的概率，则伯努利试验列中恰好出现n次成功所需试验次数服从参数为n，p的负二项分布
P{Y=k}=Cn-1k-1pn（1-p）k-n，k=n，n 1，n 2，….
记作Y～NB（n，p），其中0 定理3.1 ∑ i-1 m=r Cr-1m-1Cs-1i-m-1=∑ i-1 n=s Cr-1i-n-1Cs-1n-1.
证明 假设X～NB（r，p），Y～NB（s，p），故
【关键词】 组合恒等式；概率
【中图分类号】 O211 【文献标志码】 A
引 言
近年来，组合恒等式的研究正越来越受到人们的关注，它已成为组合数学中的一个新的分支.1972年H.W.Gould教授[1]在《Combinatorial Identities》一书中收集了550个组合恒等式，而且将证明方法归为9类，这无疑是组合恒等式研究上了不起的工作.众所周知，许多组合恒等式的证明存在一定的困难，有的证明还很繁琐.概率方法有时使得组合恒等式的证明简便且极易掌握.石焕南，范淑香[2]给出了两个组合恒等式的概率证明.黄丹，周学松[3]则得到了四个新的组合恒等式.本文利用概率方法证明了一些组合恒等式，值得一提的是利用随机变量的独立性证明组合恒等式.
1.用古典概型证明组合恒等式
引理 1.1 若{A1，A2，…，An}构成一个完备事件组，即A1，A2，…，An两两互斥，∪ n i=1 Ai=Ω，则∑ n i=1 P（Ai）=1.
定理 1.1 ∑ m k=0 CkmCr kn=Cm rm n.
证明 考虑随机试验：从m件正品和n件次品中随机地取m r件产品，设事件Am-k表示“其中恰有m-k件正品”，k=0，1，…，m.Am，Am-1，…，A0两两互斥，且∪ m k=0 Am-k=Ω，由概率的有限可加性有
1=P（∪ m k=0 Am-k）= ∑ m k=0 Cm-kmCr kn Cm rm n .
又由对称性有Cm-km=Ckm，于是∑ m k=0 CkmCr kn=Cm rm n.
定理 1.2 Cnn m-1=C1mC0n-1 C2mC1n-1 …CnmCm-1n-1.
证明 建构概率模型：把n只没有区别的球放入m（m≤n）个标了号的盒子中.Ak表示事件“从1到m中选取任意的k个盒子，n只球放到k个盒子中，且没有盒子空着”，k=1，2，…，m.由古典概率计算公式得
P（Ak）= CkmCk-1n-1 Cm-1n m-1 = CkmCk-1n-1 Cnn m-1 .
A1，A2，…，Am两两互斥，∪ m i=1 Ai=Ω，则
1=P（Ω）=P（A1∪A2∪…∪Am）=∑ m k=1 P（Ak）=∑ m k=1 CkmCk-1n-1 Cnn m-1 .
从而证得Cnn m-1=C1mC0n-1 C2mC1n-1 …CnmCm-1n-1.
2.用乘法定理证明组合恒等式
引理 2.1 设A1，A2，…An 为n个事件，n≥2，且P（A1A2…An-1）>0，则有
P（A1A2…An）=P（An|A1A2…An-1）P（An-1|A1A2…An-2）…P（A2|A1）P（A1）.
定理 2.1 1=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim ni！（2k-i）！ .
证明 建构摸球模型：设袋中装有m只白球，n只红球，自袋中取k（k≤min{m，n}）只球，若取出1只红球，则计为1只球；若取出1只白球，则相应取出1只红球，白球不计数，只算取出1只球.然后接着再取，直到总共取出k只球为止.Bi表示事件“实际取出i只球”，i=k，k 1，…，2k-1Bk，Bk 1，…，B2k-1两两互斥，∪ 2k-1 i=k Bi=Ω，Aj表示事件“实际第j次取球取得红球”，则第i次取得红球，前面i-1次有k-1次取得红球，其余取得白球.考虑在指定的k-1次取得红球，不妨设前2k-i次取得红球，后面先是取得白球后是取得红球，其概率为
P（A1A2…A2k-iA2k-i 1 A2k-i 2…Ai-1 Ai）=P（Ai|A1A2…Ai-1 ）…P（A2|A1）P（A1）= n（n-1）…（n-k 1）m（m-1）…（m-（i-k） 1） （m n）（m n-1）…（m n-i 1） .
这种指定的方式有Ci-kk种，则有
P（Bi）=Ci-kk n（n-1）…（n-k 1）m（m-1）…（m-（i-k） 1） （m n）（m n-1）…（m n-i 1） = （k！）2Ckn Ci-km Cim ni！（2k-i）！ .故有
1=P（Ω）=P（∪ 2k-1 i=k Bi）=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim ni！（2k-i）！ .
3.用随机变量的独立性证明组合恒等式
定义3.1[4] 负二项分布亦称“帕斯卡（Pascal）分布”，它有如下基本模型：
设p为伯努利试验中每次试验成功的概率，则伯努利试验列中恰好出现n次成功所需试验次数服从参数为n，p的负二项分布
P{Y=k}=Cn-1k-1pn（1-p）k-n，k=n，n 1，n 2，….
记作Y～NB（n，p），其中0
证明 假设X～NB（r，p），Y～NB（s，p），故