›
›

Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 6: Counting

Download
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH  
TRƯỜNG ĐẠI HỌC BÁCH KHOA  
KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH  
CẤU TRÚC RỜI RẠC CHO KHMT (CO1007)  
Nhóm:18-TDTT —- Homework  
CHAPTER 6  
Counting  
GVHD: Nguyễn An Khương  
SV thực hiện: Đinh Minh Tân – 1613074  
Trương Minh Tiến – 1613544  
Vũ Đào Anh Tuấn – 1613938  
Nguyễn Thị Trà My – 51305086  
Tp. Hồ Chí Minh, Tháng 11/2016  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
Exercise 2.  
a) 410  
10  
P
b)  
4i.C(10, 10 − i)  
i=1  
Exercise 3.  
a) The numbers are divisible by 7 have form 7k where k is integer. Because it is from 100 to 999,  
so we have 100 ≤ 7k ≤ 999 ⇒ 15 ≤ k ≤ 142, thus we have 128 numbers are satisfied.  
b) Similar to a), we have 450 numbers are odd  
c) There are 9 number have the same three decimal digits  
d) Similar, we have 225 numbers are divisible by 4. Because from 100 to 999 have 900 numbers,  
thus we have 900-225=675 numbers aren’t divisible by 4  
e) Similar, we have 300 numbers are divisible by 3 and 75 numbers are divisible by 12, follow d),  
we have 225 number are divisible by 4, thus we have 225+300-75=450 numbers are satisfied  
f) There are 900-450=450 numbers are satisfied  
g) There are 300-75=225 numbers are satisfied  
h) There are 75 numbers are satisfied  
Exercise 4.  
a) C11.C95.6!  
b) C11.C84.6!  
c) C21.C85.6!  
Exercise 5.  
a) 2!.C84.5!  
b) C84.6! − 2!.C84.5!  
c) C61.C51.C84.4!  
Exercise 6.  
a) 27 + 28 − 25  
Exercise 7.  
a) 25.C61 + 25.C61 − 2  
Chương 6: Homework  
Trang 1/3  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
Exercise 8.  
12  
P
a)  
68i  
i=8  
 
!
6
12  
P
P
b)  
C6i.i!  
Cpi .62p−i  
i=1  
p=8  
ꢀ
ꢁ
12  
P
68i .10−9  
i=8  
c) There are  
≈ 314582 years.  
365.24.60.60  
Exercise 9.  
a) There are 5  
b) There are 13  
Exercise 10.  
Because we have 4 numbers, but there are 3 remainder of 3 is 0, 1, 2, so we have two numbers  
are same remainder. Thus their difference is divisible by 3.  
Exercise 11.  
a) 210 = 1024  
b) C120 = 45  
c) C130 + C120 + C110 + C100 = 176  
d) C150 = 252  
Exercise 12.  
a) C120 + C140 + C160 + C180 + C + C100 = 512  
10  
10  
b) C150 = 252  
Exercise 13.  
First position the men relative to each other. Since there are eight men, there are 8! ways to do  
this.Then, there are nine slots where five womens can stand. So there are P95 ways. Thus we are  
8!P95 = 609638400 ways.  
Exercise 14.  
a) C87+6−1 = 1716  
b) C87+12−1 = 50388  
c) C87+24−1 = 2629575  
d) We solve the equation a1 + a2 + ... + a8 = 12 subject to the constraint that each ai ≥ 1.Let  
bi = ai − 1 so bi ≥ 0. So, b1 + b2 + ... + b8 = 4. Thus, they are C87+4−1 = 330 ways.  
Chương 6: Homework  
Trang 2/3  
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh  
Khoa Khoa Học và Kỹ Thuật Máy Tính  
e) We solve the equation a1 + a2 + ... + a8 = 12 subject to the constraint that each a1 ≥ 3 and  
a2 ≤ 2. As in part (d),There are C172−3+8−1 − C172−3−3+8−1 = 9724 ways.  
Exercise 15.  
14!  
There are  
= 302702400 ways.  
3!3!2!2!2!  
Exercise 16.  
a) There are two arrangements: 3-1-1 and 2-2-1  
First, 3-1-1 arrangement: There are 3 ways to choose the crowded box, C53 ways to choose  
ball to put there, 2 ways to choose box to put two other balls.So there are C53.3.2 = 90  
Second, 1-2-2 arrangement: There are C32 ways to choose two boxs,which have two balls,C52  
to choose ball to put the first box, and C32 to choose two ball to put the second box. So, there  
are C32C52C32 = 90  
Thus, there are 90 + 60 = 150 ways  
b) There are two arrangements: 3-1-1 and 2-2-1  
First, 3-1-1 arrangement: There are C53 ways to choose three balls to put the crowded box.So  
we have 10 ways.  
Second, 2-2-1 arrangement: There are 5 ways to choose one ball to put the box,which has 1  
C42  
ball,  
= 3 ways to distribute 4 ball into two remaining boxs.So we have 5.3 = 15 ways.  
2
Thus, We have 15 + 10 = 25 ways.  
Exercise 17.  
a) C110C91C81C71 = 5040  
b) C51.10.10.10 = 5000  
c) C43.9 = 36  
Exercise 18.  
7!  
There are  
= 210  
3!2!2!  
Exercise 19.  
a) As in part (d),Ex.14,there are C73 = 35  
b) We introduce an auxiliary variable x4 such that x1 + x2 + x3 + x4 = 11.  
There are C134 = 364.  
Chương 6: Homework  
Trang 3/3  
 
pdf 4 trang baolam 19060 Free
Download
Bạn đang xem tài liệu "Tài liệu Cấu trúc rời rạc cho khoa học máy tính - Chapter 6: Counting", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdftai_lieu_cau_truc_roi_rac_cho_khoa_hoc_may_tinh_chapter_6_co.pdf