Tóm tắt nội dung tài liệu
- Bài 11:Có bao nhiêu hoán vị của các chữ Bài cái trong xâu ABCDEF mà trong đó có chứa xâu con DEF? Giải: Coi xâu con DEF là một chữ cái [S] thì số hoán vị cần tìm là số hoán vị của xâu bốn chữ cái ABCS. Vậy số hoán vị của các chữ cái trong xâu ABCDEF là: 4!=24 [hoán vị].
- Bài 12:Có bao nhiêu hoán vị của các chữ Bài cái trong xâu ABCDEF mà trong đó có chứa ba chữ cái D,E,F đứng cạnh nhau? Giải: Để 3 chữ cái D,E,F đứng cạnh nhau thì trong mỗi hoán vị cần tìm phải chứa 1 hoán vị của các chữ cái của xâu DEF. Số hoán vị của xâu con DEF là:3!=6 [hv]. Coi các hoán vị của xâu DEF là các chữ cái S1,S2,S3,S4,S5,S6.Khi đó ứng với mỗi chữ cái Si,số hoán vị của các chữ cái của xâu 4 chữ cái ABC[Si] là 4! =24[hoán vị]. Do vai trò của các Si như nhau nên theo nguyên lý nhân,số hoán vị của các chữ cái trong xâu ABCDEF mà trong đó có chứa ba chữ cái D,E,F đứng cạnh nhau là: 3!× 4!=144[hoán vị]
- Bài 13:Có bao nhiêu cách xếp 6 người vào Bài ngồi quanh cái bàn tròn [hai cách xếp không coi là khác nhau nếu chúng có thể thu được từ nhau bởi phép quay bàn tròn]? Giải: Nếu xếp 6 người ngồi vào một cái bàn thẳng thì sẽ có 6!=720 cách xếp. Do xếp vào cái bàn tròn nên một cách xếp sẽ được tính thành 6 lần bởi phép quay bàn tròn nên số cách xếp 6 người vào ngồi quanh cái bàn tròn là: 720/6=120 cách xếp.
- Bài 14:Có bao nhiêu cách xếp 7 học sinh nam và 5 Bài học sinh nữ ra thành một hàng ngang sao cho không có hai nữ sinh nào đứng cạnh nhau? Giải: Đầu tiên xếp 7 học sinh nam trước.Số cách xếp là:7!=5040 cách xếp. Xếp chỗ cho 5 học sinh nữ. Có 8 vị trí để xếp 5 học sinh nữ sao cho không có 2 học sinh nữ nào đứng cạnh nhau là:6 vị trí xen giữa 2 bạn nam,1 vị trí đầu hàng và 1 vị trí cuối hàng. =>Số cách xếp 5 bàn nữ vào 8 vị trí là: A[8,5]=6720 cách. Vậy theo nguyên lý nhân,số cách xếp 7 học sinh nam và 5 học sinh nữ đứng thành hàng ngang sao cho không có 2 học sinh nữ đứng cạnh nhau là: 5040x6720=33868800 cách xếp.
- Bài 15:Có bao nhiêu xâu nhị phân độ Bài dài 32 mà trong đó có đúng 6 số 1? Giải: Xâu nhị phân độ dài 32 trong đó có đúng 6 số 1=>bài toán tương đương với việc sắp xếp 6 chữ số 1 vào 32 vị trí và không xét đến thứ tự. Vậy số xâu nhị phân thoả mãn: C[32,6]=906192.
- Bài 16:Có bao nhiêu xâu ký tự có thể tạo Bài được từ các chữ cái: MISSISSIPPI? Giải: Xâu ký tự tạo thành có: 4 chữ S 4 chữ I 2 chữ P 1 chữ M Có C[11,4] cách chọn vị trí cho chữ S,còn lại 7 vị trí. Có C[7,4] cách chọn vị trí cho chữ I,còn lại 3 vị trí. Có C[3,2] cách chọn vị trí cho chữ P,còn lại 1 vị trí. Có 1 cách chọn vị trí cho chữ M. Vậy số xâu ký tự thoả mãn: C[11,4].C[7,4].C[3,2].1=11!/[4!4!2!]=34650
- Một cách giải khác Xâu MISSISSIPPI bao gồm 4 chữ cái S,4 chữ cái I,2 chữ cái P,1 chữ cái M. Coi xâu trên được tạo thành từ 11 chữ cái khác nhau.Khi đó số hoán vị được tạo thành là 11! Xét 4 chữ cái S.Do các chữ cái giống nhau nên khi hoán vị các chữ cái S cho nhau xâu thu được ko đổi. =>Có 4! xâu giống nhau. Tương tự số xâu giống nhau khi hoán vị 4 chữ cái I là 4! và khi hoán vị 2 chữ cái P là 2! Vậy số hoán vị của các chữ cái trong xâu MISSISSIPPI là 11!/[4!4!2!]=34650[hoán vị]
- Bài 17:Có 8 cuốn sách khác nhau.Hỏi có bao nhiêu Bài cách phân các cuốn sách này cho 3 học sinh:Mơ,Mai,Mận sao cho Mơ nhận được 4 cuốn còn Mai và Mận mỗi người nhận 2 cuốn? Giải: Số sách của Mơ là 4 cuốn trong số 8 cuốn=>số cách chia sách cho Mơ là C[8,4]. Tương tự số cách chia sách cho Mai là C[4,2]. Số cách chia sách cho Mận là C[2,2]. Vậy số cách chia sách cho 3 bạn: C[8,4].C[4,2].C[2,2]=420.
- Bài 18:Giả sử X là tập t phần tử.Ta gọi tổ hợp lặp chập k từ t phần tử của X là Bài 1 bộ không có tứ tự gồm k thành phần lấy từ các phần tử của X. Ví dụ:X={a,b,c},các tổ hợp lặp chập 2 từ các phần tử của X là [a a],[a b],[a c],[b b],[b c],[c c]. Chứng minh rằng số tổ hợp lặp chập k từ t là: C[k+t-1,t-1]=C[k+t-1,k] Giải: Đánh số lần lượt t phần tử của X là i với 1≤ i ≤ t Gọi là số lần xuất hiện của phần tử thứ i trong tập k phần tử lấy từ tập X. Xi Vậy ta có: [Với , ]. Đây là bài toá1n chia tiề+ X t = kng tiền chia cho t ≤ ia trẻ] với số cách là C[k+t X i ≥ 0 1 đứ ≤ t X + X 2 + ... n [k đồ 1,t1]. Vậy số tổ hợp lặp chập k từ t phần tử của X là C[k+t1,t1]. Theo tính chất tổ hợp: C[k+t1,t1]=C[k+t1,k].
Page 2
YOMEDIA
Tham khảo tài liệu 'bài tập toán rời rạc 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
27-05-2011 1255 290
Download
Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.
Đã gửi 22-10-2012 - 08:42
dãy [x1,x2,....,x10] trong đó mỗi giá trị x chỉ nhận giá trị 0 hoặc 1 gọi là dãy nhị phân 10 bit. Có bao nhiêu dãy nhị phân 10 bit mà trong đó có ít nhất 3 kí tự 0 và 3 kí tự 1.
Đã gửi 22-10-2012 - 14:03
Phân tích logic một chút cho bạn dễ hình dung: $\left|\overline{\text{ít nhất 3 kí tự 0 và 3 kí tự 1}}\right|=\left|\text{Nhiều nhất 2 kí tự 0}\right|+\left|\text{Nhiều nhất 2 kí tự 1}\right|=\left|\text{Đúng 0 kí tự 0}\right|+\left|\text{Đúng 1 kí tự 0}\right|+\left|\text{Đúng 2 kí tự 0}\right|+\left|\text{Đúng 0 kí tự 1}\right|+\left|\text{Đúng 1 kí tự 1}\right|+\left|\text{Đúng 2 kí tự 1}\right|$ Suy ra $\left|\text{ít nhất 3 kí tự 0 và 3 kí tự 1}\right|=\left|\text{tổng số xâu}\right|-\left|\text{Đúng 0 kí tự 0}\right|-\left|\text{Đúng 1 kí tự 0}\right|-\left|\text{Đúng 2 kí tự 0}\right|-\left|\text{Đúng 0 kí tự 1}\right|-\left|\text{Đúng 1 kí tự 1}\right|-\left|\text{Đúng 2 kí tự 1}\right|$ Ta có: Tổng số xâu nhị phân $10$ bit là $2^{10}=1024$ xâu Đúng 0 kí tự 0 có: $1$ xâu Đúng 0 kí tự 1 có: $1$ xâu Đúng 1 kí tự 0 có: $C_{10}^1=10$ xâu Đúng 1 kí tự 1 có: $C_{10}^1=10$ xâu Đúng 2 kí tự 0 có: $C_{10}^2=45$ xâu Đúng 2 kí tự 1 có: $C_{10}^2=45$ xâu Vậy số xâu nhị phân $10$ bit có ít nhất 3 kí tự 0 và 3 kí tự 1 là $1024-1-1-10-10-45-45=912$ xâu
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!
Đã gửi 22-10-2012 - 19:51
Cách 2: Xét các xâu nhị phân độ dài 10 |Có ít nhất 3 vị trí 0 và 3 vị trí 1| = |Có đúng 3 vị trí 0 và 7 vị trí 1|+|Có đúng 4 vị trí 0 và 6 vị trí 1|+|Có đúng 5 vị trí 0 và 5 vị trí 1|+|Có đúng 6 vị trí 0 và 4 vị trí 1|+|Có đúng 7 vị trí 0 và 3 vị trí 1| Như vậy tổng số xâu thoả mãn là $C_{10}^3+C_{10}^4+C_{10}^5+C_{10}^6+C_{10}^7=120+210+252+210+120=912$ xâu
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!
Đã gửi 23-10-2012 - 08:44
Mình đưa bài này lên k phải là vì k giải dc nhưng mình có cách giải như thế này k bik sai chỗ nào nhưng k ra kq là 912 xâu bạn coi giúp mình nhékta có 10C3 cách chọn 3 vị trí để điền 3 chữ số 0sau đó có 7C3 cách chọn 3 vị trí để điền 3 chữ số 1Phân tích logic một chút cho bạn dễ hình dung:$\left|\overline{\text{ít nhất 3 kí tự 0 và 3 kí tự 1}}\right|=\left|\text{Nhiều nhất 2 kí tự 0}\right|+\left|\text{Nhiều nhất 2 kí tự 1}\right|=\left|\text{Đúng 0 kí tự 0}\right|+\left|\text{Đúng 1 kí tự 0}\right|+\left|\text{Đúng 2 kí tự 0}\right|+\left|\text{Đúng 0 kí tự 1}\right|+\left|\text{Đúng 1 kí tự 1}\right|+\left|\text{Đúng 2 kí tự 1}\right|$Suy ra$\left|\text{ít nhất 3 kí tự 0 và 3 kí tự 1}\right|=\left|\text{tổng số xâu}\right|-\left|\text{Đúng 0 kí tự 0}\right|-\left|\text{Đúng 1 kí tự 0}\right|-\left|\text{Đúng 2 kí tự 0}\right|-\left|\text{Đúng 0 kí tự 1}\right|-\left|\text{Đúng 1 kí tự 1}\right|-\left|\text{Đúng 2 kí tự 1}\right|$Ta có: Tổng số xâu nhị phân $10$ bit là $2^{10}=1024$ xâuĐúng 0 kí tự 0 có: $1$ xâuĐúng 0 kí tự 1 có: $1$ xâuĐúng 1 kí tự 0 có: $C_{10}^1=10$ xâuĐúng 1 kí tự 1 có: $C_{10}^1=10$ xâuĐúng 2 kí tự 0 có: $C_{10}^2=45$ xâuĐúng 2 kí tự 1 có: $C_{10}^2=45$ xâuVậy số xâu nhị phân $10$ bit có ít nhất 3 kí tự 0 và 3 kí tự 1 là$1024-1-1-10-10-45-45=912$ xâu
còn lại 4 vị trí, mỗi vị trí trong 4 vị trí này có 2 cách để điền số có thể điền 0 hoặc điền 1 nên có 24 cách điền
vậy số xâu cần tìm là 10C3 . 7C3 . 24 = 67200 xâu kết quả này hình như sai nhưng mình k hiểu tại sao lại sai giúp mình với
Đã gửi 23-10-2012 - 08:51
Bạn sai là bởi vì vi phạm quy tắc nhân: "các hành động chọn phải độc lập với nhau"
Ở hành động thứ nhất bạn "chọn vị trí để viết số 0"
độc lập vớiHành động thứ hai bạn "chọn vị trí để viết số 1"
Nếu muốn hành động thứ 3 độc lập với 2 hành động trên thìHành động thứ ba bạn phải "chọn vị trí để viết số khác 0 và khác 1"
Tất nhiên điều này là không thể !!!Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!
Đã gửi 23-10-2012 - 11:14
thật là khó hiểu ghê!!! Tự nhiên mình sai bài ni hix hix. Cảm ơn bạn nhiều nha!!