下载文档原格式
第一章答案 第二章答案 第三章答案 第四章答案第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 48→49~50, 49→50 ) 2．(a) 5!8! (b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)! (c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 因首数字可分别为偶数或奇数，知结果为 2⨯5⨯P(8,2)+3⨯4⨯P(8,2).6. (n+1)!-17. 用数学归纳法易证。
8. 两数的公共部分为240530, 故全部公因数均形如2m 5n ,个数为41⨯31. 9. 设有素数因子分解 n=p 1n 11p 2 n 22…p k n k k , 则n 2的除数个数为( 2n 1+1) (2n 2+1) …(2n k +1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。
11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。
组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。
12．考虑,)1(,)1(1010-=-=+=+=∑∑n nk k k n nnk kk nx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk k n n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。
第三章 递推关系§3.1 基本概念（一） 递推关系【定义3.1.1】（隐式）对数列{}0≥i a i 和任意自然数n ，一个关系到n a 和某些个i a （i ＜n ）的方程式，称为递推关系，记作()0,,,10=n a a a F例 022022212=-------n a a a a n n n 01223121=-------a a a a n n n 【定义3.1. 1'】（显式） 对数列{}0≥i a i ，把n a 与其之前若干项联系起来的等式对所有n ≥k 均成立（k 为某个给定的自然数），称该等式为{}i a 的递推关系，记为()k n n n n a a a F a ---=,,,21 （3.1.1）＇例 1223121++++=--a a a a n n n（二） 分类（1）按常量部分：① 齐次递推关系：指常量＝0，如21--+=n n n F F F ； ② 非齐次递推关系，即常量≠0，如121=--n n h h 。
（2）按i a 的运算关系：① 线性关系，F 是关于i a 的线性函数，如（1）中的nF 与n h 均是如此；② 非线性关系，F 是i a 的非线性函数，如112211h h h h h h h n n n n ---+++= 。
（3）按i a 的系数：① 常系数递推关系，如（1）中的n F 与n h ；② 变系数递推关系，如1-=n n np p ，1-n p 之前的系数是随着n 而变的。
（4） 按数列的多少：① 一元递推关系，其中的方程只涉及一个数列，如（3.1.1）和（3.1.1）＇均为一元的；② 多元递推关系，方程中涉及多个数列，如⎩⎨⎧+=+=----111177n n n n n n a b b b a a （5）显式与隐式：⎥⎦⎤⎢⎣⎡-+=++++11112n n n n n y x y h y y （三） 定解问题 【定义3.1.2】（定解问题）称含有初始条件的递推关系为定解问题，其一般形式为()⎩⎨⎧====--11110010,,,,0,,,k k n d a d a d a a a a F （3.1.2）解递推关系：求n a 的与a 0、a 1、…、a n －1无关的解析表达式或数列{}n a 的母函数。
3.1题（宗传玉）某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议解:设A i为甲与第i个朋友相遇的会议集，i＝1，…，6．则故甲参加的会议数为:28+5=33.3.2题（宗传玉）求从1到500的整数中被3和5整除但不被7整除的数的个数.解:设A3：被3整除的数的集合A5：被5整除的数的集合A7：被7整除的数的集合所以3.3.题（宗传玉）n个代表参加会议，试证其中至少有2人各自的朋友数相等。
解:每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种可能．，所以至少有２人的朋友数相等．3.4题（宗传玉）试给出下列等式的组合意义.解:(a) 从n 个元素中取k 个元素的组合，总含有指定的m 个元素的组合数为)()(kn mn m k m n --=--。
设这m 个元素为a 1,a 2,…,a m ,Ai 为不含a i 的组合（子集），i=1,…,m.()∑∑∑==∈⊄==⎪⎪⎭⎫⎝⎛-⎪⎪⎭⎫ ⎝⎛-=-+⎪⎪⎭⎫ ⎝⎛==⎪⎪⎭⎫⎝⎛--⎪⎪⎭⎫⎝⎛-=ml l m l l m i i lj i lk l n k m A k n k n m n k l n l j 01),(),...,(1m1i i i i i 1)1(A A A A 111213.5题（宗传玉）设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．试证存在整数i 和j，1≤i≤j≤7，使得下列之一必定成立：a i=a j=b i=b j，a i=a j=c i=c j，b i=b j=c i=c j．证：显然，每列中必有两数字相同，共有种模式，有０或１两种选择．故共有·2种选择．·2=6．现有7列，．即必有２列在相同的两行选择相同的数字，即有一矩形，四角的数字相等．3.6题（宗传玉）在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于证：把１×１正方形分成四个(1/2)×.则这５点中必有两点落在同一个小正方形内．而小正方形内的任两点的距离都小于．3.7题（王星）在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．证：把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．3.8题（王星）任取11个整数，求证其中至少有两个数它们的差是10的倍数。
Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul TerwilligerSelected solutions for Chapter31.For1≤k≤22we show that there exists a succession of consecutive days during which the grandmaster plays exactly k games.For1≤i≤77let b i denote the number of gamesplayed on day i.Consider the numbers{b1+b2+···+b i+k}76i=0∪{b1+b2+···+b j}77j=1.There are154numbers in the list,all among1,2,...,153.Therefore the numbers{b1+b2+···+b i+k}76i=0∪{b1+b2+···+b j}77j=1.are not distinct.Therefore there exist integers i,j(0≤i<j≤77)such that b i+1+···+b j=k.During the days i+1,...,j the grandmaster plays exactly k games.2.Let S denote a set of100integers chosen from1,2,...,200such that i does not divide j for all distinct i,j∈S.We show that i∈S for1≤i≤15.Certainly1∈S since 1divides every integer.By construction the odd parts of the elements in S are mutually distinct and at most199.There are100numbers in the list1,3,5,...,199.Therefore each of 1,3,5,...,199is the odd part of an element of S.We have3×5×13=195∈S.Therefore none of3,5,13,15are in S.We have33×7=189∈S.Therefore neither of7,9is in S.We have11×17=187∈S.Therefore11∈S.We have shown that none of1,3,5,7,9,11,13,15 is in S.We show neither of6,14is in S.Recall33×7=189∈S.Therefore32×7=63∈S. Therefore2×32×7=126∈S.Therefore2×3=6∈S and2×7=14∈S.We show10∈S. Recall3×5×13=195∈S.Therefore5×13=65∈S.Therefore2×5×13=130∈S. Therefore2×5=10∈S.We now show that none of2,4,8,12are in S.Below we list the integers of the form2r3s that are at most200:1,2,4,8,16,32,64,128,3,6,12,24,48,96,192,9,18,36,72,144,27,54,108,81,162.In the above array each element divides everything that lies to the southeast.Also,each row contains exactly one element of S.For1≤i≤5let r i denote the element of row i that is contained in S,and let c i denote the number of the column that contains r i.We must have c i<c i−1for2≤i≤5.Therefore c i≥6−i for1≤i≤5.In particular c1≥5so r1≥16,and c2≥4so r2≥24.We have shown that none of2,4,8,12is in S.By the above comments i∈S for1≤i≤15.3.See the course notes.4,5,6.Given integers n≥1and k≥2suppose that n+1distinct elements are chosen from{1,2,...,kn}.We show that there exist two that differ by less than k.Partition{1,2,...,nk}=∪ni=1S i where S i={ki,ki−1,ki−2,...,ki−k+1}.Among our n+1chosen elements,there exist two in the same S i.These two differ by less than k.17.Partition the set{0,1,...,99}=∪50i=0S i where S0={0},S i={i,100−i}for1≤i≤49,S50={50}.For each of the given52integers,divide by100and consider the remainder. The remainder is contained in S i for a unique i.By the pigeonhole principle,there exist two of the52integers for which these remainders lie in the same S i.For these two integers the sum or difference is divisible by100.8.For positive integers m,n we consider the rational number m/n.For0≤i≤n divide the integer10i m by n,and call the remainder r i.By construction0≤r i≤n−1.By the pigeonhole principle there exist integers i,j(0≤i<j≤n)such that r i=r j.The integer n divides10j m−10i m.For notational convenience define =j−i.Then there exists a positive integer q such that nq=10i(10 −1)m.Divide q by10 −1and call the remainder r. So0≤r≤10 −2.By construction there exists an integer b≥0such that q=(10 −1)b+r. Writingθ=m/n we have10iθ=b+r 10 −1=b+r10+r102+r103+···Since the integer r is in the range0≤r≤10 −2this yields a repeating decimal expansion forθ.9.Consider the set of10people.The number of subsets is210=1024.For each subset consider the sum of the ages of its members.This sum is among0,1,...,600.By the pigeonhole principle the1024sums are not distinct.The result follows.Now suppose we consider at set of9people.Then the number of subsets is29=512<600.Therefore we cannot invoke the pigeonhole principle.10.For1≤i≤49let b i denote the number of hours the child watches TV on day i.Consider the numbers{b1+b2+···+b i+20}48i=0∪{b1+b2+···+b j}49j=1.There are98numbers in the list,all among1,2,...,96.By the pigeonhole principle the numbers{b1+b2+···+b i+20}48i=0∪{b1+b2+···+b j}49j=1.are not distinct.Therefore there existintegers i,j(0≤i<j≤49)such that b i+1+···+b j=20.During the days i+1,...,j the child watches TV for exactly20hours.11.For1≤i≤37let b i denote the number of hours the student studies on day i.Considerthe numbers{b1+b2+···+b i+13}36i=0∪{b1+b2+···+b j}37j=1.There are74numbers in the list,all among1,2,...,72.By the pigeonhole principle the numbers{b1+b2+···+b i+13}36i=0∪{b1+b2+···+b j}37j=1are not distinct.Therefore there exist integers i,j(0≤i<j≤37)such that b i+1+···+b j=13.During the days i+1,...,j the student will have studied exactly13hours.12.Take m=4and n=6.Pick a among0,1,2,3and b among0,1,2,3,4,5such that a+b is odd.Suppose that there exists a positive integer x that yields a remainder of a(resp.b) when divided by4(resp.by6).Then there exist integers r,s such that x=4r+a and x=6s+bining these equations we obtain2x−4r−6s=a+b.In this equation the2left-hand side is even and the right-hand side is odd,for a contradiction.Therefore x does not exist.13.Since r (3,3)=6there exists a K 3subgraph of K 6that is red or blue.We assume that this K 3subgraph is unique,and get a contradiction.Without loss we may assume that the above K 3subgraph is red.Let x denote one of the vertices of this K 3subgraph,and let {x i }5i =1denote the remaining five vertices of K 6.Consider the K 5subgraph with vertices{x i }5i =1.By assumption this subgraph has no K 3subgraph that is red or blue.The only edge coloring of K 5with this feature is shown in figure 3.2of the text.Therefore we may assume that the vertices {x i }5i =1are labelled such that for distinct i,j (1≤i,j ≤5)the edge connecting x i ,x j is red (resp.blue)if i −j =±1modulo 5(resp.i −j =±2modulo5).By construction and without loss of generality,we may assume that each of x 1,x 2is connected to x by a red edge.Thus the vertices x,x 1,x 2give a red K 3subgraph.Now the edge connecting x and x 3is blue;otherwise the vertices x,x 2,x 3give a second red K 3subgraph.Similarly the edge connecting x and x 5is blue;otherwise the vertices x,x 1,x 5give a second red K 3subgraph.Now the vertices x,x 3,x 5give a blue K 3subgraph.14.After n minutes we have removed n pieces of fruit from the bag.Suppose that among the removed fruit there are at most 11pieces for each of the four kinds.Then our total n must be at most 4×11=44.After n =45minutes we will have picked at least a dozen pieces of fruit of the same kind.15.For 1≤i ≤n +1divide a i by n and call the reminder r i .By construction 0≤r i ≤n −1.By the pigeonhole principle there exist distinct integers i,j among 1,2,...,n +1such that r i =r j .Now n divides a i −a j .bel the people 1,2,...,n .For 1≤i ≤n let a i denote the number of people aquainted with person i .By construction 0≤a i ≤n −1.Suppose the numbers {a i }n i =1are mutually distinct.Then for 0≤j ≤n −1there exists a unique integer i (1≤i ≤n )such that a i =j .Taking j =0and j =n −1,we see that there exists a person aquainted with nobody else,and a person aquainted with everybody else.These people are distinct since n ≥2.These two people know each other and do not know each other,for a contradiction.Therefore the numbers {a i }n i =1are not mutually distinct.17.We assume that the conclusion is false and get a bel the people 1,2,...,100.For 1≤i ≤100let a i denote the number of people aquainted with person i .By construction 0≤a i ≤99.By assumption a i is even.Therefore a i is among 0,2,4,...,98.In this list there are 50numbers.Now by our initial assumption,for each even integer j (0≤j ≤98)there exists a unique pair of integers (r,s )(1≤r <s ≤100)such that a r =j and a s =j .Taking j =0and j =98,we see that there exist two people who know nobody else,and two people who know everybody else except one.This is a contradiction.18.Divide the 2×2square into four 1×1squares.By the pigeonhole principle there exists a 1×1square that contains at least two of the five points.For these two points the distance apart is at most √2.319.Divide the equilateral triangle into a grid,with each piece an equilateral triangle of side length1/n.In this grid there are1+3+5+···+2n−1=n2pieces.Suppose we place m n=n2+1points within the equilateral triangle.Then by the pigeonhole principle there exists a piece that contains two or more points.For these two points the distance apart is at most1/n.20.Color the edges of K17red or blue or green.We show that there exists a K3subgraph of K17that is red or blue or green.Pick a vertex x of K17.In K17there are16edges that contain x.By the pigeonhole principle,at least6of these are the same color(let us say red).Pick distinct vertices{x i}6i=1of K17that are connected to x via a red edge.Consider theK6subgraph with vertices{x i}6i=1.If this K6subgraph contains a red edge,then the twovertices involved together with x form the vertex set of a red K3subgraph.On the other hand,if the K6subgraph does not contain a red edge,then since r(3,3)=6,it contains a K3subgraph that is blue or green.We have shown that K17has a K3subgraph that is red or blue or green.21.Let X denote the set of sequences(a1,a2,a3,a4,a5)such that a i∈{1,−1}for1≤i≤5 and a1a2a3a4a5=1.Note that|X|=16.Consider the complete graph K16with vertex set X.We display an edge coloring of K16with colors red,blue,green such that no K3 subgraph is red or blue or green.For distinct x,y in X consider the edge connecting x and y.Color this edge red(resp.blue)(resp.green)whenever the sequences x,y differ in exactly 4coordinates(resp.differ in exactly2coordinates i,j with i−j=±1modulo5)(resp. differ in exactly2coordinates i,j with i−j=±2modulo5).Each edge of K16is now colored red or blue or green.For this edge coloring of K16there is no K3subgraph that is red or blue or green.22.For an integer k≥2abbreviate r k=r(3,3,...,3)(k3’s).We show that r k+1≤(k+1)(r k−1)+2.Define n=r k and m=(k+1)(n−1)+2.Color the edges of K m with k+1colors C1,C2,...,C k+1.We show that there exists a K3subgraph with all edges the same color.Pick a vertex x of K m.In K m there are m−1edges that contain x.By the pigeonhole principle,at least n of these are the same color(which we may assume is C1).Pick distinct vertices{x i}ni=1of K m that are connected to x by an edge colored C1.Considerthe K n subgraph with vertices{x i}ni=1.If this K n subgraph contains an edge colored C1,then the two vertices involved together with x give a K3subgraph that is colored C1.On the other hand,if the K n subgraph does not contain an edge colored C1,then since r k=n, it contains a K3subgraph that is colored C i for some i(2≤i≤k+1).In all cases K m hasa K3subgraph that is colored C i for some i(1≤i≤k+1).Therefore r k≤m.23.We proved earlier thatr(m,n)≤m+n−2n−1.Applying this result with m=3and n=4we obtain r(3,4)≤10.24.We show that r t(t,t,q3)=q3.By construction r t(t,t,q3)≥q3.To show the reverse inequality,consider the complete graph with q3vertices.Let X denote the vertex set of this4graph.Color the t -element subsets of X red or blue or green.Then either (i)there exists a t -element subset of X that is red,or (ii)there exists a t -element subset of X that is blue,or (iii)every t -element subset of X is green.Therefore r t (t,t,q 3)≤q 3so r t (t,t,q 3)=q 3.25.Abbreviate N =r t (m,m,...,m )(k m ’s).We show r t (q 1,q 2,...,q k )≤N .Consider the complete graph K N with vertex set X .Color each t -element subset of X with k colors C 1,C 2,...,C k .By definition there exists a K m subgraph all of whose t -element subsets are colored C i for some i (1≤i ≤k ).Since q i ≤m there exists a subgraph of that K m with q i vertices.For this subgraph every t -element subset is colored C i .26.In the m ×n array assume the rows (resp.columns)are indexed in increasing order from front to back (resp.left to right).Consider two adjacent columns j −1and j .A person in column j −1and a person in column j are called matched if they occupy the same row of the original formation.Thus a person in column j is taller than their match in column j −1.Now consider the adjusted formation.Let L and R denote adjacent people in some row i ,with L in column j −1and R in column j .We show that R is taller than L.We assume that L is at least as tall as R,and get a contradiction.In column j −1,the people in rows i,i +1,...,m are at least as tall as L.In column j ,the people in rows 1,2,...,i are at most as tall as R.Therefore everyone in rows i,i +1,...,m of column j −1is at least as tall as anyone in rows 1,2,...,i of column j .Now for the people in rows 1,2,...,i of column j their match stands among rows 1,2,...,i −1of column j −1.This contradicts the pigeonhole principle,so L is shorter than R.27.Let s 1,s 2,...,s k denote the subsets in the collection.By assumption these subsets are mutually distinct.Consider their complements s 1,s 2,...,s k .These complements are mutu-ally distinct.Also,none of these complements are in the collection.Therefore s 1,s 2,...,s k ,s 1,s 2,...,s k are mutually distinct.Therefore 2k ≤2n so k ≤2n −1.There are at most 2n −1subsets in the collection.28.The answer is 1620.Note that 1620=81×20.First assume that 100i =1a i <1620.We show that no matter how the dance lists are selected,there exists a group of 20men that cannot be paired with the 20women.Let the dance lists be bel the women 1,2,...,20.For 1≤j ≤20let b j denote the number of men among the 100that listed woman j .Note that 20j =1b j = 100i =1a i so ( 20j =1b j )/20<81.By the pigeonhole principle there exists an integer j (1≤j ≤20)such that b j ≤80.We have 100−b j ≥20.Therefore there exist at least 20men that did not list woman j .This group of 20men cannot be paired with the 20women.Consider the following selection of dance lists.For 1≤i ≤20man i lists woman i and no one else.For 21≤i ≤100man i lists all 20women.Thus a i =1for 1≤i ≤20and a i =20for 21≤i ≤100.Note that 100i =1a i =20+80×20=1620.Note also that every group of 20men can be paired with the 20women.29.Without loss we may assume |B 1|≤|B 2|≤···≤|B n |and |B ∗1|≤|B ∗2|≤···≤|B ∗n +1|.By assumption |B ∗1|is positive.Let N denote the total number of objects.Thus N = n i =1|B i |and N = n +1i =1|B ∗i |.For 0≤i ≤n define∆i =|B ∗1|+|B ∗2|+···+|B ∗i +1|−|B 1|−|B 2|−···−|B i |.5We have∆0=|B∗1|>0and∆n=N−N=0.Therefore there exists an integer r(1≤r≤n)such that∆r−1>0and∆r≤0.Now0<∆r−1−∆r=|B r|−|B∗r+1|so|B∗r+1|<|B r|.So far we have|B∗1|≤|B∗2|≤···≤|B∗r+1|<|B r|≤|B r+1|≤···≤|B n|.Thus|B∗i|<|B j|for1≤i≤r+1and r≤j≤n.Defineθ=|(B∗1∪B∗2∪···∪B∗r+1)∩(B r∪B r+1∪···∪B n)|.We showθ≥ing∆r−1>0we have|B∗1|+|B∗2|+···+|B∗r|>|B1|+|B2|+···+|B r−1|=|B1∪B2∪···∪B r−1|≥|(B1∪B2∪···∪B r−1)∩(B∗1∪B∗2∪···∪B∗r+1)|=|B∗1∪B∗2∪···∪B∗r+1|−θ=|B∗1|+|B∗2|+···+|B∗r+1|−θ≥|B∗1|+|B∗2|+···+|B∗r|+1−θ.Thereforeθ>1soθ≥2.6。
第三章递推关系1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系.解： f(n)=f(n-1)+2f(1)=2,f(2)=4解得f(n)=2n.2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求f(n)满足的递推关系.解：设a n-1a n-2…a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。
a n可以有两种情况：1）不管上述序列中是否有2，因为a n的位置在最左边，因此0和1均可选；2）当上述序列中没有1时，2可选；故满足条件的序列数为f(n)=2f(n-1)+2n-1 n 1,f(1)=3解得f(n)=2n-1(2+n).3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足的递推关系.解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。
则有h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1）f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的h(n)=(2n+4n)/2代入（2），可得f(n+1)= (2n+4n)/2-2f(n),f(1)=2.4.求满足相邻位不同为0的n位二进制序列中0的个数f(n).解：这种序列有两种情况：1)最后一位为0，这种情况有f(n-3)个；2)最后一位为1，这种情况有2f(n-2)个；所以f(n)=f(n-3)+2f(n-2)f(1)=2,f(2)=3,f(3)=5.5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n).解：最后两位是“00”的序列共有2n-2个。
f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能；f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能；依此类推，有f(n)+f(n-1)+f(n-2)+…+f(2)=2n-2f(2)=1,f(3)=1,f(4)=2.6.求n 位0,1序列中“010”只出现一次且在第n 位出现的序列数f(n).解：最后三位是“010”的序列共有2n-3个。
2020-2021学年新教材数学人教B版选择性必修第二册教案：第3章3.1 3.1.3 第2课时组合数的性质及应用含解析第2课时组合数的性质及应用学习目标核心素养1。
学会运用组合的概念，分析简单的实际问题．（重点）2.能解决无限制条件的组合问题．(难点)通过组合解决实际问题，提升逻辑推理和数学运算的素养.某国际会议中心有A、B、C、D和E共5种不同功能的会议室，且每种功能的会议室又有大、中、小和特小4种型号，总共20个会议室．现在有一个国际学术会议需要选择3种不同功能的6个会议室，并且每种功能的会议室选2个型号．问题：会议中心的工作人员安排会议的方法有多少种？组合数的性质（1）C错误!＝错误!；（2)C m＋1n＋C错误!＝C错误!.1．思考辨析（正确的打“√”，错误的打“×"）(1）C错误!＋C错误!＝C错误!（m≥2且m∈N＊）．()（2)从4名男生3名女生中任选2人，至少有1名女生的选法共有C错误!C错误!种．()（3)把4本书分成3堆，每堆至少一本共有C错误!种不同分法．（)［答案］（1）×（2）×（3)√2．若C错误!＝C错误!，则x的值为（）A．2B．4C．0 D．2或4D［由C错误!＝C错误!可知x＝2或x＝6－2＝4。
故选D。
]3．C错误!＋C错误!的值为________．84［C错误!＋C错误!＝C错误!＝错误!＝错误!＝84.]4．甲、乙、丙三位同学选修课程，从4门课程中,甲选修2门，乙、丙各选修3门，则不同的选修方案共有________种．96[甲选修2门,有C错误!＝6（种）不同方案．乙选修3门，有C错误!＝4(种)不同选修方案．丙选修3门，有C错误!＝4（种)不同选修方案．由分步乘法计数原理，不同的选修方案共有6×4×4＝96（种)．]组合数的性质错误!错误!错误!(2）C错误!＋C错误!＋C错误!＋C错误!＋C错误!＋C错误!;(3)C错误!·C错误!（n＞0，n∈N)．［解］（1）原式＝C错误!＋C错误!×1＝错误!＋错误!＝56＋4 950＝5 006。
第一章：1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。
解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。
1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。
如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。
而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。
故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。
1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？解：这是一组圆排列问题，10个人围圆就坐共有10!10 种方式。
两人坐在一起的方式数为9!92⨯,故两人不坐在一起的方式数为：9！-2*8！。
1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？解：(1)在1到9999中考虑，不是4位数的整数前面补足0，例如235写成0235,则问题就变为求：x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有F （4，5）=⎪⎪⎭⎫ ⎝⎛-+=515456 (2)分为求：x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1将它们相加即得，F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。
3.1 某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议?解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28甲参加的会议数为 28+5=333.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。
解：设 A 3：被3整除的数的集合A 5：被5整除的数的集合 A 7：被7整除的数的集合 所以 ||=||-||=-=33-4=29 3.3 n 个代表参加会议，试证其中至少有2个人各自的朋友数相等解：每个人的朋友数只能取0，1，…，n －1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n －2．故这n 个人的朋友数的实际取数只 有n －1种可能．，根据鸽巢原理所以至少有２人的朋友数相等．×3.4试给出下列等式的组合意义0j j 0(1)=(1), 1n-m -j+1(2)(1)1 j 1(3)...(1) 1 12m l l n ml n m m n l n k m n k l k l n m l n m l m l m l m l m l m l m m m m m l =-=--⎛⎫⎛⎫⎛⎫-≥≥ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭---⎛⎫⎛⎫⎛⎫=- ⎪ ⎪ ⎪--⎝⎭⎝⎭⎝⎭+-++++⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫=-+-+- ⎪ ⎪ ⎪ ⎪ ⎪-+++⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭∑∑证明：（1）从n 个不同元素中取k ，使得其中必含有m 个特定元素的方案数为)()(kn m n mk m n --=--。
设这m 个元素为a 1,a 2,…,a m , Ai 为包含a i 的组合（子集），i=1,…,m.1212|...|(...)12 =( (1))1 2 =(1) m m ml n A A A A A A k n m n m n m n m k k k m k m n l l k ⎛⎫=- ⎪⎝⎭---⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭-⎛⎫⎛- ⎪⎝⎭ 0ml =⎫ ⎪⎝⎭∑ （2）把l 个无区别的球放到n 个不同的盒子，但有m 个空盒子的方案数为11n l m n m -⎛⎫⎛⎫⎪ ⎪--⎝⎭⎝⎭令k=n-m ，设A i 为第i 个盒子有球，i=1，2，…k12k 121|...|(...)1k 11211 =(...(1)) 1 2 k kk l A A A A A A k k l k l k k l k k k l k l l k l +-⎛⎫=- ⎪⎝⎭+--+--+--+-⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭kj j 0k k-j+1 =(1)j l l =-⎛⎫⎛⎫- ⎪ ⎪⎝⎭⎝⎭∑（3）设A i 为m+l 个元素中去m+i 个，含特定元素a 的方案集；N i 为m+l 个元素中取m+i个的方案数。
新教材高中数学学生用书新人教B版选择性必修第二册：第1课时组合与组合数及组合数性质[课标解读] 1.通过实例，理解组合的概念；能利用计数原理、排列定义推导组合数公式.2.能够结合具体实例，理解排列、组合与两个计数原理的关系，能够运用两个计数原理推导排列、组合的相关公式，并能够运用它们解决简单的实际问题．【教材要点】知识点一组合的概念一般地，从n个不同对象中取出m(m≤n)个对象并成________，称为从n个不同对象中取出m个对象的一个组合．知识点二组合数的概念从n个不同对象中取出m(m≤n)个对象的________的个数，称为从n个不同对象中取出表示．m个对象的组合数，用符号C mn知识点三组合数公式及其性质(1)公式：C n m＝________＝________．(2)性质：C n m＝________，C n m＋C n m−1＝________．(3)规定：C n0＝________．【基础自测】1.下列判断不正确的是( )A.两个组合相同的充要条件是组成组合的对象完全相同B．从a1，a2，a3三个不同对象中任取两个对象组成一个组合，所有组合的个数为C23 C．从甲、乙、丙3名同学中选出2名去参加某两个乡镇的社会调查，有多少种不同的选法是组合问题D．从甲、乙、丙3名同学中选出2名，有3种不同的选法2．从2，3，5，7，11中每次选出两个不同的数作为分数的分子、分母，则可产生不同的分数的个数是________，其中真分数的个数是________．3．C62＝________，C1817＝________．4．从3，5，7，11这四个数中任取两个相乘，可以得到不相等的积的个数为________．题型1 组合的概念例1 判断下列各事件是排列问题还是组合问题．(1)10支球队以单循环进行比赛(每两队比赛一次)，这次比赛需要进行多少场次？(2)10支球队以单循环进行比赛，这次比赛冠、亚军获得者有多少种可能？(3)从10个人里选3个代表去开会，有多少种选法？(4)从10个人里选出3个不同学科的课代表，有多少种选法？状元随笔要确定是组合还是排列问题，只需确定取出的对象是否与顺序有关．方法归纳1．根据排列与组合的定义进行判断，区分排列与组合问题，先确定完成的是什么事件，然后看问题是否与顺序有关，与顺序有关的是排列，与顺序无关的是组合．2．区分有无顺序的方法把问题的一个选择结果写出来，然后交换这个结果中任意两个对象的位置，看是否会产生新的变化，若有新变化，即说明有顺序，是排列问题；若无新变化，即说明无顺序，是组合问题．跟踪训练1 判断下列问题是组合还是排列，并用组合数或排列数表示出来．(1)若已知集合{1，2，3，4，5，6，7}，则集合的子集中有3个元素的有多少？(2)8人相互发一个电子邮件，共发了多少个邮件？(3)在北京、上海、广州、成都四个民航站之间的直达航线上，有多少种不同的飞机票？有多少种不同的飞机票价？(4)从集合{1，2，3，4}中任取两个不同对象相乘，有多少个不同的结果？完成的“这件事”指的是什么？(5)从集合{1，2，3，4}中任取两个不同对象相除，有多少个不同结果？这是排列问题，还是组合问题？完成的“这件事”指的是什么？题型2 组合的列举问题(逻辑推理)例2 已知A ，B ，C ，D ，E 五个元素，写出每次取出3个元素的所有组合．方法归纳1．此类列举所有从n 个不同元素中选出m 个元素的组合，可借助本例所示的“顺序后移法”(如法一)或“树形图法”(如法二)，直观地写出组合，做到不重复不遗漏．2．由于组合与顺序无关．故利用“顺序后移法”时箭头向后逐步推进，且写出的一个组合不可交换位置．如写出ab 后，不必再交换位置为ba ，因为它们是同一组合．画“树形图”时，应注意顶层及下枝的排列思路，防止重复或遗漏．跟踪训练2 从5个不同的对象a ，b ，c ，d ，e 中取出2个，写出所有不同的组合．题型3 组合数公式的应用例3 (1)计算C 104－C 73·A 33.(2)求证：C n m ＝m ＋1n ＋1C n+1m+1. (3)从乒乓球运动员男5名、女6名中组织一场混合双打比赛，不同的组合方法种数为( )A ．C 52C 62B ．C 52A 62C ．C 52A 22C 62A 22D ．A 52A 62状元随笔 根据题目的特点，选择适当的组合数公式进行求值或证明．方法归纳关于组合数计算公式的选取1．涉及具体数字的可以直接用公式C n m＝A n m A mm ＝n (n−1)(n−2)···(n−m+1)m!计算．2．涉及字母的可以用阶乘式C n m ＝n!m!(n−m )!计算．3．计算时应注意利用组合数的性质C n m ＝C n n−m 简化运算．跟踪训练3 (1)10×9×8×···×41×2×3×···×7可表示为( )A ．A 106B ．A 107C ．C 106D ．C 107(2)算式m (m+1)(m+2)···(m+20)20!可以表示为( )A ．A m+2020B ．C m+2020 C ．21C m+2020D ．21C m+2021(3)新冠病毒爆发初期，全国支援武汉的活动中，需要从A 医院某科室的6名男医生、4名女医生中分别选派3名男医生和2名女医生，则不同的选派方案共有________种．(用数字作答)题型4 组合的性质 【思考探究】1．试用两种方法求：从a ，b ，c ，d ，e 5人中选出3人参加数学竞赛，2人参加英语竞赛，共有多少种选法？你有什么发现？你能得到一般结论吗？[提示] 方法一：从5人中选出3人参加数学竞赛，剩余2人参加英语竞赛，共C 53＝5×4×33×2×1＝10(种)选法．方法二：从5人中选出2人参加英语竞赛，剩余3人参加数学竞赛，共C 52＝5×42＝10(种)不同选法．经求解发现C 53＝C 52.推广到一般结论有C n m ＝C n n−m.2．从含有队长的10名排球队员中选出6人参加比赛，共有多少种选法？[提示] 共有C 106＝10×9×8×7×4×56×5×4×3×2×1＝210(种)选法．3．在2中，若队长必须参加，有多少种选法？若队长不能参加有多少种选法？由2，3，你发现什么结论？你能推广到一般结论吗？[提示] 若队长必须参加，共C 95＝126(种)选法．若队长不能参加，共C 96＝84(种)选法． 由2，3发现从10名队员中选出6人可分为队长参赛与队长不参赛两类，由分类加法计数原理可得：C 106 ＝C 95＋C 96.一般地：C n+1m ＝C n m ＋C n m−1.例4 (1)计算C 43＋C 53＋C 63＋…＋C 20183的值为( )A ．C 20194B ．C 20195C ．C 20194－1 D ．C 20195－1(2)解方程C 14x ＝C 142x−4的解为________．方法归纳1．性质“C n m ＝C n n−m”的意义及作用2．与排列组合有关的方程或不等式问题要用到排列数、组合数公式，以及组合数的性质，求解时，要注意由C n m中的m ∈N ＋，n ∈N ＋，且n ≥m 确定m ，n 的范围，因此求解后要验证所得结果是否适合题意．跟踪训练4 (1)化简：C m 9－C m+19＋C m 8＝________；(2)计算C 9996＋C 9997＝________．(3)若C 202n−3＝C 20n+2(n ∈N ＋)，则n ＝( ) A ．5 B ．7 C ．5或7 D ．5或6(4)若3A n 3－6A n 2＝4C n+1n−1，则n ＝( ) A ．8 B ．7 C ．6 D ．5教材反思3．1.3 组合与组合数第1课时组合与组合数及组合数性质新知初探·自主学习[教材要点]知识点一一组知识点二所有组合知识点三(1)A n mA m mn！m！(n−m)！(2)C n n−m C n+1m(3)1[基础自测]1．解析：A正确．因为只要两个组合的元素相同，不论元素的顺序如何，都是相同的组合．B正确．由组合数的定义可知正确．C错误．因为选出2名同学还要分到不同的两个乡镇，这是排列问题．D正确．因为从甲、乙、丙3人中选两名有：甲乙，甲丙，乙丙，共3个组合，即有3种不同选法．答案：C2．解析：产生分数可分两步：第一步，产生分子有5种方法；第二步，产生分母有4种方法，共有5×4＝20个分数，且各不相同．产生真分数，可分四类：第一类，当分子是2时，有4个真分数，同理，当分子分别是3，5，7时，真分数的个数分别是3，2，1，共有4＋3＋2＋1＝10个真分数．答案：20 10＝15，3．解析：C62＝6×52C1817＝C181＝18.答案：15 184．解析：从四个数中任取两个数的取法为C42＝6.答案：6课堂探究·素养提升例 1 解析：(1)是组合问题，因为每两个队比赛一次并不需要考虑谁先谁后，没有顺序的区别．(2)是排列问题，因为甲队得冠军、乙队得亚军与甲队得亚军、乙队得冠军是不一样的，是有顺序的区别．(3)是组合问题，因为3个代表之间没有顺序的区别．(4)是排列问题，因为3个人中，担任哪一科的课代表是有顺序的区别．跟踪训练1 解析：(1)已知集合的对象具有无序性，因此含3个元素的子集个数与元素的顺序无关，是组合问题，共有C73个．(2)发邮件与顺序有关，是排列问题，共发了A82个电子邮件．(3)飞机票与起点站、终点站有关，故求飞机票的种数是排列问题，有A42种飞机票；票价只与两站的距离有关，故票价的种数是组合问题，有C42种票价．＝6(个)不同结果．(4)共有C42＝4×32完成的“这件事”是指：从集合{1，2，3，4}中任取两个不同对象并相乘．(5)共有A42－2＝10(个)不同结果；这个问题属于排列问题；完成的“这件事”是指：从集合{1，2，3，4}中任取两个不同对象并相除．例2 解析：方法一：可按AB→AC →AD →BC →BD →CD 顺序写出，即所以所有组合为ABC ，ABD ，ABE ，ACD ，ACE ，ADE ，BCD ，BCE ，BDE ，CDE .方法二：画出树形图，如图所示．由此可以写出所有的组合：ABC ，ABD ，ABE ，ACD ，ACE ，ADE ，BCD ，BCE ，BDE ，CDE . 注意书写的规范性： ①注意是否与顺序有关；②注意按顺序列举，不重不漏．列举法适合总数比较少的情形．跟踪训练2 解析：要想写出所有组合，就要先将元素按照一定顺序排好，然后按顺序用图示的方法将各个组合逐个标出来，如图所示：由此可得所有的组合为ab ，ac ，ad ，ae ，bc ，bd ，be ，cd ，ce ，de .例3 解析：(1)原式＝C 104−A 73＝10×9×8×74×3×2×1－7×6×5＝210－210＝0.(2)证明：∵右边＝m+1n+1C n+1m+1＝m+1n+1·(n+1)！(m+1)！(n−m )！＝n ！m ！(n−m )！＝C n m，左边＝C n m ，∴左边＝右边，故原式成立．(3)分两步进行：第一步，选出两名男选手，有C 52种方法；第二步，从6名女生中选出2名且与已选好的男生配对，有A 62种．故有C 52A 62种．故选B.答案：(1)见解析 (2)见解析 (3)B 跟踪训练3 解析：(1)10×9×8×…×41×2×3×…×7＝A 107A 77＝C 107A 77A 77＝C 107.(2)m (m+1)(m+2)…(m+20)20！＝(m+20)！(m−1)！20！＝(m+20)！(m−1)！[(m+20)−(m−1)]！×21＝21C m+2021.(3)根据题意，从6名男医生、4名女医生中分别选派3名男医生和2名女医生，共有C 63·C 42＝20×6＝120种选派方案． 答案：(1)D (2)D (3)120例4 解析：(1)C +43C 53+C 63+⋯+C 2 0183＝C 44+C 43+C 53+…+C 2 0183−C 44＝C 54+C 53+…+C 2 0183－1＝…＝C 2 0184+C 2 0183－1＝C 2 0194－1.(2)由题意知{x =2x −4，2x −4≤14，x ≤14或{x =14−(2x −4)，2x −4≤14，x ≤14，解得x ＝4或6.答案：(1)C (2)4或6跟踪训练4 解析：(1)原式＝(C m 9+C m 8)－C m+19＝C m+19 −C m ＋19＝0. (2)C 9996+C 9997＝C 10097＝C 1003＝161 700.(3)由题意知{2n −3=n +20≤2n −3≤200≤n +2≤20n ∈N +或{2n −3+n +2=200≤2n −3≤200≤n +2≤20n ∈N +，即n ＝5或7.(4)由题意知，3n (n －1)(n －2)－6n (n －1)＝4×(n+1)n 2×1，解得n ＝5(n =23舍去).答案：(1)0 (2)161 700 (3)C (4)D。
第一章答案第二章答案第三章答案第四章答案第一章答案1. (a) 45 ( {1,6},{2,7},{ 3,8}, ••{45,50})(b) 45 5+(4+3+2+1) = 235(1 26, 2、3门,3》4、8,…,45 46 50, 46 >47^50, 47》48、50, 49 > 50 )2. (a) 5!8!(b) 7! P(8,5)(c) 2 P(5,3) 8!3. (a) n !P( n+1, m)(b) n! (m+1)!(c) 2!((m+n-2)+1)!4. 2 P(24,5) 20!5. 2 5 P(8,2)+3 4 P(8,2)6. (n+1)!-17. 用数学归纳法易证。
8. 41 319. 设n=p1n1p2n2-p k nk,则n2的除数个数为(2p1+1) (2p2+1) •••(2p k+1).10. 1)用数学归纳法可证n能表示成题中表达式的形式；2)如果某n可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a1；再对等式两端的商除以3取余数，又可得a2；对等式两端的商除以4取余数, 又可得a3；…；这说明表达式是唯一的。
11. 易用C(m,n)=m!/(n!(m-n)!)验证等式成立。
组合意义：右：从n个不同元素中任取叶1个出来，再从这叶1个中取一个的全体组合的个数；左：上述组合中，先从n个不同元素中任取1个出来，每一个相同的组合要生复C(n-1,r)次。
n n12. 考虑 7 CnX k =(1 x)n,求导数后有kC^k—1二n(1 x)2,k=0 k=0n令x=1,即知 7 kC：= n2n，k=013. 设此n个不同的数由小到大排列后为a1, a2,…,a。
当第二组最大数为a k时，第二组共有2k-1种不同的可能，第一组有2n-k-1种不同的可能。
故符合要求的n -4不同分组共有 a 2k4(2n4< -1)=(n-2)2n‘ 1 种。
