Bài tập toán rời rạc 3
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ả
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:
CoixâuconDEFlàmộtchữcái(S)thìsố
hoánvịcầntìmlàsốhoánvịcủaxâubốn
chữcáiABCS.
Vậysốhoánvịcủacácchữcáitrongxâu
ABCDEFlà:4!=24(hoánvị).
- 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:
Để3chữcáiD,E,Fđứngcạnhnhauthìtrongmỗihoán
vịcầntìmphảichứa1hoánvịcủacácchữcáicủaxâu
DEF.
SốhoánvịcủaxâuconDEFlà:3!=6(hv).
CoicáchoánvịcủaxâuDEFlàcácchữcái
S1,S2,S3,S4,S5,S6.KhiđóứngvớimỗichữcáiSi,số
hoánvịcủacácchữcáicủaxâu4chữcáiABC(Si)là4!
=24(hoánvị).
DovaitròcủacácSinhưnhaunêntheonguyênlý
nhân,sốhoánvịcủacácchữcáitrongxâuABCDEFmà
trongđócóchứabachữcáiD,E,Fđứngcạnhnhaulà:
3!× 4!=144(hoánvị)
- 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ếuxếp6ngườingồivàomộtcáibàn
thẳngthìsẽcó6!=720cáchxếp.
Doxếpvàocáibàntrònnênmộtcáchxếp
sẽđượctínhthành6lầnbởiphépquay
bàntrònnênsốcáchxếp6ngườivàongồi
quanhcáibàntrònlà:720/6=120cá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:
Đầutiênxếp7họcsinhnamtrước.Sốcáchxếplà:7!=5040cách
xếp.
Xếpchỗcho5họcsinhnữ.
Có8vịtríđểxếp5họcsinhnữsaochokhôngcó2họcsinhnữnào
đứngcạnhnhaulà:6vịtríxengiữa2bạnnam,1vịtríđầuhàngvà1
vịtrícuốihàng.
=>Sốcáchxếp5bànnữvào8vịtrílà:A(8,5)=6720cách.
Vậytheonguyênlýnhân,sốcáchxếp7họcsinhnamvà5họcsinh
nữđứngthànhhàngngangsaochokhôngcó2họcsinhnữđứng
cạnhnhaulà:
5040x6720=33868800cáchxế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âunhịphânđộdài32trongđócóđúng6
số1=>bàitoántươngđươngvớiviệcsắp
xếp6chữsố1vào32vịtrívàkhôngxét
đếnthứtự.
Vậysốxâunhịphânthoả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âukýtựtạothànhcó:
4chữS
4chữI
2chữP
1chữM
CóC(11,4)cáchchọnvịtríchochữS,cònlại7vịtrí.
CóC(7,4)cáchchọnvịtríchochữI,cònlại3vịtrí.
CóC(3,2)cáchchọnvịtríchochữP,cònlại1vịtrí.
Có1cáchchọnvịtríchochữM.
Vậysốxâuký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âuMISSISSIPPIbaogồm4chữcáiS,4chữcáiI,2chữ
cáiP,1chữcáiM.
Coixâutrênđượctạothànhtừ11chữcáikhácnhau.Khi
đósốhoánvịđượctạothànhlà11!
Xét4chữcáiS.Docácchữcáigiốngnhaunênkhihoán
vịcácchữcáiSchonhauxâuthuđượckođổi.
=>Có4!xâugiốngnhau.
Tươngtựsốxâugiốngnhaukhihoánvị4chữcáiIlà4!
vàkhihoánvị2chữcáiPlà2!
VậysốhoánvịcủacácchữcáitrongxâuMISSISSIPPI
là11!/(4!4!2!)=34650(hoánvị)
- 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áchcủaMơlà4cuốntrongsố8cuốn=>số
cáchchiasáchchoMơlàC(8,4).
TươngtựsốcáchchiasáchchoMailàC(4,2).
SốcáchchiasáchchoMậnlàC(2,2).
Vậysốcáchchiasáchcho3bạ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:
ĐánhsốlầnlượttphầntửcủaXlàivới 1 i t
GọilàsốlầnxuấthiệncủaphầntửthứitrongtậpkphầntửlấytừtậpX.
Xi
Vậytacó: (Với , ).
Đâylàbàitoá1nchiatiề+ X t = kngtiềnchiachot iatrẻ)vớisốcáchlàC(k+t
X i 0 1 đứ t
X + X 2 + ... n(kđồ
1,t1).
VậysốtổhợplặpchậpktừtphầntửcủaXlàC(k+t1,t1).
Theotínhchấttổhợp:
C(k+t1,t1)=C(k+t1,k).
|