组合

You are currently browsing the archive for the 组合 category.

我们知道,

\displaystyle 2^n=C_n^0+C_n^1+\cdots+C_n^k+\cdots+C_n^n.

因此,

\displaystyle \begin{array}{rcl} 2^0+2^1+\cdots+2^n&=&C_0^0 \\&+&(C_1^0+C_1^1) \\&+&(C_2^0+C_2^1+C_2^2) \\&+&\cdots \\&+&(C_n^0+C_n^{1}+C_n^{2}+\cdots+C_n^n) \\&=&(C_0^0+C_1^0+C_2^0+\cdots+C_n^0) \\&+&(C_1^1+C_2^1+\cdots+C_n^1) \\&+&(C_2^2+C_3^2+\cdots+C_n^2) \\&+&\cdots \\&+&(C_{n-1}^{n-1}+C_n^{n-1}) \\&+&C_n^n. \end{array}

利用杨辉三角中呈现的组合恒等式

\displaystyle C_{r}^{r}+C_{r+1}^{r}+\cdots+C_n^{r}=C_{n+1}^{r+1},

可将上式进一步化为

\displaystyle C_{n+1}^1+C_{n+1}^2+\cdots+C_{n+1}^n+C_{n+1}^{n+1}=2^{n+1}-1.

因此

\displaystyle 2^0+2^1+\cdots+2^n=2^{n+1}-1.

更加一般地,当{p\neq 1}时,由二项式定理,

\displaystyle p^n=[1+(p-1)]^n=C_n^0(p-1)^{0}+C_n^1(p-1)^1+\cdots+C_n^k(p-1)^k+\cdots+C_n^n(p-1)^{n},

因此,

\displaystyle \begin{array}{rcl} p^0+p^1+\cdots+p^n&=&C_0^0(p-1)^0 \\&+&[C_1^0(p-1)^0+C_1^1(p-1)^1] \\&+&[C_2^0(p-1)^0+C_2^1(p-1)^1+C_2^2(p-2)^2] \\&+&\cdots \\&+&[C_n^0(p-1)^0+C_n^1(p-1)^1+\cdots+C_n^n(p-1)^n] \\&=&(C_0^0+C_1^0+C_2^0+\cdots+C_n^0)(p-1)^0 \\&+&(C_1^1+C_2^1+\cdots+C_n^1)(p-1)^1 \\&+&\cdots\\&+&(C_{n-1}^{n-1}+C_n^{n-1})(p-1)^{n-1} \\&+&C_n^n(p-1)^n \\&=&C_{n+1}^1(p-1)^0+C_{n+1}^2(p-1)^1+\cdots+C_{n+1}^n(p-1)^{n-1}+C_{n+1}^{n+1}(p-1)^n \\&=&[C_{n+1}^1(p-1)^1+C_{n+1}^2(p-1)^2+\cdots+C_{n+1}^n(p-1)^{n}+C_{n+1}^{n+1}(p-1)^{n+1}]/(p-1) \\&=&\frac{[1+(p-1)]^{n+1}-1}{p-1}. \\&=&\frac{p^{n+1}-1}{p-1}. \end{array}

Tags:

受博文x_1+x_2+……+x_r=n的非负整数解的个数的启发,下面我们给出组合数C_n^m的几何意义.

1. m=2的情形

如图1,是一个等腰直角三角形的点阵,其直角边上有{n-1}个点.如果把这个点阵放 在平面直角坐标系中,可以用点集

\displaystyle \{(x,y)|x+y\leq n-2,x,y\in \mathbf{N}\}

来描述.

该点阵第{1}列有{n-1}个点,第{2}列有{n-2}个点,……,第{k}列有{n-k}个 点,……,第{n-1}列有{1}个点,因此该点阵中所有点的数目是

\displaystyle 1+2+\cdots+(n-1)=\frac{n(n-1)}{2}=C_n^2,

恰好是从{n}个不同元素中任意选取{2}个元素的所有选法总数.这是个巧合吗? 不是,可以作如下解释:

{n}个不同的元素是{a_1,a_2,\cdots,a_{n}}.从这{n}个元素任取两个元素,记 这两个元素为{a_i}{a_j},其中{i<j}.则所有取法可分类如下:

  • {i=1}时,{j}可以取{2,\cdots,n},共有{n-1}种取法.这{n-1}种取法对应于 图1中点阵第{1}列的{n-1}个点,即对应于点集{\{(x,y)|x=0,x+y\leq n-2,y\in \mathbf{N}\}}中的{n-1}个点.
  • {i=2}时,{j}可以取{3,\cdots,n},共有{n-2}种取法.这{n-2}种取法对应于 图1中点阵第{2}列的{n-2}个点,即对应于点集{\{(x,y)|x=1,x+y\leq n-2,y\in \mathbf{N}\}}中的{n-2}个点.
  • {\vdots}
  • {i=p}时,{j}可以取{p+1,\cdots,n},共有{n-p}种取法.这{n-p}种取法对应于 图1中点阵第{p}列的{n-p}个点,即对应于点集{\{(x,y)|x=p-1,x+y\leq n-2,y\in \mathbf{N}\}}中的{n-p}个点.
  • {\vdots}
  • {i=n-1}时,{j}只能等于{n},共有{1}种取法.这{1}种取法对应于图1中点阵 第{n-1}列,即最后一列中的{1}个点,即对应于点集{\{(x,y)|x=n-1,x+y\leq n-1,y\in \mathbf{N}\}}中的{1}个点.

由于从{n}个不同元素中任意选取{2}个元素共有{C_n^2}种取法,因此图1中的点 集也必有{C_n^2}个点.

2. m=3的情形

我们再来看图2,是空间中的一个三棱锥点阵.该三棱锥有三条互相垂直的棱,且这 三条互相垂直的棱上都有{n-2}个点.将该三棱锥恰当地放在空间直角坐标系中,可 以用点集{\{(x,y,z)|x+y+z\leq n-3,x,y,z\in \mathbf{N}\}}表示.下面我们来 说明,该点集中点的数目是{C_n^3}.

设有{n}个互不相同的元素{a_1,a_2,\cdots,a_n}.从这{n}个元素中任取{3}个元 素,记这{3}个元素为{a_i,a_j,a_k},且{i<j<k}.则所有取法可分类如下:

  • {i=1}时,只用在{a_{2},\cdots,a_{n}}中选取{a_j}{a_k},共有 {C_{n-1}^{2}}种选法,这和三棱锥点阵从上往下数第{n-2}层的点的数目是一样的,即和点集{\{(x,y,z)|z=0,x+y+z\leq n-3,x,y,z\in \mathbf{N}\}}中点的数目是一样的.
  • {\vdots}
  • {i=p}时,只用在{a_{p+1},\cdots,a_n}中选取{a_j}{a_k},共有 {C_{n-p}^{2}}种选法,这和三棱锥点阵从上往下数第{n-p-1}层的点的数目是 一样的,即和点集{\{(x,y,z)|z=p-1,x+y+z\leq n-3,x,y,z\in \mathbf{N}\}} 中点的数目是一样的.
  • {\vdots}
  • {i=n-2}时,{a_j,a_k}只有一种选法,即{j=n-1,k=n}的选法.这和三棱锥 点阵第从上往下数第{1}层的点的数目是一样的.

由于从{n}个不同元素中任意选取{3}个元素共有{C_n^3}种取法,因此图2种的点 集也必有{C_n^3}个点.

3. 一般情形

下面,我们使用数学归纳法证明,{m}维空间中的点集

\displaystyle \{(x_1,x_2,\cdots,x_m)|x_1+x_2+\cdots+x_m\leq n-m,x_1,x_2,\cdots,x_m\in \mathbf{N}\}

中共有{C_n^m}个点.

{m=1}时,{x_1\leq n-1}显然有{n=C_n^1}个解,它们分别是 {0,1,\cdots,n-1}.可见{m=1}时命题成立.

假设当{m\leq k},其中{k\in \mathbf{N}^{+}},点集{\{(x_{1},x_{2},\cdots,x_{m})|x_1+x_{2}+\cdots+x_m\leq n-m,x_1,x_2,\cdots,x_m\in \mathbf{N}\}}中都有{C_n^m}个点.则当{m=k+1}时,点集{\{(x_{1},\cdots,x_{m},x_{m+1})|x_1+\cdots+x_m+x_{m+1}\leq n-(m+1),x_1,\cdots,x_m,x_{m+1}\in \mathbf{N}\}}有如下情形

  • {x_{m+1}=0}时,由归纳假设, \{(x_1,x_2,\cdots,x_m,0)|x_1+\cdots+x_m\leq (n-1)-m,x_1,\cdots,x_m\in \mathbf{N}\} 中有{C_{n-1}^{m}}个点.
  • {x_{m+1}=1}时,由归纳假 设,\{(x_1,x_2,\cdots,x_m,1)|x_1+\cdots+x_m\leq (n-2)-m,x_1,\cdots,x_{m}\in \mathbf{N}\}中有{C_{n-2}^{m}}个点.
  • {\vdots}
  • {x_{m+1}=p}时,由归纳假 设,\{(x_1,x_2,\cdots,x_m,p)|x_1+\cdots+x_m\leq (n-p)-m,x_1,\cdots,x_m\in \mathbf{N}\}中有{C_{n-(p+1)}^{m}}个点.
  • {\vdots}
  • {x_{m+1}=n-(m+1)}时,由归纳假设 \{(x_1,x_2,\cdots,x_m,n-(m+1))|x_1+\cdots+x_m\leq 0,x_{1},\cdots,x_{m}\in \mathbf{N}\}中有{C_m^m=1}个点.

综上可见,由归纳假设,点集 {\{(x_1,x_2,\cdots,x_m,x_{m+1})|x_1+\cdots+x_{m+1}\leq n-(m+1),x_{1},\cdots,x_{m+1}\in \mathbf{N}\}}中共有

\displaystyle C_m^m+C_{m+1}^m+\cdots+C_{m+k}^m+\cdots+C_{n-1}^m

个点.

然后使用组合方法证明,

\displaystyle C_m^m+C_{m+1}^m+\cdots+C_{m+k}^m+\cdots+C_{n-1}^m=C_{n}^{m+1}.

{n}个互不相同的东西{a_1,a_2,\cdots,a_{n}}中任意选取{m+1}个元素,共有 {C_n^{m+1}}种选法.设选 出的元素为{a_{i_1},a_{i_2},\cdots,a_{i_{m+1}}},且设{i_1<i_2<\cdots<i_{m+1}}.

  • {i_1=1}时,{a_{i_{2}},\cdots,a_{i_{m+1}}}只能在 {a_{2},\cdots,a_{n}}中选,有{C_{n-1}^m}种选法
  • {\vdots}
  • {i_1=k}时,{a_{i_2},\cdots,a_{i_{m+1}}}只能在 {a_{k+1},\cdots,a_n}中选,有{C_{n-k}^{m}}种选法.
  • {\vdots}
  • {i_1=n-m}时,{a_{i_2},\cdots,a_{i_{m+1}}}只能在 {a_{n-m+1},\cdots,a_n}中选,有{C_m^m}种选法.

因此,

\displaystyle C_m^m+C_{m+1}^m+\cdots+C_{m+k}^m+\cdots+C_{n-1}^m=C_n^{m+1}.

可见,点集{\{(x_1,x_2,\cdots,x_m,x_{m+1})|x_1+\cdots+x_{m+1}\leq n-(m+1),x_1,\cdots,x_{m+1}\in \mathbf{N}\}}中共有{C_n^{m+1}}个点.

由数学归纳法,命题得证.

Tags:

 

题目: 求方程{x_1+x_2+\cdots+x_{r}=n}非负整数解的个数,其中{n}{r}都是正整数.

解: 首先我们归纳出{x_1+x_2+\cdots+x_{r}=n}的非负整数解的个数公式.

{r=1}时,{x_1=n}显然只有一个非负整数解.

再解决{r=2}的情形.即探讨{r_{1}+r_{2}=n}非负整数解的个数.此时显然有{n+1} 个非负整数解.

{r=3}时,探讨{r_{1}+r_{2}+r_{3}=n}非负整数解的个数.当{r_{3}=0}时,有 {n+1}个非负整数解,{r_{3}=1}时,有{n}个非负整数解,……,{r_{3}=k}时,有{n-k+1}个非负整数解,……,{r_{3}=n}时,有{1}个非负整数解.因此当{r=3}时,非负整数解的个数是

\displaystyle 1+2+\cdots+(n+1)=\frac{(n+1)(n+2)}{2}.

{r=4}时,探讨{r_1+r_2+r_3+r_4=n}非负整数解的个数.当{r_4=0}时,有 {\frac{(n+1)(n+2)}{2}}个非负整数解.当{r_4=1}时,有{\frac{n(n+1)}{2}}个非负整数解,……,{r_4=k}时,有{\frac{(n-k+1)(n-k+2)}{2}}个非负整数解,……,{r_4=n}时,有 {\frac{1\times 2}{2}}个非负整数解.因此当{r=4}时,非负整数解的个数是

\displaystyle \begin{array}{rcl} \frac{1}{2}\sum_{i=1}^{n+1}i(i+1) &=&\frac{1}{2}\times \frac{1}{3}\sum_{i=1}^{n+1}[i(i+1)(i+2)-(i-1)i(i+1)] \\&=&\frac{1}{6}(n+1)(n+2)(n+3) \end{array}

下面,我们用第二数学归纳法证明,方程{x_1+x_2+\cdots+x_{r}=n}的非负整数解的个 数是

\displaystyle \frac{1}{(r-1)!}(n+1)(n+2)\cdots (n+r-1)=\frac{(n+r-1)!}{n!(r-1)!}=C_{n+r-1}^{n}.

  • {r=1}时,{1=C_{n+1-1}^n},命题成立.
  • 设当{r\leq k(k\in \mathbf{N}^+)}时,{x_1+x_2+\cdots+x_k=n}都有{C_{n+k-1}^{n}}个非负整数解.然后探讨{x_1+x_2+\cdots+x_k+x_{k+1}=n}的非负整数解的个数.当{x_{k+1}=0}时, 有{C_{n+k-1}^{n}}个非负整数解,当{x_{k+1}=1}时,有{C_{n+k-2}^{n-1}}个非负整数解,……, 当{x_{k+1}=p}时,有{C_{(n-p)+(k-1)}^{n-p}}个非负整数解,……,当{x_{k+1}=n}时, 有{C_{(n-n)+(k-1)}^{n-n}=1}个非负整数解.因此{x_1+x_2+\cdots+x_{k+1}=n}的非负整数解的总数是

    \displaystyle \begin{array}{rcl} C_{k-1}^0+C_k^1+C_{k+1}^2+\cdots+C_{k+(n-1)}^n&=&(C_{k-1}^0+C_k^1)+C_{k+1}^2+\cdots+C_{k+(n-1)}^n \\&=&C_{k+1}^1+C_{k+1}^2+C_{k+2}^3+\cdots+C_{k+(n-1)}^n \\&=&(C_{k+1}^1+C_{k+1}^2)+C_{k+2}^3+\cdots+C_{k+(n-1)}^n \\&=&C_{k+2}^2+C_{k+2}^3+\cdots+C_{k+(n-1)}^n \\&\vdots& \\&=&C_{k+(n-2)}^{n-1}+C_{k+(n-1)}^{n} \\&=&C_{n+k}^{n}. \end{array}

    注意在上面的过程中反复运用了组合数的公式

    \displaystyle C_{n+1}^m=C_n^m+C_{n}^{m-1}.

    由数学归纳法,命题对任意正整数r成立.\Box

Tags:

题目 1 求证:{A_n^k+kA_n^{k-1}=A_{n+1}^k}.

解: 除了使用排列数{A_n^{m}}的公式证明之外,这个恒等式其实还有实际的排列意义.

考虑{n+1}个两两不同的数{a_1,a_2,\cdots,a_{n+1}}.从这{n+1}个数中任意选取{k}个数,再把这{k}个数按照一定的次序排成一列,共有{A_{n+1}^k}种方法.

还可以从另外一个角度看待这个问题.从{n+1}个数中选取{k}个数依次排成一列这件事,可以分为两类情况.

  • 第一类:这{k}个数是从{a_1,a_2,\cdots,a_n}中选的,再按顺序排成一列,共有 {A_n^k}种方法.
  • 第二类:这{k}个数中有{a_{n+1}}.从{a_1,a_2,\cdots,a_n}中选取{k-1}个数,排成一列,共 有{A_n^{k-1}}种排法,再把{a_{n+1}}插入该列{k-1}个数,可以把a_{n+1}放在第1个位置,第2个位置,……,第k个位置,共有{k}种插法.因此 由乘法原理第二类共有{kA_n^{k-1}}种方法.

由加法原理,{A_{n+1}^k=A_n^k+kA_n^{k-1}}. \Box

 

题目2:如图,四边形{ABCD}是矩形,图中其它各线或平行于{AB},或平行 于{BC},则图中共有几个矩形?  

我们来探索一般的问题.设图中共有{m}根竖线,其中{AB}是竖线{S_0},一直 到{DC}是竖线{S_{m-1}}.设图中有{n}根横线,其中{BC}是横线{H_{0}},一直 到{AD}是横线{H_{n-1}}.记竖线{S_{i}}和横线{H_{j}}的交点为{(i,j)}.

解法1: 我们来计算右上顶点为{(i,j)}的矩形有多少个.右上顶点为{(i,j)}的矩形,它 的横向宽度有{1,\cdots,i}种选择,纵向长度有{1,\cdots,j}种选择.因此由分 步乘法原理,共有{ij}个矩形以点{(i,j)}为右上顶点.求和

\displaystyle \sum_{0\leq i\leq m-1,0\leq j\leq n-1}ij=\frac{m(m-1)}{2}\frac{n(n-1)}{2}.

即可得所有矩形的数目.在上图中,{m=13,n=7},因此共有{1638}个矩形. \Box

解法2: 每个矩形都被其四个顶点{(i_1,j_1),(i_2,j_1),(i_1,j_2),(i_2,j_2)}所确 定,其中{0\leq i_1,i_{2}\leq m-1,0\leq j_1,j_2\leq n-1}.这里共涉及 {i_1,i_2,j_1,j_2}四个数.其中选出{i_1,i_2}(没有顺序要求)共有 {{m\choose 2}}种方法,选出{j_1,j_2}(没有顺序要求)共有{{n\choose 2}}种 方法.因此确定一个矩形共有

\displaystyle {n\choose 2}{m\choose 2}=\frac{m(m-1)}{2}\frac{n(n-1)}{2}.

种方法. \Box

题目3 (如下解法错在哪儿?) 若将{6}名教师派送到{4}所中学支教,要求每所中学至少分得{1}名教师,至多{2} 名,则不同的派送方案种数为?

:由于每个中学至少要安排一名老师,因此先选出{4}个老师,安排到 {4}所中学,共有{A_6^4}种安排方法.还剩下两名老师选择四个学校,共有{A_4^2} 种选法.因此总共有

\displaystyle A_6^4\times A_4^{2}=4320

种分派方法.

解: 上述解法有重复.举个例子.记{6}名教师为{A,B,C,D,E,F},{4}所学校记为{1,2,3,4}.先从{6}名教师中选择{4}名教师安排到{4}所学校,一种安排方案是

\displaystyle A\rightarrow 1,B\rightarrow 2,C\rightarrow 3,D\rightarrow 4.

还要把{E,F}两个教师安排到四所学校中的两所学校,不妨设{E\rightarrow 3},{F\rightarrow 4}.

这样的方案和如下方案是等同的:

  • 先安排{A\rightarrow 1,B\rightarrow 2,E\rightarrow 3,D\rightarrow 4},再安排 {C\rightarrow 3},{F\rightarrow 4}.
  • 先安排{A\rightarrow 1,B\rightarrow 2},{C\rightarrow 3},{F\rightarrow 4},再安排{E\rightarrow 3},{D\rightarrow 4}.
  • 先安排{A\rightarrow 1,B\rightarrow 2,E\rightarrow 3,F\rightarrow 4},再安排{C\rightarrow 3,D\rightarrow 4}.

上面的四种情况被我们的解答认为是不同的情况,但实际上它们是同一种.因此实 际答案应该是{\frac{1}{4}A_6^4A_4^2=1080}种情况. \Box

题目4 同样是题目3,下面的解法错在哪?

:由于必有两所学校会被分配到两位老师,因此先把{6}位老师进行 分组.先从{6}位老师中任选两位老师,形成一组,有{C_6^2}种选法,再从剩下 的{4}位老师中任选两位老师,形成一组,有{C_4^2}种选法.最后的两位老师各自 形成一组.这样就有{4}组老师.把这{4}组老师分配到{4}所中学,共有{A_4^4}种 分法.由分步乘法原理,共有

\displaystyle C_6^2C_4^2A_4^4=2160

种方案.

解: 还是举例子.记{6}名教师分别是{A,B,C,D,E,F},{4}所学校分别是甲、乙、丙、 丁.先从{6}名教师中取{2}名教师,如果取的是{A,B}.再从剩下的{4}名教师中 取{2}名教师,如果取的是{C,D}.最后剩下两名教师{E,F}各自形成一个团队.这 四个团队在分配给四所学校之前,没有顺序要求.

这就和下面的选法重复:先从{6}名教师中选取{C,D},形成一个团队,再从剩下的 {4}名教师中选取{A,B},形成一个团队,然后{E,F}各自形成一个团队.因此应该把算出来的答案再除以{2},得到{1080}. \Box

题目5 (2014浙江高考){(1+x)^6(1+y)^4}的展开式中,记{x^my^n}项的系数为{f(m,n)},则{f(3,0)+f(2,1)+f(1,2)+f(0,3)=(~~)}

  • A.{45}
  • B.{60}
  • C.{120}
  • D.{210}

 

解法1: {f(m,n)=C_6^mC_4^n},因此

\displaystyle f(3,0)+f(2,1)+f(1,2)+f(0,3)=C_6^3C_4^0+C_6^2C_4^1+C_6^1C_4^2+C_6^0C_4^3=120.

\Box

解法2:{x^3y^0,x^2y^1,x^1y^2,x^0y^3}的系数之和,与{(1+x)^6(1+x)^4=(1+x)^{10}}{x^3}项的系数相同,所以{f(3,0)+f(2,1)+f(1,2)+f(0,3)=C_{10}^3=120}. \Box

注5.1:如上两个证明殊途同归,导致如下等式成立

\displaystyle C_6^3C_4^0+C_6^2C_4^1+C_6^1C_4^2+C_{6}^{0}C_{4}^{3}=C_{10}^3.

更加一般地,有如下恒等式成立:

\displaystyle C_{m+n}^k=C_m^kC_n^0+C_m^{k-1}C_n^1+\cdots+C_m^{k-p}C_{n}^{p}+\cdots+C_m^0C_n^k.

不难理解如上恒等式的组合意义.作为一个特例,当{m=n=k}时,可得

\displaystyle \begin{array}{rcl} C_{2n}^n&=&C_n^nC_n^0+C_n^{n-1}C_n^1+\cdots+C_n^{n-p}C_n^{p}+\cdots+C_n^0C_n^n \\&=&(C_n^0)^2+(C_n^1)^2+\cdots+(C_n^{p})^2+\cdots+(C_n^n)^2. \end{array}

Tags: