📄 1_6.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="#FFFFFF"><h1>1.6组合的生成</h1><p>设从[1,n]中取r元的组合全体为C(n,r).C<sub>1</sub>C<sub>2</sub>…C<sub>r</sub>∈C(n,r).<br> 不妨设C<sub>1</sub>＜C<sub>2</sub>＜…＜C<sub>r,</sub>i≤C<sub>i</sub>≤(n－r+i),i=1,2,…,r<br> 令j=max{i|C<sub>i</sub>＜n－r+i}.<br> 则C<sub>1</sub>C<sub>2</sub>…C<sub>r</sub>的下一个组合为C<sub>1</sub>C<sub>2</sub>…C<sub>j-1</sub>(C<sub>j</sub>+1)(C<sub>j</sub>+2)…(C<sub>j</sub>+r－j+1)<br> 这等于给C(n,r)的元素建立了字典序。</p><p><b>[例]</b>用两种方法计算[1,n]的无重不相邻组合C'(n,r)的计数问题</p><p>解法1: 0…010…010…010…010…0 共有n位，其中含有r个1且不可含11。</p><p>①以1结尾：r-1个10与n-1-2(r-1)个0的排列<br> r-1+[n-1-2(r-1)]=n-r <br> 这样的排列有<img src="1_6pic/image002.gif" width="188" height="48" align="middle"> </p><p>②以0结尾：r个10与n-2r个0的排列<br> r+n-2r=n-r这样的排列有<img src="1_6pic/image006.gif" width="51" height="48" align="middle">个, <img src="1_6pic/image004.gif" width="193" height="48" align="middle"><br> 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> </p><p>解法2:任给a<sub>1</sub>a<sub>2</sub>…a<sub>r</sub>∈C'(n,r),a<sub>1</sub>＜a<sub>2</sub>＜…＜a<sub>r</sub> <br> 令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> b<sub>i</sub>=a<sub>i</sub>-i+1,i=1,2,…,r. <br> 1≤b<sub>1</sub>＜b<sub>2</sub>＜…＜b<sub>r</sub>≤n-r+1,b<sub>1</sub>b<sub>2</sub>…b<sub>r</sub>∈C(n-r+1,r)<br> C'(n,r)=C(n-r+1,r)</p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -