📄 1_7.htm
字号:
<html><head><title>Untitled Document</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><body bgcolor="#FeFeFe"><h1>1.7可重组合</h1><p>C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。<br> <object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=4,0,2,0" width="470" height="50"> <param name=movie value="1_7pic/1_7.swf"> <param name=quality value=high> <embed src="1_7pic/1_7.swf" quality=high pluginspage="http://www.macromedia.com/shockwave/download/index.cgi?P1_Prod_Version=ShockwaveFlash" type="application/x-shockwave-flash" width="470" height="50"> </embed> </object><br> 上图为r个相同的球,n-1个相同的盒壁<br> 易知所求计数为<img src="1_7pic/image008.gif" width="156" height="48" align="middle"><br> 即<span class=overline>C</span>(n,r)=C(n+r-1,r)=<span class=overline>C</span>(n-1,r)+<span class=overline>C</span>(n,r-1)<br> 不含"1" 至少含一个"1"</p><p>另证:设a<sub>1</sub>a<sub>2</sub>…a<sub>r</sub>∈<span class=overline>C</span>(n,r),1≤a<sub>1</sub>≤a<sub>2</sub>≤…≤a<sub>r</sub>≤n,<br> 令<span class=overline>C</span>(n,r)上的f，使得b<sub>i</sub>=a<sub>i</sub>+i-1,i=1,2,…,r.<br> 则b<sub>1</sub>b<sub>2</sub>…b<sub>r</sub>满足1≤b<sub>1</sub>＜b<sub>2</sub>＜…＜b<sub>r</sub>≤n+r-1<br> b<sub>1</sub>b<sub>2</sub>…b<sub>r</sub>∈C(n+r-1,r),f：a<sub>1</sub>a<sub>2</sub>…a<sub>r</sub>→b<sub>1</sub>b<sub>2</sub>…b<sub>r</sub><br> 显然f是单射，f<sup>-1</sup>:b<sub>1</sub>b<sub>2</sub>…b<sub>r</sub>→a<sub>1</sub>a<sub>2</sub>…a<sub>r</sub><br> a<sub>i</sub>=b<sub>i</sub>-i+1,i=1,2,…,r.<br> a<sub>1</sub>a<sub>2</sub>…a<sub>r</sub>∈<span class=overline>C</span>(n,r)<br> f是单射 <span class=overline>C</span>(n,r)≤C(n+r-1,r)<br> f<sup>-1</sup>是单射 <span class=overline>C</span>(n,r)≥C(n+r-1,r)<br> ∴C(n,r)=C(n+r-1,r)<br> 第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。 </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -