组合计数

You are currently browsing articles tagged 组合计数.

 

题目: 求方程{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: