Richard组合数学第5版-第5章课后习题答案(英文版)
Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul Terwilliger
Selected solutions for Chapter5
1.For an integer k and a real number n,we show
n k
=
n?1
k?1
+
n?1
k
.
First assume k≤?1.Then each side equals0.Next assume k=0.Then each side equals 1.Next assume k≥1.Recall
P(n,k)=n(n?1)(n?2)···(n?k+1).
We have
n k
=
P(n,k)
k!
=
nP(n?1,k?1)
k!
.
n?1 k?1
=
P(n?1,k?1)
(k?1)!
=
kP(n?1,k?1)
k!
.
n?1
k
=
P(n?1,k)
k!
=
(n?k)P(n?1,k?1)
k!
.
The result follows.
2.Pascal’s triangle begins
1
11
121
1331
14641
15101051
1615201561
172135352171
18285670562881
193684126126843691
1104512021025221012045101
···
1
3.Let Z denote the set of integers.For nonnegative n∈Z de?ne F(n)=
k∈Z
n?k
k
.
The sum is well de?ned since?nitely many summands are nonzero.We have F(0)=1and F(1)=1.We show F(n)=F(n?1)+F(n?2)for n≥2.Let n be https://www.wendangku.net/doc/6515673729.html,ing Pascal’s formula and a change of variables k=h+1,
F(n)=
k∈Z
n?k
k
=
k∈Z
n?k?1
k
+
k∈Z
n?k?1
k?1
=
k∈Z
n?k?1
k
+
h∈Z
n?h?2
h
=F(n?1)+F(n?2).
Thus F(n)is the n th Fibonacci number.
4.We have
(x+y)5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
and
(x+y)6=x6+6x5y+15x4y2+20x3y3+15x2y4+6xy5+y6.
5.We have
(2x?y)7=
7
k=0
7
k
27?k(?1)k x7?k y k.
6.The coe?cient of x5y13is35(?2)13 18
5
.The coe?cient of x8y9is0since8+9=18.
https://www.wendangku.net/doc/6515673729.html,ing the binomial theorem,
3n=(1+2)n=
n
k=0
n
k
2k.
Similarly,for any real number r,
(1+r)n=
n
k=0
n
k
r k.
https://www.wendangku.net/doc/6515673729.html,ing the binomial theorem,
2n=(3?1)n=
n
k=0
(?1)k
n
k
3n?k.
2
9.We have
n k =0
(?1)k n
k 10k =(?1)n n k =0(?1)n ?k n k 10k =(?1)n (10?1)n =(?1)n 9n .The sum is 9n for n even and ?9n for n odd.10.Given integers 1≤k ≤n we show
k n k =n n ?1k ?1
.Let S denote the set of ordered pairs (x,y )such that x is a k -subset of {1,2,...,n }and y
is an element of x .We compute |S |in two ways.(i)To obtain an element (x,y )of S there are n k choices for x ,and for each x there are k choices for y .Therefore |S |=k n k .(ii)To
obtain an element (x,y )of S there are n choices for y ,and for each y there are n ?1
k ?1 choices for x .Therefore |S |=n n ?1k ?1
.The result follows.
11.Given integers n ≥3and 1≤k ≤n .We show
n k ? n ?3k = n ?1k ?1 + n ?2k ?1 + n ?3
k ?1
.Let S denote the set of k -subsets of {1,2,...,n }.Let S 1consist of the elements in S that
contain 1.Let S 2consist of the elements in S that contain 2but not 1.Let S 3consist of the elements in S that contain 3but not 1or 2.Let S 4consist of the elements in S that do
not contain 1or 2or 3.Note that {S i }4i =1partition S so |S |= 4
i =1|S i |.We have
|S |= n k ,|S 1|= n ?1k ?1 ,|S 2|= n ?2k ?1 ,|S 3|= n ?3k ?1 ,|S 4|= n ?3
k .
The result follows.12.We evaluate the sum
n
k =0
(?1)k n
k 2
.
First assume that n =2m +1is odd.Then for 0≤k ≤m the k -summand and the (n ?k )-summand are opposite.Therefore the sum equals 0.Next assume that n =2m is even.To
evaluate the sum in this case we compute in two ways the the coe?cient of x n in (1?x 2)n .(i)By the binomial theorem this coe?cient is (?1)m 2m m .(ii)Observe (1?x 2)=(1+x )(1?x ).We have
(1+x )n =n k =0
n k x k
,
(1?x )n =n k =0
n
k (?1)k x k .
3
By these comments the coe?cient of x n in(1?x2)n is
n k=0
n
n?k
(?1)k
n
k
=
n
k=0
(?1)k
n
k
2
.
Therefore
n
k=0(?1)k
n
k
2
=(?1)m
2m
m
.
13.We show that the given sum is equal to
n+3
k .
The above binomial coe?cient is in row n+3of Pascal’s https://www.wendangku.net/doc/6515673729.html,ing Pascal’s formula, write the above binomial coe?cient as a sum of two binomial coe?ents in row n+2of Pascal’s triangle.Write each of these as a sum of two binomial coe?ents in row n+1of Pascal’s triangle.Write each of these as a sum of two binomial coe?ents in row n of Pascal’s triangle.The resulting sum is
n k
+3
n
k?1
+3
n
k?2
+
n
k?3
.
14.Given a real number r and integer k such that r=k.We show
r k
=
r
r?k
r?1
k
.
First assume that k≤?1.Then each side is0.Next assume that k=0.Then each side is 1.Next assume that k≥1.Observe
r k
=
P(r,k)
k!
=
rP(r?1,k?1)
k!
,
and
r?1
k
=
P(r?1,k)
k!
=
(r?k)P(r?1,k?1)
k!
.
The result follows.
15.For a variable x consider
(1?x)n=
n
k=0
n
k
(?1)k x k.
4
Take the derivative with respect to x and obtain
?n(1?x)n?1=
n
k=0
n
k
(?1)k kx k?1.
Now set x=1to get
0=
n
k=0
n
k
(?1)k k.
The result follows.
16.For a variable x consider
(1+x)n=
n
k=0
n
k
x k.
Integrate with respect to x and obtain
(1+x)n+1 n+1=
n
k=0
n
k
x k+1
k+1
+C
for a constant C.Set x=0to?nd C=1/(n+1).Thus
(1+x)n+1?1
n+1=
n
k=0
n
k
x k+1
k+1
.
Now set x=1to get
2n+1?1 n+1=
n
k=0
n
k
1
k+1
.
17.Routine.
18.For a variable x consider
(x?1)n=
n
k=0
n
k
(?1)n?k x k.
Integrate with respect to x and obtain
(x?1)n+1 n+1=
n
k=0
n
k
(?1)n?k
x k+1
k+1
+C
for a constant C.Set x=0to?nd C=(?1)n+1/(n+1).Thus
(x?1)n+1?(?1)n+1
n+1=
n
k=0
n
k
(?1)n?k
x k+1
k+1
.
5
Now set x =1to get
(?1)n n +1=n k =0
n k
(?1)n ?k 1
k +1.Therefore
1
n +1=n k =0 n k (?1)k 1k +1
.19.One readily checks
2 m 2 + m 1
=m (m ?1)+m =m 2.Therefore
n k =1
k 2=
n
k =0
k 2
=2n
k =0 k 2 +
n k =0
k
1
=2 n +13 +
n +12 =(n +1)n (2n +1)6
.
20.One readily checks
m 3=6 m 3 +6 m 2 + m
1
.
Therefore
n k =1
k
3
=
n
k =0
k 3
=6
n
k =0 k
3
+6n k =0 k
2 +n k =0
k
1 =6 n +14 +6 n +13 +
n +12 =
(n +1)2n 24= n +12 2.
6
21.Given a real number r and an integer k .We show
?r
k
=(?1)k
r +k ?1k .First assume that k <0.Then each side is zero.Next assume that k ≥0.Observe
?r k =(?r )(?r ?1)···(?r ?k +1)
k !
=(?1)k
r (r +1)···(r +k ?1)
k !=(?1)k
r +k ?1
k
.22.Given a real number r and integers k,m .We show
r m m k = r k r ?k
m ?k
.
First assume that m Observe r m m k = r (r ?1)···(r ?m +1)m !m ! k !(m ?k )! = r (r ?1)···(r ?m +1)k !(m ?k )! = r (r ?1)···(r ?k +1)k !(r ?k )(r ?k ?1)···(r ?m +1)(m ?k )! = r k r ?k m ?k . 23.(a) 2410 .(b) 94 156 .(c) 94 93 63 .(d) 94 156 ? 94 93 63 . 24.The number of walks of length 45is equal to the number of words of length 45involving 10x ’s,15y ’s,and 20z ’s.This number is 45! 10!×15!×20! . 7 25.Given integers m 1,m 2,n ≥0.Show n k =0 m 1k m 2n ?k = m 1+m 2 n . Let A denote a set with cardinality m 1+m 2.Partition A into subsets A 1,A 2with cardinalities m 1and m 2respectively.Let S denote the set of n -subsets of A .We compute |S |in two ways.(i)By construction |S |= m 1+m 2 n . (ii)For 0≤k ≤n let the set S k consist of the elements in S whose intersection with A 1 has cardinality k .The sets {S k }n k =0partition S ,so |S |= n k =0|S k |.For 0≤k ≤n we now compute |S k |.To do this we construct an element x ∈S k via the following 2-stage procedure: stage to do #choices 1pick x ∩A 1 m 1k 2 pick x ∩A 2 m 2n ?k The number |S k |is the product of the entries in the right-most column above,which comes to m 1k m 2n ?k .By these comments |S |=n k =0 m 1k m 2 n ?k . The result follows. 26.For an integer n ≥1show n k =1 n k n k ?1 = 12 2n +2 n +1 ? 2n n .Using Problem 25, n k =1 n k n k ?1 = n k =0 n k n k ?1 = n k =0 n k n n +1?k = 2n n +1 =12 2n n ?1 +12 2n n +1 . 8 It remains to show 12 2n n ?1 +12 2n n +1 =12 2n +2n +1 ? 2n n . This holds since 2n n ?1 +2 2n n + 2n n +1 = 2n +1n + 2n +1 n +1 = 2n +2n +1 . 27.Given an integer n ≥1.We show n (n +1)2n ?2 =n k =1 k 2 n k . Let S denote the set of 3-tuples (s,x,y )such that s is a nonempty subset of {1,2,...,n } and x,y are elements (not necessarily distinct)in s .We compute |S |in two ways.(i)Call an element (s,x,y )of S degenerate whenever x =y .Partition S into subsets S +,S ?with S +(resp.S ?)consisting of the degenerate (resp.nondegenerate)elements of S .So |S |=|S +|+|S ?|.We compute |S +|.To obtain an element (s,x,x )of S +there are n choices for x ,and given x there are 2n ?1choices for s .Therefore |S +|=n 2n ?1.We compute |S ?|.To obtain an element (s,x,y )of S ?there are n choices for x ,and given x there are n ?1choices for y ,and given x,y there are 2n ?2choices for s .Therefore |S ?|=n (n ?1)2n ?2.By these comments |S |=n 2n ?1+n (n ?1)2n ?2=n (n +1)2n ?2. (ii)For 1≤k ≤n let S k denote the set of elements (s,x,y )in S such that |s |=k .The sets {S k }n k =1give a partition of S ,so |S |= n k =1|S k |.For 1≤k ≤n we compute |S k |.To obtain an element (s,x,y )of S k there are n k choices for s ,and given s there are k 2ways to choose the pair x,y .Therefore |S k |=k 2 n k .By these comments |S |=n k =1k 2 n k . The result follows. 28.Given an integer n ≥1.We show n k =1 k n k 2=n 2n ?1n ?1 .Let S denote the set of ordered pairs (s,x )such that s is a subset of {±1,±2,...,±n }and x is a positive element of s .We compute |S |in two ways.(i)To obtain an element (s,x )of S There are n choices for x ,and given x there are 2n ?1 n ?1 choices for s .Therefore |S |=n 2n ?1 n ?1 . 9 (ii)For1≤k≤n let S k denote the set of elements(s,x)in S such that s contains exactly k positive elements.The sets{S k}n k=1partition S,so|S|= n k=1 |S k|.For1≤k≤n we compute|S k|.To obtain an element(s,x)of S k there are n k ways to pick the positive elements of s and n n?k = n k ways to pick the negative elements of s.Given s there are k ways to pick x.Therefore|S k|=k n k 2 .By these comments |S|= n k=1 k n k 2 . The result follows. 29.The given sum is equal to m2+m2+m3 n . To see this,compute the coe?cient of x n in each side of (1+x)m1(1+x)m2(1+x)m3=(1+x)m1+m2+m3. In this computation use the binomial theorem. 30,31,32.We refer to the proof of Theorem5.3.3in the text.Let A denote an antichain such that |A|= n n/2 . For0≤k≤n letαk denote the number of elements in A that have size k.So n k=0αk=|A|= n n/2 . As shown in the proof of Theorem5.3.3, n k=0αk n k ≤1, with equality if and only if each maximal chain contains an element of A.By the above comments n k=0αk n n/2 ? n k n k ≤0, with equality if and only if each maximal chain contains an element of A.The above sum is nonpositive but each summand is nonnegative.Therefore each summand is zero and the sum is zero.Consequently(a)each maximal chain contains an element of A;(b)for0≤k≤n eitherαk is zero or its coe?cient is zero.We now consider two cases. 10 Case:n is even.We show that for0≤k≤n,αk=0if k=n/2.Observe that for0≤k≤n, if k=n/2then the coe?cient ofαk is nonzero,soαk=0. Case:n is odd.We show that for0≤k≤n,eitherαk=0if k=(n?1)/2orαk=0 if k=(n+1)/2.Observe that for0≤k≤n,if k=(n±1)/2then the coe?cient ofαk is nonzero,soαk=0.We now show thatαk=0for k=(n?1)/2or k=(n+1)/2. To do this,we assume thatαk=0for both k=(n±1)/2and get a contradiction.By assumption A contains an element x of size(n+1)/2and an element y of size(n?1)/2. De?ne s=|x∩y|.Choose x,y such that s is maximal.By construction0≤s≤(n?1)/2. Suppose s=(n?1)/2.Then y=x∩y?x,contradicting the fact that x,y are incomparable. So s≤(n?3)/2.Let y denote a subset of x that contains x∩y and has size(n?1)/2. Let x denote a subset of y ∪y that contains y and has size(n+1)/2.By construction |x ∩y|=s+1.Observe y is not in A since x,y are comparable.Also x is not in A by the maximality of s.By construction x covers y so they are together contained in a maximal chain.This chain does not contain an element of A,for a contradiction. 33.De?ne a poset(X,≤)as follows.The set X consists of the subsets of{1,2,...,n}. For x,y∈X de?ne x≤y whenever x?y.For n=3,4,5we display a symmetric chain decomposition of this poset.We use the inductive procedure from the text. For n=3, ?,1,12,123 2,23 3,13. For n=4, ?,1,12,123,1234 4,14,124 2,23,234 24, 3,13,134 34. For n=5, ?,1,12,123,1234,12345 5,15,125,1235 4,14,124,1245 45,145 2,23,234,2345 25,235 24,245 3,13,134,1345 35,135 34,345. 11 34.For 0≤k ≤ n/2 there are exactly n k ? n k ?1 symmetric chains of length n ?2k +1. 35.Let S denote the set of 10jokes.Each night the talk show host picks a subset of S for his repertoire.It is required that these subsets form an antichain.By Corollary 5.3.2each antichain has size at most 105 ,which is equal to 252.Therefore the talk show host can continue for 252nights. https://www.wendangku.net/doc/6515673729.html,pute the coe?cient of x n in either side of (1+x )m 1(1+x )m 2=(1+x )m 1+m 2, In this computation use the binomial theorem. 37.In the multinomial theorem (Theorem 5.4.1)set x i =1for 1≤i ≤t .38.(x 1+x 2+x 3)4is equal to x 41+x 42+x 43+4(x 31x 2+x 31x 3+x 1x 32+x 32x 3+x 1x 33+x 2x 3 3) +6(x 21x 2 2+x 21x 23+x 22x 23)+12(x 21x 2x 3+x 1x 22x 3+x 1x 2x 23). 39.The coe?cient is 10! 3!×1!×4!×0!×2! which comes to 12600.40.The coe?cient is 9! 3!×3!×1!×2! ×13×(?1)3×2×(?2)2 which comes to ?40320. 41.One routinely obtains the multinomial theorem (Theorem 5.4.1)with t =3. 42.Given an integer t ≥2and positive integers n 1,n 2,...,n t .De?ne n = t i =1n i .We show n n 1n 2···n t = t k =1 n ?1 n 1···n k ?1 n k ?1n k +1···n t . Consider the multiset {n 1·x 1,n 2·x 2,...,n t ·x t }. Let P denote the set of permutations of this multiset.We compute |P |in two ways.(i)We saw earlier that |P |= n ! n 1!×n 2!×···×n t != n n 1n 2···n t .12 (ii)For1≤k≤t let P k denote the set of elements in P that have?rst coordinate x k.The sets{P k}t k=1partition P,so|P|= t k=1 |P k|.For1≤k≤t we compute|P k|.Observe that |P k|is the number of permutations of the multiset {n1·x1,...,n k?1·x k?1,(n k?1)·x k,n k+1·x k+1,...,n t·x t}. Therefore |P k|= n?1 n1···n k?1n k?1n k+1···n t . By these comments |P|= t k=1 n?1 n1···n k?1n k?1n k+1···n t . The result follows. 43.Given an integer n≥1.Show by induction on n that 1 (1?z)n = ∞ k=0 n+k?1 k z k,|z|<1. The base case n=1is assumed to hold.We show that the above identity holds with n replaced by n+1,provided that it holds for n.Thus we show 1 (1?z)n+1= ∞ =0 n+ z ,|z|<1. Observe 1 (1?z)n+1= 1 (1?z)n 1 1?z = ∞ k=0 n+k?1 k z k ∞ h=0 z h = ∞ =0 c z where c = n?1 + n 1 + n+1 2 +···+ n+ ?1 = n+ . The result follows. 13 44.(Problem statement contains typo)The given sum is equal to (?3)n .Observe (?3)n =(?1?1?1)n = n 1+n 2+n 3=n n n 1 n 2n 3 (?1)n 1+n 2+n 3 = n 1 +n 2 +n 3 =n n n 1 n 2n 3 (?1)n 1?n 2+n 3.Also 1=(1?1+1)n = n 1 +n 2 +n 3 =n n n 1n 2n 3 (?1)n 2. 45.(Problem statement contains typo)The given sum is equal to (?4)n .Observe (?4)n =(?1?1?1?1)n = n 1+n 2+n 3+n 4=n n n 1n 2n 3n 4 (?1)n 1+n 2+n 3+n 4= n 1 +n 2 +n 3 +n 4 =n n n 1n 2n 3n 4 (?1)n 1?n 2+n 3?n 4.Also 0=(1?1+1?1)n = n 1 +n 2 +n 3 +n 4 =n n n 1n 2n 3n 4 (?1)n 2+n 4. 46.Observe √30=5 3025 =5(1+z )1/2 z =1/5, =5∞ k =0 1/2k z k . For n =0,1,2,...the n th approximation to √ 30is a n =5n k =0 1/2k 5?k . We have 14 n a n 05 1 5.5 2 5.475 3 5.4775 4 5.4771875 5 5.47723125 6 5.477224688 7 5.477225719 8 5.477225551 9 5.477225579 47.Observe 101/3=2 10 8 1/3 =2(1+z)1/3z=1/4, =2 ∞ k=0 1/3 k z k. For n=0,1,2,...the n th approximation to101/3is a n=2 n k=0 1/3 k 4?k. We have n a n 02 1 2.166666667 2 2.152777778 3 2.154706790 4 2.154385288 5 2.154444230 6 2.154432769 7 2.154435089 8 2.154434605 9 2.154434708 48.We show that a poset with mn+1elements has a chain of size m+1or an antichain of size n+1.Our strategy is to assume the result is false,and get a contradiction.By assumption each chain has size at most m and each antichain has size at most n.Let r denote the size of the longest chain.So r≤m.By Theorem5.6.1the elements of the poset can be partitioned into r antichains{A i}r i=1 .We have|A i|≤n for1≤i≤r.Therefore mn+1= r i=1 |A i|≤rn≤mn, 15 for a contradiction.Therefore,the poset has a chain of size m+1or an antichain of size n+1. 49.We are given a sequence of mn+1real numbers,denoted{a i}mn i=0.Let X denote the set of ordered pairs{(i,a i)|0≤i≤mn}.Observe|X|=mn+1.De?ne a partial order≤on X as follows:for distinct x=(i,a i)and y=(j,a j)in X,declare x of{a i}mn i=0,and the antichains correspond to the(strictly)decreasing subsequences of{a i}mn i=0 . By Problem48,there exists a chain of size m+1or an antichain of size n+1.Therefore the sequence{a i}mn i=0has a(weakly)increasing subsequence of size m+1or a(strictly)decreasing subsequence of size n+1. 50.(i)Here is a chain of size four:1,2,4,8.Here is a partition of X into four antichains: 8,12 4,6,9,10 2,3,5,7,11 1 Therefore four is both the largest size of a chain,and the smallest number of antichains that partition X. (ii)Here is an antichain of size six:7,8,9,10,11,12.Here is a partition of X into six chains: 1,2,4,8 3,6,12 9 5,10 7 11 Therefore six is both the largest size of an antichain,and the smallest number of chains that partition X. 51.There exists a chain x1 16 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 组合图形的面积 方法与技巧 组合图形是由两个或两个以上的简单的几何图形组合而成的。组合的形式分为两种：一是拼合组合，二是重叠组合。由于组合图形具有条件相等的特点，往往使得问题的解决无从下手。要正确解答组合图形的面积，应该注意以下几点： 1．切实掌握有关简单图形的概念、公式，牢固建立空间观念； 2．仔细观察，认真思考，看清所求图形是由哪几个基本图形组合而成的； 3．适当采用增加辅助线等方法帮助解题； 4．采用割、补、分解、代换等方法，可将复杂问题变得简单。 回顾与复习： 长方形面积= 三角形面积= 正方形面积= 梯形面积= A级 基础点睛 典型例题1：一个等腰直角三角形，最长的边是12厘米，这个三角形的面积是多少平方厘米？ 【巩固练习1】：已知正方形ABCD的边长是7厘米，求正方形EFGH的面积。 典型例题2：如图正方形中套着一个长方形，正方形的边长是12厘 米，长方形的四个角的顶点把正方形的四条边各分成两段，其中长的一段是短的2倍。求中间长方形的面积。 【巩固练习2】：如图长方形ABCD的面积是16平方厘米，E、F都是所在 边的中点，求三角形AEF的面积。 典型例题3：求四边形ABCD的面积。（单位：厘米） 【巩固练习3】：求下图长方形ABCD的面积（单位：厘米）。 典型例题4：有一种将正方形内接于等腰直角三角形。已知等腰直角三角形的面积是72平方厘米，正方形的面积分别是多少？ 【巩固练习4】：有一种将正方形内接于等腰直角三角形。已知等腰直角三角形的面积是72平方厘米，正方形的面积分别是多少？ B级 培优拓展 典型例题5：四边形ABCD和四边形DEFG都是正方形，已知三角形AFH的面积是7平方厘米。三角形CDH的面积是多少平方厘米？ 【巩固练习5】：图中两个正方形的边长分别是6厘米和4厘米，求阴影部分的面积。 作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明： 第五章 区组设计与编码 1.拉丁方与正交拉丁方 拉丁方：由1，2，…，n 构成n ×n 方阵n n ij a ?)(，如果每行每列中1，2，…，n 各出现一次，则称此方阵为拉丁方。 如： ??? ? ? ?=12212 n ???? ? ? ?????? ? ?=12 3312231 21 3132321 3 n 正交换丁方：设()() n n ij n n ij a A a A ??==) 2(2) 1(1是两个n ×n 的拉丁方，如果矩阵 ()() n n ij ij a a ?) 2()1(,中2n 个数偶()) 2()1(,ij ij a a 互不相同，n j i ,,2, 1, =， 则称1A 和2A 正交，或称1A 和2A 是互相正交的拉丁方。 如：???? ? ? ?=???? ? ??=12 3312 231 ,213132 32121A A 由于??? ? ? ? ?)1,2() 2,1()3,3()3,1()1,3() 2,2()2,3()3,2()1,1(中元素两两不同，故21A A ⊥ 36名军官问题：ij a 表示军官的军衔为i ，军官所在的团为j ，()66),(?j i 要求第一个数字构成拉丁方，第二个数字也构成拉丁方，并且正交。 定理：两两相互正交的n 阶拉丁方的个数不超过n-1个 pf ：设k A A A ,,,21 是两两相互正交的n 阶拉丁方，往证1-≤n k 。设n a a a 21是1， 2，…，n 的一个全排列，() ,,,2,1,) (k l a A n n l ij l ==?对1A 作如下置换 ??? ? ??n a a a n 2 1 21，得一方阵() n n ij a A ?=) 1(1，则1A 与k A A ,2正交。 事实上，如果1A 不与2A 正交，则 ()() n n ij ij a a ?) 2() 1(,中至少有一对数偶出现次数超过1次，设该对数偶为),(m l a a ，则 ),(m a l 在( )) 2() 1(,ij ij a a 中至少出现2次，与2 1 ,A A 正交矛盾，由此不妨设k A A A ,,,21 的 第一行均为),,2,1(n ，任取,1k m l ≤<≤则方阵 ()() n n m ij ij a a ?) ()1(,的第一行均是),,(),2,1(),1,1((r n 从而1不能出现在k A A A ,,,21 的 第2行第1列元素，故这些元素只能取2，3，…, n 中一个，而且取法不能相同，故n k ≤。 2.域与有限域 域：),(,:) 1(,+→?+≠V V V V V φ Abel 群 b a b a +→),( （2） ),(:* * *?→??V V V V Abel 群 ab b a →),( }0/{* V V = （3）分配律成立 ac ab c b a +=+)( ca ba a c b +=+)( 则称),,(?+V 为域 例： Q ，R ，C ， {}Q b a bi a i Q ∈+=,|)( 二元域}1,0{2=F ， p 元域}1,,2,1,0{-=p F p 有限域：元素个数有限的域叫做有限域 比如： },,2,1,0{p F p =模p 的剩余类域， 取)(x f 是][x F p 中n 次不可约多项式，则 第八讲 组合数学 组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开 例1．圆周上有800个点，依顺时针方向标号为1,2,…,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k 号点染成了红色，则可依顺时针方向转过k 个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？ 解：易见，第k 号点能被染红的充要条件是 ?j ∈N *?{0}，使得a 0?2j ≡k (mod800)，1≤k ≤800 ① 这里a 0是最初染的点的号码，为求最大值，不妨令a 0=1.即2j ≡k (mod25×52). 当j=0,1,2,3,4时，k 分别为1,2,4,8,16，又由于2模25的阶20)2(25=δ，因此，当j ≥5时 2j+20-2j =2j (220-1)≡0(mod 800), 而对?k<20,k ∈N *，及j ≥5,j ∈N *，由于25+(2k -1)，所以 2j+k -2j =2j (2k -1)不为800的倍数. 所以，共存在5+20=25个k ，满足①式。 注：本题解法不止一种，但利用些同余理论，可使解法简洁许多. 例2．集合X 的覆盖是指X 的一族互不相同的非空子集A 1、A 2、…、A k ，它们的并集A 1∪A 2∪…∪A k =X ，现有集合X={1,2,…,n}，若不考虑A 1, A 2,…, A k 的顺序，试求X 的覆盖有多少个？ 解：首先，X 的非空子集共有2n -1个，它们共组成了n 2 1 2--1个非空子集族.其次， 这些子集族中，不合某一元素i 的非空子集组成的非空子集族有( ) n 121 21---个；不含两 个元素的子集组成的族有( ) n 2 2 1 21---个；依次类推，则由容斥原理，X 的覆盖共有 ()() --+--------)12 ()12 ()12 (1 22 1 21 1 221n n n n n =())12()1(1 2 1 ---=-∑n n j n j j 个. 注：有些组合计数问题直接计数较难，但从反面考虑简洁明了. 组合数学课后标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 组合数学第01讲_比赛中的推理 知识图谱 组合数学第01讲_比赛中的推理-一、比赛中的推理场次计算总分计算具体赛程积分与名次得失球相关 一：比赛中的推理 知识精讲 比赛中的推理:这些问题有各种不同的形式：有分析对阵情况的，有计算各队积分的，有利用积分排名的，甚至还有讨论进球数、失球数的．不同类型的问题我们应该用不同的方法来处理． 在推理中，画示意图或表格用来分析比赛问题，能够让我们对比赛的情况更为直观明了． 1．比赛分类： （1）淘汰赛：每场比赛踢掉一支球队，只取第一名． （2）单循环赛：n支球队，每两队比赛1场，总共比赛场． （3）双循环比赛：n支球队，每两球比赛2场总共比赛场． 2．与比赛积分有关的推理问题．两种常见的计分法： （1）2分制计分法：“每场比赛胜者得2分，负者得0分，平局各得1分”．这种情况下，每场比赛无论结果如何，双方总得分都是2分，因此所有选手的总分就等于“比赛场数×2”． （2）3分制计分法：“每场比赛胜者得3分，负者得0分，平局各的1分”．这种情况下，总分就是“胜负场数×3+平局场数×2”，或者写成“比赛场数×2-平局场数”． 三点剖析 重难点：要注意搞清比赛规则，特别是积分规则，对阵方式，认识总场次、总得分与某个对或人总得分、总场次间的区别与联系．．若是画对阵关系图，注意箭头表胜负，虚线表示平局． 题模精讲 题模一场次计算 例、 某年级8个班级进行足球友谊赛，比赛采用单循环赛制（参加比赛的队每两队之间只进行一场比赛），胜一场得3分，负一场得0分，平一场得1分．某班级共得15分，并以无负局成绩获得冠军，那么该班共胜几场比赛 答案： 4 解析： 该班赛了7场．假设全是平局，应得7分．每将1场平局替换为胜场，总分增分，故该班共胜场． 例、 为弘扬亚运精神，四年级组织了篮球联赛，赛制为单循环制，即每两队之间都要比一场，计划安排15场比赛，应该邀请几个篮球队参加 答案： 6 解析： 由于，故应该邀请6个篮球队参加． 例、 甲、乙、丙、丁与小明五位同学进入象棋决赛．每两人都要比赛一盘，每胜一盘得2分，和一盘得1分，输一盘得0分．到现在为止，甲赛了4盘，共得了2分；乙赛了3盘，得了4分；丙赛了2盘，得了1分；丁赛了1盘，得了2分．那么小明现在已赛了______盘． 答案： 2 解析： 由题意可画出比赛图，已赛过的两人之间用线段连接． 由图看出小明赛了2盘． 组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k 李凡长版-组合数学课后习题答案-习题3 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的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），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有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”的可能； 依此类推，有 17 知识图谱 组合数学第01讲_比赛中的推理-一、比赛中的推理场次计算总分计算具体赛程积分与名次得失球相关 一：比赛中的推理 知识精讲 比赛中的推理:这些问题有各种不同的形式：有分析对阵情况的，有计算各队积分的，有利用积分排名的，甚至还有讨论进球数、失球数的．不同类型的问题我们应该用不同的方法来处理． 在推理中，画示意图或表格用来分析比赛问题，能够让我们对比赛的情况更为直观明了． 1．比赛分类： （1）淘汰赛：每场比赛踢掉一支球队，只取第一名． （2）单循环赛：n支球队，每两队比赛1场，总共比赛场． （3）双循环比赛：n支球队，每两球比赛2场总共比赛场．2．与比赛积分有关的推理问题．两种常见的计分法： （1）2分制计分法：“每场比赛胜者得2分，负者得0分，平局各得1分”．这种情况下，每场比赛无论结果如何，双方总得分都是2分，因此所有选手的总分就等于“比赛场数×2”． （2）3分制计分法：“每场比赛胜者得3分，负者得0分，平局各的1分”．这种情况下，总分就是“胜负场数×3+平局场数×2”，或者写成“比赛场数×2-平局场数”． 三点剖析 重难点：要注意搞清比赛规则，特别是积分规则，对阵方式，认识总场次、总得分与某个对或人总得分、总场次间的区别与联系．．若是画对阵关系图，注意箭头表胜负，虚线表示平局． 题模精讲 题模一场次计算 例1.1.1、 某年级8个班级进行足球友谊赛，比赛采用单循环赛制（参加比赛的队每两队之间只进行一场比赛），胜一场得3分，负一场得0分，平一场得1分．某班级共得15分，并以无负局成绩获得冠军，那么该班共胜几场比赛？ 答案： 4 解析： 该班赛了7场．假设全是平局，应得7分．每将1场平局替换为胜场，总分增分，故该班共胜场． 例1.1.2、 为弘扬亚运精神，四年级组织了篮球联赛，赛制为单循环制，即每两队之间都要比一场，计划安排15场比赛，应该邀请几个篮球队参加？ 答案： 6 解析： 由于，故应该邀请6个篮球队参加． 第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 ① 考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P ?个。 ② 考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P ?个。 第五章 P ólya 计数理论 1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类. 解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|S n |＝5。 ??? ? ?????? ?????? ??=512345432152431543215413254321) 23)(14)(5)(234)(123( ??? ? ?????? ??=51234543215214354321 ??? ? ??=5341254321 )5)(34)(12(= （5）（12）（34）的置换的型为1122而S n 中属于1122型的元素个数为15 21!1!2! 52 1=个其共轭类为 （5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24） 2. 设D 是n 元集合,G 是D 上的置换群.对于D 的子集A 和B ,如果存在G ∈σ, 使得}|)({A a a B ∈=σ,则称A 与B 是等价的.求G 的等价类的个数. 解：根据Burnside 引理∑= =n i i a c G l 1 1)(1，其中c 1(a i )表示在置换a i 作用下保持不变的元素个数，则有 c 1(σI )=n; 设在σ的作用下，A 的元素在B 中的个数为i ，则 c 2(σ)=n －2i ； 若没有其他置换，则G 诱出来的等价类个数为l=i n i n n -=-+)]2([2 1 3. 由0,1,6,8,9组成的n 位数,如果把一个数调转过来读得到另一个数,则称这两 个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n 位数有多少个？ 解：该题可理解为相当于n 位数，0，1，6，8，9这5个数存在一定的置换关系 第一章什么是组合数学 组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种 方法去实现它。此时，人们就可以计数并将它们分类。 虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?” “存在一个……吗?” “能用多少方法—…?” “计算……的数目。” 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul Terwilliger Selected solutions for Chapter5 1.For an integer k and a real number n,we show n k = n?1 k?1 + n?1 k . First assume k≤?1.Then each side equals0.Next assume k=0.Then each side equals 1.Next assume k≥1.Recall P(n,k)=n(n?1)(n?2)···(n?k+1). We have n k = P(n,k) k! = nP(n?1,k?1) k! . n?1 k?1 = P(n?1,k?1) (k?1)! = kP(n?1,k?1) k! . n?1 k = P(n?1,k) k! = (n?k)P(n?1,k?1) k! . The result follows. 2.Pascal’s triangle begins 1 11 121 1331 14641 15101051 1615201561 172135352171 18285670562881 193684126126843691 1104512021025221012045101 ··· 1 3.Let Z denote the set of integers.For nonnegative n∈Z de?ne F(n)= k∈Z n?k k . The sum is well de?ned since?nitely many summands are nonzero.We have F(0)=1and F(1)=1.We show F(n)=F(n?1)+F(n?2)for n≥2.Let n be https://www.wendangku.net/doc/6515673729.html,ing Pascal’s formula and a change of variables k=h+1, F(n)= k∈Z n?k k = k∈Z n?k?1 k + k∈Z n?k?1 k?1 = k∈Z n?k?1 k + h∈Z n?h?2 h =F(n?1)+F(n?2). Thus F(n)is the n th Fibonacci number. 4.We have (x+y)5=x5+5x4y+10x3y2+10x2y3+5xy4+y5 and (x+y)6=x6+6x5y+15x4y2+20x3y3+15x2y4+6xy5+y6. 5.We have (2x?y)7= 7 k=0 7 k 27?k(?1)k x7?k y k. 6.The coe?cient of x5y13is35(?2)13 18 5 .The coe?cient of x8y9is0since8+9=18. https://www.wendangku.net/doc/6515673729.html,ing the binomial theorem, 3n=(1+2)n= n k=0 n k 2k. Similarly,for any real number r, (1+r)n= n k=0 n k r k. https://www.wendangku.net/doc/6515673729.html,ing the binomial theorem, 2n=(3?1)n= n k=0 (?1)k n k 3n?k. 2 1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？ 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！ n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１ 1.7题 试证：)2()2)(1(n n n ++被2n 除尽。 证明：因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。 组合数学答案第五版期末答案问：仰韶文化不包括下列哪一项：（） 答：齐家文化 问：仰韶文化出土文物上具有一种统一的“人面鸟纹”形象。 答：错 问：仰韶文化处于华北地带，地质构造相对简单划一（）。 答：正确 问：仰韶文化的典型代表是西安的半坡遗址以及临潼的姜寨遗址。 答：正确 问：仰韶文化的典型器物是： 答：彩陶 问：汉语的北方方言区不包括（）。 答：上江官话 问：汉语的被动不能省略,但是量词可以省略。() 答：错误 问：汉语的词缀属于哪一种类型的词缀？ 答：自源型 问：汉语的句例边界不清楚。 答：正确 问：汉语的理解模式属于()。 答：上下文理解模式 问：（）提出了认同危机理论，把心理发展分为8个阶段。 答：埃里克逊 问：()提出了三界唯心,万法唯识的观点。 答：佛家 问：()提出了设计的十项原则。 答：迪特·拉姆斯 问：（）提出了生物发生定律，运用到数学教学即历史发生原理。 答：E·haeckel 问：()提出了私人政府的法这一概念。 答：马考利 问：郁达夫的小说《沉沦》与日本文学中的（）有千丝万缕的联系。 答：私小说 问：以下正确的是( ). 答：按主方职务的高低站成一列，职务最高者站首位,与客方职务最高者先行握手话别。主方职务最低的与客方职务最高的话别，最后才是主方职务最高的与客方职务最高的话别。告别时主客双方职务最高者可以多寒暄几句，以表惜别之情。 问：小说《沉沦》发表之后，引起了轩然大波，有人支持其创作，也有人反对。下列哪些作家是支持其创作的？（） 答：周作人郭沫若 问：以下关于《沉沦》小说主人公的解读，正确的有：（） 答：这是一个青春忧郁症患者。他的本我和超我都太强大，强大到无法调和，这导致了他最后的沉沦。“灵与肉的冲突”是青春期的主人公面临的最大难题。 问：演讲时的肢体语言可以是（） 答：身体自然放松手势要多用掌 问：辩论者需要将听、看、想三者相结合，才能获得对事物的准确认知。（） 答：√ 问：麝猫后睾吸虫第二中间宿主是鲤科鱼类。 答：对 问：弗兰西斯培根的方法论主要表现在: 答：科学归纳法 问：关于随机抽样，下列那一项说法是正确的（）。 答：随机化抽样可以令样本有较好的代表性抽样时应使得总体中的每一个个体都有同等的机会被抽取 问：异尖线虫第三期幼虫经口侵入人体后，病变特征包括（）。 答：消化道粘膜下层病变肝等其它脏器损伤入侵寄生处有鸡蛋大小肿块腹部绞痛(完整word版)组合数学课后答案
第五讲 组合图形面积
组合数学课后答案
组合数学 第五章
第八讲-组合数学
组合数学课后标准答案
组合数学第01讲比赛中的推理(六年级)
组合数学题目及标准答案
李凡长版-组合数学课后习题答案-习题3
组合数学第01讲比赛中的推理(六年级)
组合数学作业答案
李凡长版 组合数学课后习题答案 习题5
第一章 什么是组合数学
组合数学 课后答案
Richard组合数学第5版-第5章课后习题答案(英文版)
组合数学参考答案(卢开澄第四版) - 修改版
组合数学答案第五版期末答案.docx
- 第五章 递归关系及解法
- Richard组合数学第5版-第4章课后习题答案(英文版)
- 组合数学复习
- 组合数学参考答案(卢开澄第四版) - 修改版
- 组合数学【第5版】(英文版)第3章答案
- 组合数学作业答案解析
- 组合数学第四卢开澄标准答案第四章
- 组合数学作业答案
- 组合数学讲义 5章 抽屉原理
- 组合数学复习总结
- lu-计算机2009组合数学—第五章生成函数(一)
- 组合数学 第五章
- Richard组合数学第5版-第5章课后习题答案(英文版)
- 组合数学第五章
- 组合数学课件第五章容斥原理
- 组合数学_第6章6.4-6.5_
- 组合数学一PPT课件
- 软件2010组合数学第五章生成函数三
- 组合数学课件--第一章排列与组合讲解
- 吉林大学组合数学习题解答