intTypePromotion=1
ADSENSE

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

1.196
lượt xem
290
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ủ đề:
Lưu

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

  1. 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ị).
  2. 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ị)     
  3. 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.
  4. 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.
  5. 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.
  6. 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
  7. 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ị)
  8. 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.
  9. 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,t­1). Vậy số tổ hợp lặp chập k từ t phần tử của X là C(k+t­1,t­1).  Theo tính chất tổ hợp:   C(k+t­1,t­1)=C(k+t­1,k).
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2