当前位置：文档之家› Richard组合数学第5版-第4章课后习题答案(英文版)

Richard组合数学第5版-第4章课后习题答案(英文版)

Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul Terwilliger

Selected solutions for Chapter4

1.The permutation31524is followed by35124and preceded by31254.To see this,recall the display on page90.In that display the permutations of(1,2,3,4)are listed in24rows. According to the algorithm in Section4.1,for each row1,2,...,24we insert a5in the?ve possible locations of the given permutation,working from right to left for odd numbered rows and left to right for even numbered rows.The permutation3124appears on row9 which is odd,so for this row the5’s are inserted from right to left.

2.The mobile integers are8,3,7.For these integers the arrow points to an adjacent smaller integer.

3.Working from left to right across each row,

←?1←?

←?

?→5←?

←?

?→

←?

?→

←?

?→

←?

?→

←?1←?

←?

?→5←?

←?

?→

←?

?→

←?

?→

←?

?→

?→4←?

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→5←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?1←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→5←?

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?

?→

←?3←?

←?

?→5←?

←?

?→

←?

?→

←?

?→

←?

?→

4.For1≤k≤n the direction of k changes immediately after we move a mobile integer m (1≤m

5.The integer k is equal to the total number of inversions for the given permutation.Any switch of adjacent terms ab→ba either decreases this total by one(if a>b)or increases this total by one(if a

6.(a)We have

i12345678

b i24040010

(b)We have

i12345678

b i65113210

7.(a)Using algorithm1,

867

8657

48657

486573

4865723

48165723

Using algorithm2,

123

4123

41523

416523

4165723

48165723 (b)Using algorithm1,

768

7658

76584

736584

7365842

73658412

Using algorithm 2,

1123123412354123654127365412736584

8.(a)For a permutation of {1,2,3,4,5,6}the corresponding inversion sequence (b 1,b 2,b 3,b 4,b 5,b 6)satis?es 0≤b i ≤6?i for 1≤i ≤6.The total number of inversions is 6

i =1b i .This total is at most 5+4+3+2+1+0=15with equality if and only if b i =6?i for 1≤i ≤6.Therefore there is just one permutation with 15inversions.

(b)The number of permutations with 14inversions is equal to the number of integral solu-tions to

0≤b i ≤6?i

(1≤i ≤6),

6 i =1

b i =14.

Each solution (b 1,b 2,b 3,b 4,b 5,b 6)is obtained from (5,4,3,2,1,0)by subtracting 1from one

of the ?rst 5coordinates.This can be done in 5ways.Therefore there are 5permutations with 14inversions.

(c)The number of permutations with 13inversions is equal to the number of integral solutions to

0≤b i ≤6?i

(1≤i ≤6),

6 i =1

b i =13.

Each solution (b 1,b 2,b 3,b 4,b 5,b 6)is obtained from (5,4,3,2,1,0)by subtracting 1from two

of the ?rst 5coordinates ( 5

2 ways)or subtracting 2from one of the ?rst four coordinates (4ways).Therefore the number of solutions is 52 +4=14.There are 14permutations with 13inversions.

9.For a permutation i 1i 2···i n of {1,2,...,n }an inversion is an ordered pair (i k ,i )such that k < and i k >i .There are n 2 possibilities for (i k ,i ).Therefore the number of inversions is at most n

2 .The following are equivalent:(i)there are n 2 inversions;(ii)i k >i for 1≤k < ≤n ;(iii)i k =n ?k +1for 1≤k ≤n .Thus n ···321is the unique permutation with n 2

inversions.The permutations of {1,2,...,n }that have exactly n 2

?1inversions are obtained from n ···321by switching a single pair of adjacent terms.There are n ?1such permutations.

10.We have

256143

251643

215643

125643

125634

125364

123564

123546

123456

and

436251

436215

436125

431625

413625

143625

143265

142365

124365

123465

123456

11.(a)The set{x5,x4,x3}corresponds to

coordinate76543210

entry00111000 (b)The set{x7,x5,x3,x1}corresponds to

coordinate76543210

entry10101010 (c)The set{x6}corresponds to

coordinate76543210

entry01000000 12.(a){x4,x3,x1,x0};(b){x6,x4,x2,x0};(c){x3,x2,x1,x0}.

not contain)x i.

rank x4x3x2x1x0

000000

100001

200010

300011

400100

500101

600110

700111

801000

901001

1001010

1101011

1201100

1301101

1401110

1501111

1610000

1710001

1810010

1910011

2010100

2110101

2210110

2310111

2411000

2511001

2611010

2711011

2811100

2911101

3011110

3111111

does not contain)x i.

rank x5x4x3x2x1x0 0000000 1000001 2000010 3000011 4000100 5000101 6000110 7000111 8001000 9001001 10001010 11001011 12001100 13001101 14001110 15001111 16010000 17010001 18010010 19010011 20010100 21010101 22010110 23010111 24011000 25011001 26011010 27011011 28011100 29011101 30011110 31011111

rank x5x4x3x2x1x0

32100000

33100001

34100010

35100011

36100100

37100101

38100110

39100111

40101000

41101001

42101010

43101011

44101100

45101101

46101110

47101111

48110000

49110001

50110010

51110011

52110100

53110101

54110110

55110111

56111000

57111001

58111010

59111011

60111100

61111101

62111110

63111111 6

15.We convert to binary,add1,and then convert back:

subset{x4,x1,x0}{x7,x5,x3}{x7,x5,x4,x3,x2,x1,x0}{x0}

binary rep00010011101010001011111100000001 binary rep+100010100101010011100000000000010

next subset{x4,x2}{x7,x5,x3,x0}{x7,x6}{x1}

16.We convert to binary,subtract1,and then convert back:

subset{x4,x1,x0}{x7,x5,x3}{x7,x5,x4,x3,x2,x1,x0}{x0}

binary rep00010011101010001011111100000001 binary rep-100010010101001111011111000000000 prec.subset{x4,x1}{x7,x5,x2,x1,x0}{x7,x5,x4,x3,x2,x1}?

17.150=128+16+4+2has the binary representation10010110so the150th subset is {x7,x4,x2,x1}.200=128+64+8has binary representation11001000so the200th subset is{x7,x6,x3}.250=128+64+32+16+8+2has binary representation11111010so the 250th subset is{x7,x6,x5,x4,x3,x1}.

18.Consider the re?ected Gray code of order4.For0≤m≤15the m th term is g3g2g1g0 where

m g3g2g1g0

00000

10001

20011

30010

40110

50111

60101

70100

81100

91101

101111

111110

121010

131011

141001

151000

See the course notes for a4-cube representation.

19.The following is a noncyclic Gray code of order3:

rank codeword

0000

1001

2011

3010

4110

5100

6101

7111

20.The following is a cyclic Gray code of order3that is not the re?ected Gray code:

rank codeword

0000

1001

2011

3111

4101

5100

6110

7010

m g4g3g2g1g0 000000 100001 200011 300010 400110 500111 600101 700100 801100 901101 1001111 1101110 1201010 1301011 1401001 1501000 1611000 1711001 1811011 1911010 2011110 2111111 2211101 2311100 2410100 2510101 2610111 2710110 2810010 2910011 3010001 3110000

m g5g4g3g2g1g0 0000000 1000001 2000011 3000010 4000110 5000111 6000101 7000100 8001100 9001101 10001111 11001110 12001010 13001011 14001001 15001000 16011000 17011001 18011011 19011010 20011110 21011111 22011101 23011100 24010100 25010101 26010111 27010110 28010010 29010011 30010001 31010000

m g5g4g3g2g1g0

32110000

33110001

34110011

35110010

36110110

37110111

38110101

39110100

40111100

41111101

42111111

43111110

44111010

45111011

46111001

47111000

48101000

49101001

50101011

51101010

52101110

53101111

54101101

55101100

56100100

57100101

58100111

59100110

60100010

61100011

62100001

63100000 10

23.(a)The sum of the entries is4,which is even,so we change coordinate zero.The successor is010100111.

(b)The sum of the entries is4,which is even,so we change coordinate zero.The successor is110001101.

(c)the sum of the entries is9,which is odd.Coordinate zero is1so we change coordinate one.The successor is111111101.

24.(a)The sum of the entries is4,which is even.The sequence ends with10so we change coordinate two.The predecessor is010100010.

(b)The sum of the entries is4,which is even.The sequence ends with100so we change coordinate three.The predecessor is110000100

(c)The sum of the entries is9,which is odd.So we change coordinate zero.The predecessor is111111110.

25.

26.The lexicographic ordering is12,13,14,15,23,24,25,34,35,45.

27.The lexicographic ordering is123,124,125,126,134,135,136,145,146,156,234,235, 236,245,246,256,345,346,356,456.

28.In the lexicographic order the6-subset that follows2,3,4,6,9,10is2,3,4,7,8,9and the 6-subset that precedes2,3,4,6,9,10is2,3,4,6,8,10.

29.In the lexicographic order the7-subset that follows1,2,4,6,8,14,15is1,2,4,6,9,10,11 and the7-subset that precedes1,2,4,6,8,14,15is1,2,4,6,8,13,15.

30.In the table below we list the permutations of{1,2,3}according to the lexicographic order of their inversion sequence.

permutation123132************

inversion sequence000010100110200210

Below we similarly list the permutations of{1,2,3,4}.

123412431324142313421432

000000100100011002000210

213421433124412331424132

100010101100111012001210

231424133214421334124312

200020102100211022002210

234124313241423134214321

300030103100311032003210

31.We ?rst generate the 3-subsets of {1,2,3,4,5}in lexicographic order:123,124,125,134,135,145.For each subset we order the elements in all possible ways,using the algorithm from Section 4.1.This yields the following ordering of the 3-permutations of {1,2,3,4,5}.Reading left to right,

123132312321231213124142412421241214125152512521251215134143413431341314135153513531351315145

154

514

541

451

415

32.We ?rst generate the 4-subsets of {1,2,3,4,5,6}in lexicographic order.Reading left to right,

12341235123612451246125613451346135614562345

2346

2356

24563456

For each subset we order the elements in all possible ways,using the algorithm from Section 4.1.This yields an ordering of the 4-permutations of {1,2,3,4,5,6}.We omit the details due to length.

33.By convention the ?rst term in the lexicographical order is position 1.The total number of 4-subsets of {1,2,3,4,5,6,7,8,9}is 94

.We now count the number of 4-subsets that come after 2489in the lexicographical order.A 4-subset comes after 2489if and only if it has the form (i)abcd (3≤a

94 ? 74 ? 53 .34.Consider the lexicographical order of r -subsets for {1,2,...,n }.

(a)The ?rst n ?r +1terms are

1,2,...,r ?1,r,1,2,...,r ?1,r +1,

···

1,2,...,r ?1,n.

(b)The last r +1terms are

n ?r,n ?r +1,...,n ?1,n ?r,n ?r +1,...,n ?2,n,

···

n ?r +1,n ?r +2,...,n ?1,n.

35.Let A and B denote distinct r -subsets of {1,2,...,n }.We show that with respect to lexicographic order,A

36.View X ={1,2,...,n }.(i)There are 2(n 2

)di?erent relations on X .Reason:To construct a relation R on X ,for 1≤x,y ≤n we must decide whether or not xRy .There are n 2choices for (x,y ).The result follows by the multiplication principle.

(ii)There are 2n (n ?1)re?exive relations on X .Reason:To construct a re?exive relation R on X ,for distinct 1≤x,y ≤n we must decide whether or not xRy .There are n (n ?1)choices for (x,y ).The result follows by the multiplication principle.(iii)Abbreviate N = n +12

.There are 2N symmetric (resp.antisymmetric)relations on X .Reason:To construct a symmetric (resp.antisymmetric)relation R on X ,for 1≤x ≤y ≤n we must decide whether or not xRy .There are N choices for (x,y ).The result follows by the multiplication principle.(iv)Abbreviate M = n 2

.There are 2M re?exive symmetric (resp.antisymmetric)relations on X .Reason:To construct a re?exive symmetric (resp.antisymmetric)relation R on X ,for 1≤x

37.Recall that a relation on X is a partial order if and only if it is re?exive,antisymmetric,and transitive.We now show that the relation R has these features.

R is re?exive:For x ∈X we show xRx .The relations R and R are re?exive so xR x and xR x .Therefore xRx .

R is antisymmetric:For distinct x,y ∈X such that xRy ,we show that yRx fails.We assume xRy so xR y .The relation R is antisymmetric so yR x fails.Therefore yRx fails.

R is transitive:For x,y,z ∈X such that xRy and yRz we show xRz .By construction xR y and yR z .The relation R is transitive so xR z .Similarly xR z .Therefore xRz .

38.Recall that a relation on a set is a partial order if and only if it is re?exive,antisymmetric,and transitive.We show that the relation T on the set X 1×X 2has these features.

T is re?exive:For x ∈X 1×X 2we show xT x .Write x =(x 1,x 2).The relation ≤1is re?exive so x 1≤1x 1.Similarly x 2≤2x 2.Therefore xT x .

T is antisymmetric:For distinct x,y ∈X 1×X 2such that xT y ,we show that yT x fails.Write x =(x 1,x 2)and y =(y 1,y 2).Since x,y are distinct,there exists i ∈{1,2}such that x i =y i .Since xT y we have x i ≤i y i .The relation ≤i is antisymmetric so y i ≤i x i .Therefore yT x fails.

T is transitive:For x,y,z ∈X 1×X 2such that xT y and yT z ,we show xT z .Write x =(x 1,x 2)and y =(y 1,y 2)and z =(z 1,z 2).Pick i ∈{1,2}.Since xT y we have x i ≤i y i ,and since yT z we have y i ≤i z i .By this and since ≤i is transitive we ?nd x i ≤i z i .Therefore xT z .39.De?ne the set J n =J ×J ×···×J (n factors).Thus J n consists of the n -tuples of zeros and ones.For x ∈J n and 1≤i ≤n let x i denote the entry in coordinate i of x ,so that x =(x 1,x 2,...,x n ).De?ne a partial order ≤on J n such that for x,y ∈J n ,x ≤y whenever x i ≤y i for 1≤i ≤n .By construction the poset (J n ,≤)is the direct product of n

copies of the poset(J,≤).We show that the poset(J n,≤)can be identi?ed with the poset (P(X),?).View X={1,2,...,n}.De?ne a function f:J n→P(X)by

f(x)={i∈X|x i=1},x∈J n.

The function f is a bijection.We show that for x,y∈J n,x≤y if and only if f(x)?f(y). Let x,y be given and note that the following assertions are equivalent:

(i)x≤y;

(ii)x i≤y i for1≤i≤n;

(iii)x i=1implies y i=1for1≤i≤n;

(iv)i∈f(x)implies i∈f(y)for1≤i≤n;

(v)f(x)?f(y).

We have shown that the poset(J n,≤)can be identi?ed with the poset(P(X),?).

40.For each integer r≥0de?ne a poset[r]as follows.The poset consists of the set {0,1,...,r}together with the total order0<1<···

x={x1·a1,x2·a2,...,x m·a m},0≤x j≤n j(1≤j≤m).

For x,y∈P(X)the following are equivalent:

(i)x?y;

(ii)x j≤y j for1≤j≤m;

(iii)(x1,x2,...,x m)≤(y1,y2,...,y m)in the poset[n1]×[n2]×···×[n m].

Therefore the poset[n1]×[n2]×···×[n m]can be identi?ed with the poset(P(X),?).

41.We show that a partial order≤on a?nite set X is uniquely determined by its cover relation.This is a consequence of the following lemma.

Lemma The following are equivalent for all distinct x,y∈X:

(i)x

(ii)there exists an integer r≥2and a sequence(x1,x2,...,x r)of elements in X such that x=x1and x r=y and x i covers x i?1for2≤i≤r.

Proof:(i)?(ii)Consider the set S consisting of the?nite sequences(x1,x2,...,x r)such that x1=x and x r=y and x i?1

42.The diagram of the cover relation is essentially the n-cube,where n=|X|.

43.The linear extensions are

abecfd,abefcd,aebcfd,aebfcd,abcefd,aefbcd.

44.Recall that a relation is an equivalence relation whenever it is re?exive and symmetric and transitive.We show that R has these features.

R is re?exive:For x∈X,x and x are in the same part of the partition.

R is symmetric:For x,y∈X,x and y are in the same part of the partition if and only if y and x are in the same part of the partition.

R is transitive:For x,y,z∈X,if x,y are in the same part of the partition,and y,z are in the same part of the partition,then x,z are in the same part of the partition.

45.The relation R is an equivalence relation.To verify this,one checks that R is re?exive, symmetric,and transitive.For the equivalence relation R one equivalence class consists of 0.Every other equivalence class consists of a positive integer and its opposite.

46.We show that R is an equivalence relation.

R is re?exive:For an integer a,certainly a and a have the same remainder when divided by m.

R is symmetric:For integers a,b suppose a and b have the same remainder when divided by m.Then b and a have the same remainder when divided by m.

R is transitive:For integers a,b,c suppose a,b have the same remainder when divided by m, and b,c have the same remainder when divided by m.Then a,c have the same remainder when divided by m.We have shown that R is an equivalence relation.The equivalence classes are[0],[1],...,[m?1]where[r]={r+im|i∈Z}for0≤r≤m?1.The relation R has m equivalence classes.

47.(a)It is routinely checked that≤is a partial order onΠn.

(b)Given equivalence relations R and S on{1,2,...,n}we have R≤S whenever xRy implies xSy for all x,y∈{1,2,...,n}.

48.Consider the prime factorizations for a and b:

a=2a13a25a3···b=2b13b25b3···

Then

c=2c13c25c3···d=2d13d25d3···

where c i=min{a i,b i}for i≥1and d i=max{a i,b i}for i≥1.The integer c(resp.d)is the greatest common factor(resp.least common multiple)of a,b.

49.It is routinely checked that R∩S is an equivalence relation.In general R∪S is not an equivalence relation.

50.There are48linear extensions.

51.For a permutationπof{1,2,...,n}let Inv(π)denote the set of inversions ofπ.Letσdenote a permutation of{1,2,...,n}.By de?nitionπ≤σwhenever Inv(π)?Inv(σ).We show that for the partial order≤the following are equivalent:

(i)σcoversπ;

(ii)σis obtained fromπby applying a transposition ab→ba with a

Proof:(i)?(ii)By assumptionπ<σso Inv(π)?Inv(σ).The containment is proper since a permutation is determined by its inversions.Pick an inversion ba(a

π=···a···b···σ=···b···a···

Of all the inversions ba that meet the above requirement,pick one for which the distance betwen the symbols b,a inσis minimal.We show that b,a are adjacent inσ.Suppose that this is not the case.Thenσhas the form

σ=···b···c···a···

By the minimality condition neither of bc and ca is an inversion that is contained in Inv(σ) but not in Inv(π).Consequently inπthe c lies to the left of a and to the right of b.This is a contradiction so c does not exist.We have shown that b,a are adjacent inσ.In other wordsσhas the form

σ=···ba···

Apply the transposition ba→ab toσand let p denote the resulting permutation.Thus

p=···ab···

The set Inv(p)is obtained from Inv(σ)by removing the inversion ba.Consequentlyπ≤p<σ.By assumptionσcoversπsoπ=p.Thereforeπis obtained fromσby applying the transposition ba→ab.Consequentlyσis obtained fromπby applying the transposition ab→ba.

(ii)?(i)The permutationsσandπhave the form

π=···ab···σ=···ba···

with agreement in all coordinates except the two shown.The set Inv(σ)is obtained from Inv(π)by adding the inversion ba.Thus Inv(π)?Inv(σ)soπ≤σ.Also|Inv(σ)|=

|Inv(π)|+1so there does not exist a permutation τsuch that π<τ<σ.Therefore σcovers π.

Before solving problems 52and 53we recall a few points from the text.

Problem B For an integer m ≥0consider the base 2representation of m as a sequence of zeros and ones.(i)Describe how to adjust this sequence to get the corresponding representa-tion of m +1.(ii)For m ≥1,describe how to adjust this sequence to get the corresponding representation of m ?1.

Sol Write the base 2representation of m as ···b 2b 1b 0,so that m = ∞i =0b i 2i

with b i ∈{0,1}for i ≥0.

(i)To get the corresponding representation of m +1we specify which coordinates to change.For i ≥0change b i if and only if each of b 0,b 1,...,b i ?1is 1.Thus b 0always gets changed;b 1gets changed if and only if b 0is 1;b 2gets changed if and only if each of b 0,b 1is 1,and so on.(ii)Assume m ≥1.To get the corresponding representation of m ?1we specify which coordinates to change.For i ≥0change b i if and only if each of b 0,b 1,...,b i ?1is 0.Thus b 0always gets changed;b 1gets changed if and only if b 0is 0;b 2gets changed if and only if each of b 0,b 1is 0,and so on.

Problem G Let ···g 2g 1g 0denote a term in the re?ected Gray code.(i)Describe the next term in the code.(ii)Assume that there exists an integer i ≥0such that g i =1.Describe the preceding term in the code.

Sol (i)We specify which coordinate to change.First assume that ∞

i =0g i is even.Then change g 0.Next assume that ∞

i =0g i is odd.Change g s for the unique integer s ≥1such that g s ?1=1and each of g 0,g 1,...,g s ?2is 0.(ii)First assume that ∞

i =0g i is odd.Then change g 0.Next assume that ∞i =0g i is even.Change g s for the unique integer s ≥1such that g s ?1=1and each of g 0,g 1,...,g s ?2is 0.52.For an integer m ≥0let ···b 2b 1b 0denote the base 2representation of m and let ···g 2g 1g 0denote term m in the re?ected Gray code.We show that for i ≥0,b i =0if g i +g i +1+···is even,and b i =1if g i +g i +1+···is odd.For i ≥0de?ne B i =0if g i +g i +1+···is even,and B i =1if g i +g i +1+···is odd.We show B i =b i .Call the sequence ···B 2B 1B 0the B -sequence for m .For the purpose of this proof call the sequence ···b 2b 1b 0the b -sequence for m .Note that for m =0the B -sequence and b -sequence are both equal to ···000.To ?nish the proof,it su?ces to show that for m ≥0the B -sequence of m +1is related to the B -sequence of m in the same way that the b -sequence of m +1is related to the b -sequence of m .It is explained in Problem B(i)how the b -sequence of m +1is related to the b -sequence of m .Now consider the B -sequences.First assume ∞i =0g i is even,so that B 0=0.By Problem G,term m +1in the re?ected Gray code is obtained from ···g 2g 1g 0by changing g 0.Therefore the B -sequence for m +1is obtained from ···B 2B 1B 0by changing B 0to 1.Next assume ∞

i =0g i is odd,so that B 0=1.Consider the unique integer s ≥1such that g s ?1=1and each of g 0,g 1,...,g s ?2is 0.By construction B s =0and B i =1for 0≤i ≤s ?1.By Problem G,term m +1in the re?ected Gray code is obtained from ···g 2g 1g 0by changing g s .Therefore the B -sequence for m +1is obtained from ···B 2B 1B 0by changing B s to 1and B i to 0for 0≤i ≤s ?1.We have shown that the B -sequence of m +1is related to the

B -sequence of m in the same way that the b -sequence of m +1is related to the b -sequence of m .The result follows.

53.For an integer m ≥0let ···b 2b 1b 0denote the base 2representation of m and let ···g 2g 1g 0denote term m in the re?ected Gray code.We show that for i ≥0,g i =0if b i +b i +1is even and g i =1if b i +b i +1is odd.For i ≥0de?ne G i =0if b i +b i +1is even and G i =1if b i +b i +1is odd.We show G i =g i .Call the sequence ···G 2G 1G 0the G -sequence for m .For the purpose of this proof call the sequence ···g 2g 1g 0the g -sequence for m .Note that for m =0the G -sequence and g -sequence are both equal to ···000.To ?nish the proof,it su?ces to show that for m ≥0the G -sequence of m +1is related to the G -sequence of m in the same way that the g -sequence of m +1is related to the g -sequence of m .It is explained in Problem G(i)how the g -sequence of m +1is related to the g -sequence of m .Now consider the G -sequences.First assume b 0=0,so that ∞i =0G i is even.The base 2representation of m +1is obtained from ···b 2b 1b 0by changing b 0to 1.Therefore the G -sequence of m +1is obtained from ···G 2G 1G 0by changing G 0.Next assume that b 0=1,so that ∞i =0G i is odd.There exists a unique integer s ≥1such that b s =0and b i =1for 0≤i ≤s ?1.By construction G s ?1=1and each of G 0,G 1,...,G s ?2is 0.The base 2representation of m +1is obtained from ···b 2b 1b 0by changing b s to 1and b i to 0for 0≤i ≤s ?1.Therefore the G -sequence of m +1is obtained from ···G 2G 1G 0by changing G s .We have shown that the G -sequence of m +1is related to the G -sequence of m in the same way that the g -sequence of m +1is related to the g -sequence of m .The result follows.

54.We augment the covering relation for ≤by declaring that b covers a .View the augmented covering relation as the covering relation of a new partial order ≤ .The partial order ≤ has a linear extension by Theorem 4.5.2.This linear extension has the desired features.55.This is a routine consequence of 54.

56.It is routine to check that R is a partial order.Assume that i 1i 2···i n is not the identity permutation.We show that R has dimension 2.De?ne a partial order ≤1on X such that (a,b )≤1(c,d )whenever a ≤c .Observe that ≤1is a linear extension of R .De?ne a partial order ≤2on X such that (a,b )≤2(c,d )whenever b ≤d .Observe that ≤2is a linear extension of R .The relation R is the intersection of ≤1and ≤2.Therefore R has dimension at most 2.The partial orders ≤1and ≤2are not identical so R is not a total order;consequently R has dimension at least 2.By these comments R has dimension 2.57.

58.The following are equivalent:(i)the relation is an equivalence relation;(ii)K n is partitioned into complete graphs such that any two distinct vertices of K n are connected by a red edge if and only if they are in the same complete subgraph.

59.Let T denote the total number of inversions for all n !permutations of {1,2,...,n }.Thus T is the number of triples (r,s ;a 1a 2···a n )such that a 1a 2···a n is a permutation of {1,2,...,n }and (r,s )is an inversion of a 1a 2···a n .To count these triples we proceed in stages:

stage to do#choices

1select the values of r,s n 2

2select the location of r,s among a1a2···a n n 2

3choose the remaining n?2terms among a1a2···a n(n?2)!

T is the product of the entries in the right-most column above,which comes to n!n(n?1)/4.

(完整word版)组合数学课后答案

习题二证明：在一个至少有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．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -=+---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!! !! 10 =n C 规定：组合数性质： .2 n n n n n m n m n m n m n n m n C C C C C C C C 21011 =+++=+=+--…… ，， ①；②；③；④ 111 12111212211 r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-++++ +=+++ +=++ +=注：若1 2 m m 1212m =m m +m n n n C C ==则或四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。

组合数学课后答案

作业习题答案习题二 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、元素：我们把问题中被取的对象叫做元素 2、排列：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素各不相同）按照一定的顺．．．．序．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．．．．。说明：（1）排列的定义包括两个方面：①取出元素，②按一定的顺序排列（与位置有关）（2）两个排列相同的条件：①元素完全相同，②元素的排列顺序也相同合作探究二排列数的定义及公式 3、排列数：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个数叫做从n 个元素中取出 m 元素的排列数，用符号m n A 表示议一议：“排列”和“排列数”有什么区别和联系？ 4、排列数公式推导探究：从n 个不同元素中取出2个元素的排列数2n A 是多少？3n A 呢？m A n 呢？ )1()2)(1(+-?--=m n n n n A m n （,,m n N m n *∈≤）说明：公式特征：（1）第一个因数是n ，后面每一个因数比它前面一个少1，最后一个因数是1n m -+，共有m 个因数；（2）,,m n N m n *∈≤ 即学即练: 1.计算 (1）410A ； (2）25A ；(3)3355A A ÷ 2.已知101095m A =???，那么m = 3．,k N +∈且40,k ≤则(50)(51)(52)(79)k k k k ----用排列数符号表示为( ) A ．5079k k A -- B ．2979k A - C ．3079k A - D ．3050k A - 例1．计算从c b a ,,这三个元素中，取出3个元素的排列数，并写出所有的排列。 5 、全排列：n 个不同元素全部取出的一个排列，叫做n 个不同元素的全排列。此时在排列数公式中， m = n 全排列数：(1)(2)21!n n A n n n n =--?=（叫做n 的阶乘）. 即学即练:口答（用阶乘表示）：（1）334A （2）44A （3）)!1(-?n n 排列数公式的另一种形式： )! (!m n n A m n -= 另外，我们规定 0! =1 .

组合数学课后标准答案

组合数学课后标准答案

————————————————————————————————作者：————————————————————————————————日期：

任取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个相同种类的水果。

排列组合典型例题

排列组合典型例题排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。教学目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3.学会应用数学思想和方法解决排列组合问题. 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理）完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.

组合数学题目及标准答案

组合数学例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 h ，使得 ah+1+…+ ak= 39 证令Sj= ，j =1 , 2 , …,100。显然 ∑=j i i a 1 ∑=h i i a 1

高中数学排列组合经典题型全面总结版

高中数学排列与组合（一）典型分类讲解一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有 34A 由分步计数原理得1 1 3 434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有 522522480A A A =种不同的排法练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共有55A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种 46 A 不同的方法,由分步计数原理,节目的不同顺序共有54 56A A 种练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略例4. 7人排队,其中甲乙丙3人顺序一定共有多少不同的排法解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数,则共有不同排法种数是： 73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 47 A 种方法，其余的三个位置甲乙丙共有 1种坐法，则共有4 7A 种方法。思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有方法练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？ 5 10C 五.重排问题求幂策略例5.把6名实习生分配到7个车间实习,共有多少种不同的分法解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原理共有6 7种不同的排法练习题： 1．某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为 42 4 4 3 允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n 不同的元素没有限制地安排在m 个位置上的排列数为n m 种

李凡长版-组合数学课后习题答案-习题3

李凡长版-组合数学课后习题答案-习题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

高中数学排列组合题型总结与易错点提示25587汇编

排列组合复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1 m 种不同的方法，在第2类办法中有2 m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有：12n N m m m =+++种不同的方法． 2.分步计数原理（乘法原理）完成一件事，需要分成n 个步骤，做第1步有1 m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有：12n N m m m =???种不同的方法． 3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有13 C C 1 4 A 3 4 C 1 3 然后排首位共有14 C 最后排其它位置共有34 A 由分步计数原理得113434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花

不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有5225 2 2 480A A A 种不同的排法乙甲丁丙练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共有55 A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种46 A 不同的方法,由分步计数原理,节目的不同顺序共有5456 A A 种练习题：某班新年联欢会原定的5个节目已排成节目单，要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列 ,同时要注意合并元素内部也必须排列. 元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端

高中数学排列组合中的典型例题与分析(三)

排列与组合的八大典型错误、 24种解题技巧三大模型一、知识点归纳二、基本题型讲解三、排列组合解题备忘录 1.分类讨论的思想 2.等价转化的思想 3.容斥原理与计数 4.模型构造思想四、排列组合中的8大典型错误 1．没有理解两个基本原理出错 2.判断不出是排列还是组合出错 3.重复计算出错 4.遗漏计算出错 5.忽视题设条件出错 6.未考虑特殊情况出错 7．题意的理解偏差出错 8.解题策略的选择不当出错五、排列组合24种解题技巧 1．排序问题相邻问题捆绑法相离问题插空排定序问题缩倍法（插空法）定位问题优先法多排问题单排法圆排问题单排法可重复的排列求幂法全错位排列问题公式法 2．分组分配问题平均分堆问题去除重复法（平均分配问题）相同物品分配的隔板法全员分配问题分组法有序分配问题逐分法 3．排列组合中的解题技巧至多至少间接法染色问题合并单元格法交叉问题容斥原理法构造递推数列法六．排列组合中的基本模型分组模型（分堆模型）错排模型染色问题

七．排列组合问题经典题型与通用方法（一）排序问题 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列.例1.,,,,A B C D E 五人并排站成一排，如果,A B 必须相邻且B 在A 的右边，则不同的排法有（）A、60种 B、48种 C、36种 D、24种解析：把,A B 视为一人，且B 固定在A 的右边，则本题相当于4人的全排列，4 424A =种，答案：D . 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（）A、1440种B、3600种C、4820种D、4800种解析：除甲乙外，其余5个排列数为5 5A 种，再用甲乙去插6个空位有2 6A 种，不同的排法种数是5 2 563600A A =种，选B . 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法. 例3.A,B,C,D,E 五人并排站成一排，如果B 必须站在A 的右边（,A B 可以不相邻）那么不同的排法有（）A、24种B、60种C、90种D、120种解析：B 在A 的右边与B 在A 的左边排法数相同，所以题设的排法只是5个元素全排列数的一半，即 5 51602 A =种，选 B .11.定位问题优先法：某个或几个元素要排在指定位置，可先排这个或几个元素；再排其它的元素。例11.现有1名老师和4名获奖同学排成一排照相留念，若老师不站两端则有不同的排法有多少种？解析：老师在中间三个位置上选一个有1 3A 种，4名同学在其余4个位置上有4 4A 种方法；所以共有1 4 3472A A =种。 12.多排问题单排法:把元素排成几排的问题可归结为一排考虑，再分段处理。例12.（1）6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数是（）A、36种B、120种C、720种D、1440种（2）8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？解析：（1）前后两排可看成一排的两段，因此本题可看成6个不同的元素排成一排，共 66720A =种，选C . （2）解析：看成一排，某2个元素在前半段四个位置中选排2个，有2 4A 种，某1个元素排在后半段的四个位置中选一个有1 4A 种，其余5个元素任排5个位置上有5 5A 种，故共有1 2 5 4455760A A A =种排法. 16.圆排问题单排法:把n 个不同元素放在圆周n 个无编号位置上的排列，顺序（例如按顺时钟）不同的排法才算不同的排列，而顺序相同（即旋转一下就可以重合）的排法认为是相同的，它与普通排列的区别在于只计顺序而无首位、末位之分，下列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个相同种类的水果。

排列组合计算公式及经典例题汇总

排列组合公式/排列组合计算公式排列A------和顺序有关组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列" 把5本书分给3个人,有几种分法"组合" 1．排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)表示. A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1). 2．组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n 个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号

c(n,m) 表示. c(n,m)=A(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m); 3．其他排列与组合公式从n个元素中取出r个元素的循环排列数＝A(n,r)/r=n!/r(n-r)!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/(n1!*n2!*...*nk!). k类元素,每类的个数无限,从中取出m个元素的组合数为 c(m+k-1,m). 排列（Anm(n为下标，m为上标)） Anm=n×（n-1）....（n-m+1）；Anm=n！/（n-m）！（注：！是阶乘符号）；Ann（两个n分别为上标和下标）=n！；0！=1；An1（n为下标1为上标）=n

高考数学排列组合与概率知识点排列组合典型题基本方法技巧

排列组合与概率经典教案两个基本原理： 1.加法原理（分类计数原理）:做一件事,完成它有n 类办法,在第一类办法中有1m 种不同的方法, 在第二类办法中有2m 种不同的方法, ……,在第n 类办法中有n m 种不同的方法,那么完成这件事共有：n m m m m N +???+++=321种不同的方法. 2.乘法原理（分步计数原理）: 做一件事,完成它有n 个步骤,做第一步有1m 种不同的方法, 做第二步有有2m 种不同的方法, ……, 做第n 步有n m 种不同的方法,那么完成这件事共有： n m m m m N ???????=321种不同的方法. 特别注意：分类是独立的、一次性的；分步是连续的、多次的。三组基本概念： 1．排列 1）排列：从n 个不同元素中取出m(m ≤n)个元素,按照一定的顺序排成一列,叫做从n 个不同元素中取出m 个元素的一个排列。 2）排列数：从n 个不同元素中取出m(m ≤n)个元素的所有排列的个数,叫做从n 个不同元素中取出m 个元素的排列数。通常用m n A 表示。特别地，当n m =时，称为全排列，当n m π时，称为选排列。 2．组合 1）组合：从n 个不同元素中取出m(m ≤n)个元素并成一组,叫做从n 个不同元素中取出m 个元素的一个组合。 2）组合数：从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数,叫做从n 个不同元素中取出m 个元素的组合数,记作m n C 。 3．事件与概率 1）事件的分类：（1）必然事件：在一定的条件下必然要发生的事件；（2）不可能事件：在一定的条件下不可能发生的事件；（3）随机事件：在一定的条件下可能发生也可能不发生的事件。 2）一些特殊事件：（1）等可能事件：对于每次随机试验来说，只可能出现有限个不同的试验结果；另外，所有不同的试验结果，它们出现的可能性是相等的。（2）互斥事件：不可能同时发生的两个事件，我们把它称为互斥事件。如果事件A 1，A 2，…，A n 中的任何两个都是互斥事件，那么就说事件A 1，A 2，…，A n 彼此互斥。（3）对立事件：必有一个发生的两个互斥事件叫做对立事件。事件A 的对立事件通常记作 A 。特别地，有 B A +、B A ?的对立事件分别是B A ?、B A +，即B A B A ?=+、B A B A +=?。（4）相互独立事件：一个事件是否发生对另一个事件发生的概率没有影响的两个事件叫做相互独立事件。 3）事件的概率：在大量重复进行同一试验时，事件A 发生的频率n m 总是接近于某个常数，在它附近摆动，这时就把这个常数叫做事件A 的概率，记作P (A )。一些重要公式： 1．排列数公式： )! (! )1()2)(1(m n n m n n n n A m n -=+-???--= 这里*,N m n ∈,且n m ≤。

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.doczj.com/doc/d31541527.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.doczj.com/doc/d31541527.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.doczj.com/doc/d31541527.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 除尽。

相关主题

组合数学答案

组合数学参考答案

组合体答案

组合数学第五版

组合数学第五讲

数学排列组合典型例题

文本预览

相关文档

吉林大学组合数学习题解答

排列组合练习题与答案

组合数学题库答案

组合数学答案合集

组合数学课后答案

组合数学函授试题答案

组合数学课后答案

《组合数学》第五版第6章答案.pdf

组合数学题目及标准答案

组合数学题库答案

组合数学课后答案 PDF 版

组合数学课后标准答案

组合数学第一章作业答案

组合数学习题答案卢开澄

最新整理组合数学课后答案word版本

组合数学第四版卢开澄标准答案-第四章

组合数学课后答案

组合数学答案

组合数学作业答案1-2章2016

组合数学答案

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)

文档之家

Richard组合数学第5版-第4章课后习题答案(英文版)

(完整word版)组合数学课后答案

排列组合知识点总结+典型例题及答案解析

组合数学课后答案

高中数学排列组合典型例题精讲

组合数学课后标准答案

排列组合典型例题

组合数学题目及标准答案

高中数学排列组合经典题型全面总结版

李凡长版-组合数学课后习题答案-习题3

高中数学排列组合题型总结与易错点提示25587汇编

高中数学排列组合中的典型例题与分析(三)

组合数学 课后答案

排列组合计算公式及经典例题汇总

最新排列组合知识点汇总及典型例题(全)

高考数学 排列组合与概率知识点 排列组合典型题 基本方法 技巧

Richard组合数学第5版-第5章课后习题答案(英文版)

组合数学参考答案(卢开澄第四版) - 修改版

组合数学课后答案

高考数学排列组合与概率知识点排列组合典型题基本方法技巧