Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

JUN  27  2022  MATH  175

Assignment  1

Definition.  We denote by  (r(n)) the number of r -subsets of an n- element set.  Moreover,

Ç  år(n) =  .

Example  (Page  60  #11).  How  many  sets  of three  integers  between  1  and  20  are  possible  if no  two consecutive integers are to be in a set.

Solution.  First, there are (3(20)) =  = 1140 sets of three integers between 1 and 20. Then, we compute

{1, 2}:  {1, 2, 3}, {1, 2, 4}, · · · , {1, 2, 20} ⇒ 18 ways.

{2, 3}:  {2, 3, 4}, {2, 3, 5}, · · · , {2, 3, 20} ⇒ 17 ways.

{3, 4}:  {1, 3, 4}, {3, 4, 5}, · · · , {3, 4, 20} ⇒ 17 ways.

{18, 19}...:  {1, 18, 19}, {2, 18, 19}, · · · , {16, 18, 19}, {18, 19, 20} ⇒ 17 ways.

{19, 20}:  {1, 19, 20}, {2, 19, 20}, · · · , {17, 19, 20} ⇒ 17 ways.

In total, there are  18 + 18 × 17 = 324 cases.  By exclude these case, there are  1140 − 324 sets of three

integers between 1 and 20 are possible if no two consecutive integers are to be in a set.                             □

Example  (Page 60 #18).  In  how  many  ways  can  two  red and four blue  rooks  be placed  on  an 8- by-8 board so that no two rooks can attack one another?

Solution.  First, we consider the ways such that 6 different rooks be placed so that no two rooks can attack one another, then we divide this number by the repetitions 2! · 4! = 48. The repetitions come from treating the two red rooks are the same and the four blue rooks are the same.

Then, we have the following observation, the position of a rook will tell you which column and row this rook is on.  Since rook attacks in a straight line either horizontally or vertically, if no two rooks can attack on one another, then no two rooks will be on the same row nor the same column.  So each rook will be on a unique column and a unique row.  To place these 6 rooks, we are picking 6 columns from 8 columns and 6 rows from 8 rows.  For the first rook, there are 8 × 8 possibilities, then for the second rook, there are 7 × 7 possibilities, etc. In summary, there are

8 × 8 × 7 × 7 × · · · × 3 × 3 = 406425600

ways if you have 6 different rooks.  By dividing the repetitions 48, there are 8467200 ways that two red

and four blue rooks are placed on an 8-by-8 board so that no two rooks can attack one another.            □