Bài tập toán rời rạc 3

Chia sẻ: Nguyen Doan Minh Tri | Ngày: | Loại File: PPT | Số trang:9

Thêm vào BST

Báo xấu

1.553
lượt xem 292
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập toán rời rạc 3

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).