Lý thuyết Toán rời rạc

Chia sẻ: Dinh Tuan | Ngày: | Loại File: PDF | Số trang:216

Thêm vào BST

Báo xấu

177
lượt xem 17
download

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

Toán học rời rạc là một bộ phận của Toán học nhằm nghiên cứu các đối tượng rời rạc: Nghiên cứu các cấu trúc rời rạc khác nhau và các phương pháp giải các vấn đề có liên quan đến các cấu trúc này. Để tìm hiểu sâu hơn về vấn đề này mời các bạn tham khảo Tài liệu Toán rời rạc của tác giả Phạm Tiến Sơn.

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết Toán rời rạc

TOAN `.I RA ´ RO .C Pha.m Tiˆe´n So.n - `a La.t, 2005 D
2
Mu.c lu.c ˙’. D MO -` AˆU 6 ´ D 1 PHEP ˆ´M -E 9 1.1 y co. ba˙’n cu˙’a ph´ep d¯ˆe´m . . . . . . . . . . . . . . . . . . . . . . C´ac nguyˆen l´ 9 1.1.1 y tˆo˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nguyˆen l´ 9 1.1.2 Nguyˆen l´ y t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.3 Nguyˆen l´ u. . . . . . . . . . . . . . . . . . . . . . . . y bao h`am-loa.i tr` 13 1.2 Ho´an vi. v`a tˆo˙’ ho..p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3 C´ac thuˆa.t to´an sinh ra ho´an vi. v`a tˆo˙’ ho..p . . . . . . . . . . . . . . . . . . . . 20 1.4 Ho´an vi. v`a tˆo˙’ ho..p suy rˆo.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5 u.c v`a c´ac d¯`oˆng nhˆa´t th´ C´ac hˆe. sˆo´ nhi. th´ u.c . . . . . . . . . . . . . . . . . . . 32 1.6 Nguyˆen l´ `ong chim bˆ y chuˆ `o cˆau . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.6.1 Nguyˆen l´ `ong chim bˆ y chuˆ u. nhˆa´t) . . . . . . . . . . . . `o cˆau (da.ng th´ 36 1.6.2 Nguyˆen l´ `ong chim bˆ y chuˆ u. hai) . . . . . . . . . . . . . `o cˆau (da.ng th´ 37 1.6.3 Nguyˆen l´ `ong chim bˆ y chuˆ u. ba) . . . . . . . . . . . . . `o cˆau (da.ng th´ 39 ˆ. 2 QUAN HE 43 2.1 Quan hˆe. hai ngˆoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Quan hˆe. v`a ma trˆa.n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3
2.3 u. tu.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Quan hˆe. th´ 54 2.4 Quan hˆe. tu.o.ng d¯u.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.5 Bao d¯o´ng cu˙’a quan hˆe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.6 Lattice cu˙’a c´ac phˆan hoa.ch . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.6.1 Thuˆa.t to´an giao c´ac phˆan hoa.ch . . . . . . . . . . . . . . . . . . . . 77 2.6.2 Thuˆa.t to´an trˆo.n c´ac phˆan hoa.ch . . . . . . . . . . . . . . . . . . . . . 78 -A 3 D ˆ´ BOOLE . I SO 81 3.1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2 Latiice phˆan bˆo´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.3 - a.i sˆo´ Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D 96 3.4 H`am Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.5 Biˆe˙’u diˆ˜en c´ac h`am Boole qua hˆe. tuyˆe˙’n, hˆo.i v`a phu˙’ d¯.inh . . . . . . . . . . . 107 3.6 Biˆe˙’u diˆ˜en tˆo´i thiˆe˙’u cu˙’a h`am Boole . . . . . . . . . . . . . . . . . . . . . . . 111 3.6.1 Kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.6.2 Phu.o.ng ph´ap ba˙’n d¯`ˆo Karnaugh . . . . . . . . . . . . . . . . . . . . . 112 4 MA ˆ´N T´INH ˜ TUYE 119 4.1 Mo˙’. d¯`aˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.1.1 Kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.1.2 M˜a ph´at hiˆe.n lˆo˜i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.1.3 M˜a su˙’.a sai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.2 C´ac kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.3 Khoa˙’ng c´ach Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.4 u.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Hˆo.i ch´ 4.4.1 ung ba˙’ng chuˆa˙’n . . . . . . . . . . . . . . . . . . . . . . . . 140 Gia˙’i m˜a d` 4
4.5 M˜a ho`an ha˙’o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 4.6 M˜a Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 -` 5 DOˆ THI. 149 5.1 C´ac kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.2 `en v`a chu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Dˆay chuyˆ 5.3 Chu tr`ınh Hamilton v`a b`ai to´an ngu.`o.i du li.ch . . . . . . . . . . . . . . . . . 162 5.3.1 Quy tˇa´c t`ım chu tr`ınh Hamilton . . . . . . . . . . . . . . . . . . . . . 164 5.3.2 M˜a Gray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.4 - u.`o.ng d¯i v`a ma.ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 D 5.4.1 Thuˆa.t to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.5 Ma trˆa.n biˆe˙’u diˆ˜en d¯`oˆ thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 5.5.1 `e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Ma trˆa.n kˆ 5.5.2 Ma trˆa.n liˆen thuˆo.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.6 D u.a c´ac d¯`ˆo thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 - ˇa˙’ng cˆa´u gi˜ 5.7 - `ˆo thi. phˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 D ˆ 6 CAY 191 6.1 Mo˙’. d¯`aˆu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.1.1 C´ac kh´ai niˆe.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.1.2 M˜a Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 6.2 Cˆay bao tr` um . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6.2.1 Thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu rˆo.ng x´ac d¯.inh cˆay bao tr` um . . . . . 198 6.2.2 Thuˆa.t to´an t`ım kiˆe´m theo chiˆ `eu sˆau x´ac d¯i.nh cˆay bao tr` um . . . . . 199 6.3 um nho˙’ nhˆa´t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Cˆay bao tr` 6.3.1 Thuˆa.t to´an Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5
6.4 Liˆe.t kˆe cˆay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 6.5 Cˆay nhi. phˆan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 6.5.1 Thuˆa.t to´an xˆay du..ng cˆay t`ım kiˆe´m nhi. phˆan . . . . . . . . . . . . . . 210 T` e.u tham kha˙’ o ai liˆ 215 6
˙’. D MO -` AˆU To´an ho.c r`o.i ra.c l`a mˆo.t bˆo. phˆa.n cu˙’a To´an ho.c nhˇ`a m nghiˆen c´u.u c´ac d¯oˆ´i tu.o..ng r`o.i ra.c: nghiˆen c´ . u u c´ac cˆa´u tr´ . . . uc r`o i ra.c kh´ac nhau v`a c´ac phu o ng ph´ap gia˙’i c´ac vˆa´n d¯`ˆe c´o liˆen quan d¯ˆe´n c´ac cˆa´u tr´ uc n`ay. Thˆong tin lu.u tr˜ u. v`a vˆa.n h`anh trong m´ay t´ınh du.´o.i da.ng c´ac t´ın hiˆe.u r`o.i ra.c (c´ac m´ay t´ınh liˆen tu.c chı˙’ l`a c´ac m´ay t´ınh tu.o.ng tu.., chuyˆen du.ng). V`ı vˆa.y cˆong cu. d` ung d¯ˆe˙’ biˆe˙’u diˆ˜en thˆong tin trong m´ay v`a xu˙’ l´ . . y c´ac thˆong tin n`ay l`a To´an ho.c r`o i ra.c. Ngo`ai ra, c´ac phu.o.ng ph´ap v`a kˆe´t qua˙’ cu˙’a To´an ho.c r`o.i ra.c c´o thˆe˙’ d` ung d¯ˆe˙’ gia˙’i quyˆe´t tru..c tiˆe´p nhiˆ `eu vˆa´n d¯`ˆe d¯aˇ. t ra cu˙’a Tin ho.c nhu. logic, h`am d¯a.i sˆo´ logic, tˆo˙’ ho..p trˆen t` u.... To´an ho.c r`o.i ra.c chuˆa˙’n bi. sˇa˜n v`a cung cˆa´p c´ac cˆong cu., phu.o.ng ph´ap luˆa.n d¯ˆe˙’ gia˙’i quyˆe´t nhiˆ `eu . . . vˆa´n d¯`ˆe cu˙’a Tin ho.c. C´o thˆe˙’ n´oi To´an ho.c r`o i ra.c l`a ng`anh To´an ho.c co so˙’ cho Tin ho.c. Mu.c d¯´ıch cu˙’a gi´ao tr`ınh nhˇ`a m cung cˆa´p mˆo.t sˆo´ cˆong cu. To´an ho.c d¯ˆe˙’ bu.´o.c d¯`aˆu d¯i v`ao Tin ho.c. Gi´ao tr`ınh d¯u.o..c tr`ınh b`ay mˆo.t c´ach d`an tra˙’i ho.n l`a d¯i sˆau v`ao mˆo.t vˆa´n d¯`ˆe cu. thˆe˙’. Cuˆo´i mˆo˜i phˆ`an c´o c´ac b`ai tˆa.p nhˇ`a m cu˙’ng cˆo´ nh˜u.ng kiˆe´n th´ u.c d¯˜a ho.c. Hy vo.ng rˇa` ng gi´ao tr`ınh n`ay d¯a´p u´.ng d¯u.o..c phˆ `an n`ao yˆeu cˆ `au ho.c tˆa.p cu˙’a c´ac ba.n sinh viˆen. `om s´au chu.o.ng v´o.i 20 t`ai liˆe.u tham kha˙’o tr`ınh b`ay c´ac vˆa´n d¯`ˆe sau: Gi´ao tr`ınh bao gˆ Chu.o.ng 1: Ph´ep d¯ˆe´m. D - `ˆe cˆa.p d¯ˆe´n c´ac phu.o.ng ph´ap co. ba˙’n cu˙’a ph´ep d¯ˆe´m: Nguyˆen l´y t´ıch, nguyˆen l´ y tˆo˙’ng, nguyˆen l´ y bao h`am-loa.i tr` u., nguyˆen l´ y c´ac chuˆ`ong chim bˆ `o cˆau... Ch´ ung d¯o´ng vai tr`o quan tro.ng trong Tin ho.c, chˇa˙’ng ha.n: d¯ˆe˙’ u ´o c lu o. ng th`o i gian thu..c hiˆe.n . . . . . cu˙’a mˆo.t thuˆa.t to´an ch´ ung ta cˆ `an d¯ˆe´m sˆo´ th`o.i gian thi h`anh t`u.ng d`ong lˆe.nh hoˇa.c c´ac v`ong lˇa.p. Ph´ep d¯ˆe´m c˜ung d¯o´ng vai tr`o quan tro.ng trong l´ y thuyˆe´t x´ac suˆa´t. Chu.o.ng 2: Quan hˆe.. Tr`ınh b`ay c´ac quan hˆe. th´ u. tu.., quan hˆe. tu.o.ng d¯u.o.ng v`a cuˆo´i c` ung l`a quan hˆe. tˆo˙’ng qu´at trˆen nh˜ . u ng tˆa.p h˜ . u u ha.n. Ch´ung ta c˜ ung x´et mˆo´i quan hˆe. gi˜ u.a c´ac quan hˆe. v´o.i ma trˆa.n hay d¯`oˆ thi. biˆe˙’u diˆ˜en n´o. Chu.o.ng 3: D - a.i sˆo´ Boole. Thuˆa.t ng˜ u. “d¯a.i sˆo´ Boole” d¯u.o..c su˙’. du.ng d¯ˆe˙’ mˆo ta˙’ nhiˆ`eu l˜ınh . vu. c c´o liˆen quan, t` u tu duy logic v`a c´ac ba˙’ng chˆan tri. d¯ˆe´n c´ac ph´ep to´an sˆo´ ho.c d¯u o..c thu..c . . . hiˆe.n bo˙’.i c´ac ma.ch d¯iˆe.n tu˙’.. Chu.o.ng n`ay bˇa´t d¯`ˆau v´o.i mˆo´i quan hˆe. gi˜ u.a c´ac tˆa.p d¯u.o..c sˇa´p th´ . . . u tu. v`a c´ac lattice. Kˆe´ tiˆe´p l`a d¯a.i sˆo´ Boole v`a vˆa´n d¯`ˆe cu. c tiˆe˙’u ho´a h`am Boole. 7
Chu.o.ng 4: M˜a tuyˆe´n t´ınh. Gi´o.i thiˆe.u so. lu.o..c vˆ `e l´ y thuyˆe´t m˜a bao gˆ `om c´ac m˜a cho ph´ep . ph´at hiˆe.n v`a su˙’ a sai. D- ˆay l`a vˆa´n d¯`ˆe th`o i su. do su. ph´at triˆe˙’n c´ac cˆong nghˆe. m´o.i trong viˆe.c . . . `en v`a lu.u tr˜ truyˆ u. d˜ u. liˆe.u. Chu.o.ng 5: D - `ˆo thi.. Chu.o.ng n`ay gi´o.i thiˆe.u mˆo.t sˆo´ kh´ai niˆe.m v`a b`ai to´an co. ba˙’n cu˙’a l´ y . . . thuyˆe´t d¯`oˆ thi. nhu chu tr`ınh Euler, chu tr`ınh Hamilton, d¯u `o ng d¯i ngˇa´n nhˆa´t, t´ınh phˇa˙’ng cu˙’a d¯`ˆo thi.... Chu.o.ng 6: Cˆay. Nˆo.i dung ch´ınh cu˙’a chu.o.ng d¯`ˆe cˆa.p d¯ˆe´n nh˜u.ng vˆa´n d¯`ˆe: Xˆay du..ng m˜a tˆo´i u.u Huffman, cˆay bao tr` um v`a hˆe. c´ac chu tr`ınh d¯oˆ. c lˆa.p, cˆay bao tr`um tˆo´i thiˆe˙’u, liˆe.t kˆe cˆay. Tˆoi d¯aˇ. c biˆe.t c´am o.n c´ac d¯`oˆng nghiˆe.p, d¯aˇ. c biˆe.t Th.s. Trˆ `an Tuˆa´n Minh, c´ac ba.n b`e v`a c´ac sinh viˆen v`ı nh˜ . u ng d¯´ong g´op cu˙’a ho. trong qu´a tr`ınh biˆen soa.n gi´ao tr`ınh n`ay. Tˆoi chˆan th`anh c´am o.n ba.n d¯o.c vˆ u.ng y `e nh˜ ´ kiˆe´n d¯ˆo´i v´o.i c´ac thiˆe´u s´ot khˆong thˆe˙’ tr´anh kho˙’i cu˙’a cuˆo´n s´ach. - `a La.t, ng`ay 12 th´ang 6 nˇam 2003 D Pha.m Tiˆe´n So.n 8
Chu.o.ng 1 ´ D PHEP ˆ´M -E To´an tˆo˙’ ho..p nghiˆen c´ u.u vˆ`e c´ach sˇa´p xˆe´p c´ac d¯ˆo´i tu.o..ng, l`a mˆo.t bˆo. phˆa.n quan tro.ng cu˙’a to´an ho.c r`o.i ra.c. Nh˜ u.ng vˆa´n d¯`ˆe cu˙’a tˆo˙’ ho..p d¯u.o..c nghiˆen c´u.u t` u. Thˆe´ ky˙’ 17, liˆen quan tru.´o.c . . tiˆen d¯ˆe´n c´ac tr`o cho i may ru˙’i. Ng`ay nay to´an tˆo˙’ ho. p d¯u o. c d`. . ung rˆo.ng r˜ai trong tin ho.c. Mu.c d¯´ıch ch´ınh cu˙’a chu.o.ng n`ay l`a thiˆe´t lˆa.p mˆo.t sˆo´ phu.o.ng ph´ap d¯ˆe´m c´ac tˆa.p h˜ u.u ha.n phˆ . `an tu˙’ cu˙’a ch´ `an tu˙’ m`a khˆong liˆe.t kˆe c´ac phˆ . ung. 1.1 C´ ac nguyˆ y co. ba˙’n cu˙’a ph´ en l´ ep d ¯ˆe´m u.u ha.n phˆ V´oi tˆa.p h˜ `an tu˙’. S, ta k´ y hiˆe.u #S l`a sˆo´ phˆ `an tu˙’. cu˙’a tˆa.p S. Do d¯o´ #S = #T nˆe´u ung sˆo´ c´ac phˆ hai tˆa.p S v`a T c´o c` `an tu˙’.. Ch´ uy´ rˇ`a ng #∅ = 0, #{1, 2, . . . , n} = n v´o.i n ∈ N. ung ta bˇa´t d¯`aˆu v´o.i mˆo.t sˆo´ nguyˆen l´ Ch´ y d¯ˆe´m. 1.1.1 Nguyˆ en l´ o˙’ng y tˆ Gia˙’ su˙’. A1 , A2 , . . . , Am l`a c´ac su.. kiˆe.n d¯oˆi mˆo.t loa.i tr` u. nhau; v`a gia˙’ su˙’. c´ac su.. kiˆe.n A1 , A2 , . . . , Am . . c´o tu o ng u ´ ng n1 , n2 , . . . , nm c´ach xa˙’y ra. Khi d¯´o su.. kiˆe.n (hoˇa.c A1 , hoˇa.c A2 , . . . , hoˇa.c Am ) . c´o n1 + n2 + · · · + nm c´ach xa˙’y ra. V´ı du. 1.1.1 Gia˙’ su˙’. l´o.p tru.o˙’.ng c´o thˆe˙’ l`a mˆo.t n˜ u. sinh, hoˇa.c l`a mˆo.t nam sinh. C´o bao nhiˆeu . . . c´ach cho.n l´o p tru o˙’ ng kh´ac nhau nˆe´u sˆo´ ho.c sinh n˜ u. l`a 36 v`a sˆo´ nam sinh l`a 20? 9
Go.i A1 (tu.o.ng u ´.ng, A2 ) l`a su.. kiˆe.n l´o.p tru.o˙’.ng l`a n˜ u. sinh (tu.o.ng u ´.ng, nam sinh). Ta c´o 36 c´ach cho.n l´o.p tru.o˙’.ng l`a n˜ u. sinh v`a 20 c´ach cho.n l´o.p tru.o˙’.ng l`a nam sinh. Theo nguyˆen y tˆo˙’ng, su.. kiˆe.n (A1 hoˇa.c A2 ) c´o (36 + 20) = 56 c´ach cho.n. l´ V´ı du. 1.1.2 Gia˙’ su˙’. mˆo.t sinh viˆen c´o thˆe˙’ cho.n d¯u ´ng mˆo.t chuyˆen d¯`ˆe tu.. cho.n trong mˆo.t trong ba danh s´ach. Ba danh s´ach n`ay gˆ `om 3, 5 v`a 9 chuyˆen d¯`ˆe tu.o.ng u´.ng. Ho˙’i sinh viˆen d¯´o c´o bao nhiˆeu c´ach lu..a cho.n? y tˆo˙’ng, c´o 3 + 5 + 9 = 17 c´ach. Theo nguyˆen l´ Nhˆ a.n x´ et 1 Nguyˆen l´ y tˆo˙’ng c´o thˆe˙’ ph´at biˆe˙’u theo thuˆa.t ng˜ u. cu˙’a l´ y thuyˆe´t tˆa.p ho..p nhu. . sau. Nˆe´u c´ac tˆa.p T1 , T2 , . . . , Tm d¯oˆi mˆo.t r`o i nhau th`ı sˆo´ c´ac phˆ . `an tu˙’ cu˙’a tˆa.p T1 ∪T2 ∪· · ·∪Tm bˇ`a ng tˆo˙’ng sˆo´ c´ac phˆ . `an tu˙’ cu˙’a c´ac tˆa.p n`ay; t´ . u c l`a m X #(T1 ∪ T2 ∪ . . . ∪ Tm ) = #Ti . i=1 1.1.2 Nguyˆ en l´ y t´ıch Gia˙’ su˙’. A1 , A2 , . . . , Am l`a c´ac su.. kiˆe.n d¯oˆi mˆo.t loa.i tr` u. nhau; v`a gia˙’ su˙’. c´ac su.. kiˆe.n A1 , A2 , . . . , Am . . c´o tu o ng u ´ ng n1 , n2 , . . . , nm c´ach xa˙’y ra. Khi d¯o´ su.. kiˆe.n (A1 v`a A2 v`a . . . v`a Am ) c´o . n1 × n2 × · · · × nm c´ach xa˙’y ra. V´ı du. 1.1.3 Gia˙’ su˙’. c´o hai mˇa.t na., ba m˜ u. Ho˙’i c´o mˆa´y c´ach ho´a trang? D`ung nguyˆen l´ y t´ıch, c´o 3 × 2 = 6 c´ach ho´a trang kh´ac nhau. C˜ ung c´o thˆe˙’ d` y thuyˆe´t ung l´ . . tˆa.p ho. p nhu sau: Mˆo˜i c´ach ho´a trang l`a mˆo.t c´ach cho.n x ∈ X v`a mˆo.t c´ach cho.n y ∈ Y. Do d¯´o sˆo´ c´ach ho´a trang l`a sˆo´ c´ac cˇa.p (x, y) thuˆo.c X × Y v`a do d¯o´ bˇ`a ng #X × #Y = 2 × 3 = 6. Nhˆ a.n x´ et 2 Nguyˆen l´ ung thu.`o.ng d¯u.o..c ph´at biˆe˙’u du.´o.i da.ng tˆa.p ho..p nhu. sau: Gia˙’ y n`ay c˜ su˙’. c´ac tˆa.p T1 , T2 , . . . , Tm c´o h˜ u.u ha.n phˆ`an tu˙’. v`a d¯oˆi mˆo.t r`o.i nhau. Khi d¯´o sˆo´ phˆ`an tu˙’. cu˙’a tˆa.p t´ıch Descartes T1 × T2 × · · · × Tm bˇ`a ng #T1 × #T2 × · · · × #Tm . V´ı du. 1.1.4 C´o bao nhiˆeu chuˆo˜i bit kh´ac nhau c´o d¯ˆo. d`ai 8? Mˆo˜i bit c´o hai c´ach cho.n, hoˇa.c y t´ıch, c´o 28 = 256 chuˆo˜i bit c´o d¯oˆ. d`ai 8. 0 hoˇa.c 1. Do d¯o´ theo nguyˆen l´ V´ı du. 1.1.5 C´o bao nhiˆeu ba˙’ng sˆo´ xe kh´ac nhau, nˆe´u mˆo˜i ba˙’ng gˆ u. c´ai v`a theo `om ba ch˜ sau l`a ba con sˆo´ (gia˙’ thiˆe´t ba˙’ng ch˜. `om 26 k´ u c´ai gˆ . y tu. )? 10
Mˆo˜i ch˜u. c´ai c´o 26 c´ach cho.n; mˆo˜i sˆo´ c´o 10 c´ach cho.n. Do d¯´o theo nguyˆen l´ y t´ıch, sˆo´ c´ac ba˙’ng sˆo´ xe kh´ac nhau l`a: 26 × 26 × 26 × 10 × 10 × 10 = 17.576.000. u. tˆa.p X c´o m phˆ V´ı du. 1.1.6 C´o bao nhiˆeu ´anh xa. kh´ac nhau t` `an tu˙’. lˆen tˆa.p Y c´o n phˆ `an ˙ ’. tu ? Mˆo˜i ´anh xa. l`a mˆo.t bˆo. m c´ach cho.n mˆo.t trong n phˆ `an tu˙’. cu˙’a Y cho mˆo˜i mˆo.t trong m phˆ `an . tu˙’ cu˙’a X. Theo nguyˆen l´ y t´ıch, sˆo´ ´anh xa. n`ay bˇa` ng m {z· · · × n} = n . |n × n × `an m lˆ V´ı du. 1.1.7 C´o bao nhiˆeu ´anh xa. mˆo.t-mˆo.t (d¯o.n ´anh) kh´ac nhau t` u. tˆa.p X c´o m phˆ `an tu˙’. `an tu˙’.? lˆen tˆa.p Y c´o n phˆ u. X t´o.i Y. Nˆe´u m > n : khˆong c´o ´anh xa. mˆo.t-mˆo.t t` Gia˙’ su˙’. m ≤ n v`a X := {a1 , a2 , . . . , am }. + V´o.i phˆ `an tu˙’. a1 c´o n c´ach cho.n phˆ `an tu˙’. tu.o.ng u ´.ng trong Y. + V`ı ´anh xa. l`a mˆo.t-mˆo.t, nˆen d¯oˆ´i v´o.i a2 chı˙’ c`on (n − 1) c´ach cho.n. .. . + Tu.o.ng tu.., am chı˙’ c`on (n − m + 1) c´ach cho.n. y t´ıch, sˆo´ ´anh xa. mˆo.t-mˆo.t kh´ac nhau bˇa` ng Theo nguyˆen l´ n(n − 1)(n − 2) · · · (n − m + 1). u.u ha.n S. - ˆe´m sˆo´ tˆa.p con cu˙’a mˆo.t tˆa.p h˜ V´ı du. 1.1.8 D Gia˙’ su˙’. S := {a1 , a2 , . . . , an }. Dˆ˜e d`ang thiˆe´t lˆa.p mˆo.t tu.o.ng u ´.ng mˆo.t-mˆo.t gi˜ u.a tˆa.p con P . cu˙’a S v´o i c´ac chuˆo˜i bit d¯oˆ. d`ai n : bit th´ . u i bˇ`a ng 1 nˆe´u v`a chı˙’ nˆe´u ai ∈ P. Mˇa.t kh´ac, sˆo´ c´ac chuˆo˜i bit d¯oˆ. d`ai n l`a 2 nˆen sˆo´ c´ac tˆa.p con cu˙’a S l`a 2n . n V´ı du. 1.1.9 Cho hai d¯oa.n chu.o.ng tr`ınh sau: Chu.o.ng tr`ınh 1: Chu.o.ng tr`ınh 2: k := 0; k := 0; for i1 := 1 to n1 do k := k + 1; for i1 := 1 to n1 do for i2 := 1 to n2 do k := k + 1; for i2 := 1 to n2 do ... ... for im := 1 to nm do k := k + 1; for im := 1 to nm do k := k + 1; 11
Ho˙’i k s˜e lˆa´y gi´a tri. bao nhiˆeu sau khi mˆo˜i d¯oa.n chu.o.ng tr`ınh trˆen d¯u.o..c thu..c hiˆe.n? + Chu.o.ng tr`ınh 1: C´ u. mˆo˜i v`ong lˇa.p d¯.ia phu.o.ng, k tˇang lˆen mˆo.t d¯o.n vi.. Go.i Ai l`a sˆo´ lˆ `an lˇa.p cu˙’a v`ong lˇa.p th´u. i. Ai c´o ni kha˙’ nˇang. Ho.n n˜ u.a Ai v`a Aj , i 6= j, loa.i tr`. u nhau. Do d¯o´ theo nguyˆen l´ y tˆo˙’ng, sˆo´ v`ong lˇa.p l`a n1 + n2 + · · · + nm . + Chu.o.ng tr`ınh 2: C´ u. mˆo˜i v`ong lˇa.p to`an cu.c, k tˇang lˆen mˆo.t d¯o.n vi.. Mˆo˜i v`ong lˇa.p to`an cu.c do m v`ong lˇa.p d¯i.a phu.o.ng gh´ep la.i. Theo nguyˆen l´ y t´ıch sˆo´ v`ong lˇa.p to`an cu.c bˇ`a ng n1 × n2 × · · · × nm . V´ı du. 1.1.10 Trong nhiˆ `eu tru.`o.ng ho..p cˆ`an pha˙’i phˆo´i ho..p ca˙’ hai nguyˆen l´ y tˆo˙’ng v`a t´ıch: . . . . Gia˙’ su˙’ mˆo˜i ngu `o i su˙’ du.ng m´ay t´ınh c´o mˆo.t mˆa.t m˜a, gˆ `om t` . u 6 d¯ˆe´n 8 k´ y tu..; mˆo˜i k´ y tu.. l`a mˆo.t ch˜ u. c´ai hoa hoˇa.c l`a mˆo.t con sˆo´. Mˆo˜i mˆa.t m˜a nhˆa´t thiˆe´t pha˙’i ch´ u.a ´ıt nhˆa´t mˆo.t con sˆo´. Ho˙’i c´o bao nhiˆeu mˆa.t m˜a c´o thˆe˙’ c´o? Go.i P l`a tˆo˙’ng sˆo´ c´ac mˆa.t m˜a c´o thˆe˙’ c´o v`a P6 , P7 , P8 l`a sˆo´ c´ac mˆa.t m˜a c´o thˆe˙’ v´o.i d¯oˆ. d`ai tu.o.ng u ´.ng bˇ`a ng 6, 7, 8. y tˆo˙’ng: P = P6 + P7 + P8 . Theo nguyˆen l´ Viˆe.c t´ınh tru..c tiˆe´p P6 l`a kh´o. Ta t´ınh gi´an tiˆe´p nhu. sau: + Sˆo´ c´ac xˆau c´o d¯ˆo. d`ai 6, gˆ u. v`a sˆo´, bao gˆ `om ch˜ `om ca˙’ tru.`o.ng ho..p khˆong c´o con sˆo´ n`ao theo nguyˆen l´ y t´ıch l`a (26 + 10)6 = 366 . u.a con sˆo´ n`ao l`a 266 . + Sˆo´ c´ac xˆau d¯oˆ. d`ai 6, khˆong ch´ + Do d¯o´ P6 = 366 − 266 = 1.867.866.560. Tu.o.ng tu.. cho P7 v`a P8 : P7 = 367 − 267 = 70.332.353.920, P8 = 368 − 268 = 2.612.282.842.880. Cuˆo´i c` ung P = P6 + P7 + P8 = 2.684.483.063.360. Nhˆ a.n x´et 3 Khi c´ac su.. kiˆe.n A1 v`a A2 c´o thˆe˙’ xa˙’y ra d¯`ˆong th`o.i ta khˆong thˆe˙’ d` ung nguyˆen . . . y tˆo˙’ng. Tru `o ng ho. p n`ay cˆ l´ . . `an su˙’ a d¯oˆ˙’i nhu sau: Nˆe´u vˆa˜n cˆo.ng (n1 + n2 ) ta d¯a˜ d¯ˆe´m th` u.a, v`ı c´o tru.`o.ng ho..p d¯a˜ d¯ˆe´m hai lˆ `an c` ung mˆo.t su.. kiˆe.n (mˆo.t lˆ `an trong A1 , mˆo.t lˆ `an trong A2 ). . . . . Tru `o ng ho. p n`ay chı˙’ xa˙’y ra khi n´o d¯`oˆng th`o i c´o thˆe˙’ xa˙’y ra A1 v`a A2 . V`ı vˆa.y cˆ u. d¯i sˆo´ `an tr` tru.`o.ng ho..p dˆoi th` u.a n`ay. 12
1.1.3 Nguyˆ en l´ y bao h` u. am-loa.i tr` Gia˙’ su˙’. A1 v`a A2 l`a hai su.. kiˆe.n bˆa´t k` y. Nˆe´u su.. kiˆe.n A1 c´o thˆe˙’ xa˙’y ra n1 c´ach, su.. kiˆe.n A2 c´o thˆe˙’ xa˙’y ra n2 c´ach, th`ı su.. kiˆe.n (A1 hoˇa.c A2 ) c´o thˆe˙’ xa˙’y ra [(n1 + n2 )− sˆo´ lˆ `an (A1 v`a A2 )] c´ach. u. tˆa.p ho..p, nguyˆen l´ Bˇ`a ng thuˆa.t ng˜ u. tro˙’. th`anh: y bao h`am-loa.i tr` #(A1 ∪ A2 ) = #A1 + #A2 − #(A1 ∩ A2 ). V´ı du. 1.1.11 C´o bao nhiˆeu chuˆo˜i bit d¯oˆ. d`ai 8 hoˇa.c bˇa´t d¯`aˆu bˇ`a ng 1, hoˇa.c kˆe´t th´ uc bˇ`a ng ˙ ’ ˜ 00? (C´o thˆe c´o chuˆoi v`. ´ ` ` u a bˇat d¯ˆau bˇa ng 1, v`. ´ u a kˆet th´ ` uc bˇa ng 00). Go.i P1 l`a sˆo´ c´ac chuˆo˜i bit d¯oˆ. d`ai 8 bˇa´t d¯`aˆu bˇa` ng 1. Nhu. vˆa.y, phˆ `an tu˙’. th´ u. nhˆa´t d¯a˜ d¯u.o..c cho.n, chı˙’ c`on la.i 7 bit. Theo nguyˆen l´ y t´ıch, P1 = 27 = 128. Go.i P2 l`a sˆo´ c´ac chuˆo˜i bit d¯oˆ. d`ai 8 kˆe´t th´ uc bˇa` ng 00. Theo nguyˆen l´ y t´ıch P2 = 26 = 64. Go.i P3 l`a sˆo´ c´ac chuˆo˜i bit d¯oˆ. d`ai 8 bˇa´t d¯`ˆau bˇ`a ng 1 v`a kˆe´t th´ uc bˇ`a ng 00. Theo nguyˆen l´ y t´ıch P3 = 25 = 32. ´ du.ng nguyˆen l´ Ap y bao h`am-loa.i tr` u. ta c´o P = P1 + P2 − P3 = 160. Nguyˆen l´ y bao h`am-loa.i tr` u. c´o thˆe˙’ mo˙’. rˆo.ng cho tru.`o.ng ho..p m su.. kiˆe.n, nhu.ng ph´ u.c ta.p ho.n, ta s˜e d¯`ˆe cˆa.p o˙’. phˆ `an sau. Su.. cˆong nhˆa.n ba nguyˆen l´ y trˆen nhu. l`a xuˆa´t ph´at d¯iˆe˙’m cu˙’a l´ y thuyˆe´t tˆo˙’ ho..p: + T´ınh d¯u ´ng d¯ˇa´n cu˙’a ba nguyˆen l´ ´ng hiˆe˙’n nhiˆen”. Quan d¯iˆe˙’m cu˙’a ch´ y trˆen l`a “d¯u ung ta l`a cˆong nhˆa.n 3 nguyˆen l´ . ˙ ’ y trˆen, coi nhu xuˆa´t ph´at d¯iˆem cu˙’a l´ ˙ ’ . y thuyˆe´t tˆo ho. p. C´ac kˆe´t qua˙’ `an lu.o..t d¯u.o..c suy ra tru..c tiˆe´p hoˇa.c gi´an tiˆe´p t` kh´ac s˜e lˆ u. ba nguyˆen l´y n`ay. + Nˆe´u khˆong thoa˙’ m˜an, c˜ u.ng minh ba nguyˆen l´ ung c´o thˆe˙’ t`ım c´ach ch´ y n`ay, nhu. vˆa.y ta `an d¯ˆe´n c´ac cˆong cu. kh´ac, thu..c chˆa´t ta la.i cˆong nhˆa.n mˆo.t d¯iˆ la.i pha˙’i cˆ `eu g`ı kh´ac l`a “d¯u ´ng hiˆe˙’n nhiˆen” d¯ˆe˙’ rˆ `oi suy luˆa.n ra ba nguyˆen l´ y trˆen. B` ai tˆ a.p 1. C´o bao nhiˆeu chuˆo˜i 8 bit bˇa´t d¯`ˆau bˇa` ng 1100? 13
2. C´o bao nhiˆeu chuˆo˜i 8 bit bˇa´t d¯`ˆau v`a kˆe´t th´ uc bˇa` ng 1? u. hai, hoˇa.c bit th´ 3. C´o bao nhiˆeu chuˆo˜i 8 bit trong d¯o´ hoˇa.c bit th´ u. tu. bˇ`a ng 1? 4. C´o bao nhiˆeu chuˆo˜i 8 bit c´o d¯u ´ng mˆo.t bit bˇ`a ng 1? D -u ´ng hai bit bˇa` ng 1? C´o ´ıt nhˆa´t mˆo.t bit bˇ`a ng 1? 5. C´o bao nhiˆeu chuˆo˜i 8 bit d¯o.c xuˆoi ngu.o..c d¯`ˆeu giˆo´ng nhu. nhau? 6. C´ac k´y tu.. ABCDE d¯u.o..c su˙’. du.ng d¯ˆe˙’ ta.o th`anh c´ac chuˆo˜i d¯oˆ. d`ai 3. (a) C´o bao nhiˆeu chuˆo˜i d¯u.o..c ta.o ra nˆe´u cho ph´ep lˇa.p? (b) C´o bao nhiˆeu chuˆo˜i d¯u.o..c ta.o ra nˆe´u khˆong cho ph´ep lˇa.p? (c) C´o bao nhiˆeu chuˆo˜i bˇa´t d¯`ˆau bˇ`a ng A d¯u.o..c ta.o ra nˆe´u cho ph´ep lˇa.p? (d) C´o bao nhiˆeu chuˆo˜i bˇa´t d¯`ˆau bˇ`a ng A d¯u.o..c ta.o ra nˆe´u khˆong cho ph´ep lˇa.p? (e) C´o bao nhiˆeu chuˆo˜i khˆong ch´ u.a k´ y tu.. A d¯u.o..c ta.o ra nˆe´u cho ph´ep lˇa.p? (f) C´o bao nhiˆeu chuˆo˜i khˆong ch´ u.a k´ y tu.. A d¯u.o..c ta.o ra nˆe´u khˆong cho ph´ep lˇa.p? 7. Trˆen tˆa.p X := {5, 6, . . . , 200} : (a) C´o bao nhiˆeu sˆo´ chˇa˜n, le˙’? (b) C´o bao nhiˆeu sˆo´ chia hˆe´t cho 5? (c) C´o bao nhiˆeu sˆo´ gˆ `om nh˜ u.ng ch˜u. sˆo´ phˆan biˆe.t? (d) C´o bao nhiˆeu sˆo´ khˆong ch´ u.a ch˜u. sˆo´ 0? (e) C´o bao nhiˆeu sˆo´ l´o.n ho.n 101 v`a khˆong ch´ u.a ch˜ u. sˆo´ 6? u. sˆo´ d¯u.o..c sˇa´p theo th´ (f) C´o bao nhiˆeu sˆo´ c´o c´ac ch˜ u. tu.. tˇang thu..c su..? (g) C´o bao nhiˆeu sˆo´ c´o da.ng xyz v´o.i 0 6= x < y v`a y > z? 8. Gia˙’ su˙’. c´o 5 s´ach tin ho.c, 3 s´ach m´ay t´ınh, 2 s´ach vˆa.t l´ y. (a) C´o bao nhiˆeu c´ach sˇa´p xˆe´p ch´ ung lˆen gi´a s´ach? (b) C´o bao nhiˆeu c´ach sˇa´p xˆe´p sao cho 5 s´ach tin ho.c o˙’. ph´ıa tr´ai, c`on 2 s´ach vˆa.t l´y o˙’. bˆen pha˙’i? (c) C´o bao nhiˆeu c´ach sˇa´p ch´ ung nh´om d¯u.o..c ung lˆen gi´a sao cho tˆa´t ca˙’ c´ac s´ach theo c` sˇa´p kˆ `e nhau? (d) C´o bao nhiˆeu c´ach sˇa´p ch´ ung lˆen gi´a sao cho hai s´ach vˆa.t l´ `e nhau? y khˆong kˆ 9. C´o 10 ba˙’n copy cu˙’a mˆo.t cuˆo´n s´ach v`a c´o mˆo.t copy cu˙’a 10 cuˆo´n s´ach kh´ac. C´o bao nhiˆeu c´ach c´o thˆe˙’ cho.n 10 cuˆo´n s´ach? `eu nhˆa´t n phˆ 10. C´o bao nhiˆeu tˆa.p con c´o nhiˆ `an tu˙’. cu˙’a tˆa.p gˆ `om (2n + 1) phˆ `an tu˙’.? ´ du.ng nguyˆen l´ 11. Ap y bao h`am-loa.i tr`u. d¯ˆe˙’ gia˙’i: (a) C´o bao nhiˆeu chuˆo˜i 8 bit hoˇa.c bˇa´t d¯`ˆau bˇ`a ng 100 hoˇa.c c´o bit th´ u. tu. bˇa` ng 1? (b) C´o bao nhiˆeu chuˆo˜i 8 bit hoˇa.c bˇa´t d¯`ˆau bˇ`a ng 1 hoˇa.c kˆe´t th´uc bˇa` ng 1? 14
1.2 Ho´ an vi. v` o˙’ ho..p a tˆ `an tu˙’. x1 , x2 , . . . , xn l`a mˆo.t sˇa´p xˆe´p c´o th´ - i.nh ngh˜ıa 1.2.1 Mˆo.t ho´an vi. cu˙’a n phˆ D u. tu.. n phˆ . `an tu˙’ n`ay. `an tu˙’.. Nˆe´u c´ac phˆ V´ı du. 1.2.1 C´o s´au ho´an vi. cu˙’a ba phˆ `an tu˙’. d¯u.o..c k´ y hiˆe.u l`a A, B, C th`ı s´au ho´an vi. l`a ABC, ACB, BAC, BCA, CAB, CBA. - i.nh l´ D `an tu˙’.. an vi. cu˙’ a n phˆ y 1.2.2 C´o n! ho´ Ch´ u.ng minh. Ta ch´ u.ng minh theo quy na.p. Mˆo.t ho´an vi. cu˙’a n phˆ `an tu˙’. c´o thˆe˙’ d¯u.o..c xˆay du..ng theo n bu.´o.c liˆen tiˆe´p: Cho.n phˆ `an tu˙’. d¯`aˆu tiˆen, cho.n phˆ `an tu˙’. th´u. hai, ..., cho.n phˆ `an . ´ tu˙’ cuˆoi c` ` . ` ˙ ’ ` . ` ung. Phˆan tu˙’ d¯aˆu tiˆen c´o thˆe cho.n n c´ach. Ngay khi phˆan tu˙’ d¯ˆau tiˆen d¯u o. c cho.n, . . phˆ `an tu˙’. th´ u. hai c´o thˆe˙’ d¯u.o..c cho.n n − 1 c´ach. Khi phˆ `an tu˙’. th´ u. hai d¯˜a d¯u.o..c cho.n, phˆ `an tu˙’. th´ u. ba c´o thˆe˙’ d¯u.o..c cho.n n − 2 c´ach, v`a vˆan vˆan. Theo nguyˆen l´ y quy na.p v`a sau d¯o´ nguyˆen l´ ` y t´ıch, tˆon ta.i n(n − 1)(n − 2) · · · 2 · 1 = n! ho´an vi. cu˙’a n phˆ `an tu˙’.. 2 V´ı du. 1.2.2 C´o 10! = 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 3.628.800 `an tu˙’.. ho´an vi. cu˙’a 10 phˆ y tu.. ABCDEF ch´ V´ı du. 1.2.3 C´o bao nhiˆeu ho´an vi. cu˙’a c´ac k´ u.a chuˆo˜i con DEF ? C´o thˆe˙’ xem chuˆo˜i con DEF nhu. mˆo.t k´ y tu... Theo D - i.nh l´ y 1.2.2 c´o 4! = 24 ho´an vi. cu˙’a c´ac k´ . y tu. ABCDEF ch´ . ˜ u a chuˆoi con DEF. y tu.. ABCDEF ch´ V´ı du. 1.2.4 C´o bao nhiˆeu ho´an vi. cu˙’a c´ac k´ u.a c´ac k´ y tu.. DEF theo th´ u. tu.. bˆa´t k` y? Ta c´o thˆe˙’ gia˙’i b`ai to´an qua hai bu.´o.c: Cho.n mˆo.t th´ u. tu.. cu˙’a c´ac k´y tu.. DEF ; v`a xˆay du..ng mˆo.t ho´an vi. cu˙’a ABC ch´ u.a th´ u. tu.. d¯˜a cho cu˙’a c´ac k´y tu.. DEF. Theo D - i.nh l´ y 1.2.2, bu.´o.c d¯`ˆau tiˆen c´o 3! = 6 c´ach; theo V´ı du. 1.2.3 bu.´o.c th´ u. hai c´o 4! = 24 c´ach. Theo nguyˆen l´ y t´ıch, sˆo´ c´ac ho´an vi. cu˙’a ABCDEF ch´ . . y tu. DEF theo th´ u a c´ac k´ u. tu.. bˆa´t k` y l`a 6 · 24 = 144. Trong mˆo.t sˆo´ tru.`o.ng ho..p ta muˆo´n kha˙’o s´at mˆo.t th´ u. tu.. cu˙’a r phˆ `an tu˙’. d¯u.o..c cho.n t` u. n . `an tu˙’ . Mˆo.t th´ phˆ . . . u tu. nhu thˆe´ go.i l`a “r-ho´an vi.”. 15
- i.nh ngh˜ıa 1.2.3 Mˆo.t r-ho´an vi. cu˙’a n phˆ D `an tu˙’. (phˆan biˆe.t) x1 , x2 , . . . , xn l`a mˆo.t sˇa´p xˆe´p r-phˆ `an tu˙’. c´o th´ u. tu.. t` u. n phˆ `an tu˙’. n`ay. Sˆo´ c´ac r-ho´an vi. cu˙’a tˆa.p n phˆ `an tu˙’. phˆan biˆe.t k´ y hiˆe.u l`a P (n, r). V´ı du. 1.2.5 Ta c´o mˆo.t sˆo´ 2-ho´an vi. cu˙’a a, b, c l`a ab, bc, ac. Nˆe´u r = n trong D ung ta nhˆa.n d¯u.o..c mˆo.t th´ - i.nh ngh˜ıa 1.2.3, ch´ u. tu.. cu˙’a tˆa´t ca˙’ n phˆ `an tu˙’.. - i.nh l´ Do d¯´o theo D y 1.2.2 P (n, n) = n!. Tˆo˙’ng qu´at ta c´o - i.nh l´ D y 1.2.4 Sˆo´ c´ac r-ho´ `an tu˙’. phˆan biˆe.t l`a an vi. cu˙’ a tˆa.p n phˆ P (n, r) = n(n − 1)(n − 2) · · · (n − r + 1), r ≤ n. Ch´u.ng minh. Ch´ ung ta d¯ˆe´m sˆo´ c´ac c´ach c´o th´ u. tu.. cu˙’a r phˆ`an tu˙’. d¯u.o..c cho.n t` u. tˆa.p gˆ `om n phˆ . `an tu˙’ . C´o n c´ach cho.n phˆ . `an tu˙’ d¯`ˆau tiˆen. Kˆe´ tiˆe´p, c´o n − 1 c´ach cho.n phˆ . `an tu˙’ th´u. hai, n − 2 c´ach cho.n phˆ `an tu˙’. th´u. ba, ..., c´o n − r + 1 c´ach cho.n phˆ `an tu˙’. th´ u. r. Do d¯o´ theo nguyˆen l´y t´ıch, sˆo´ c´ac r-ho´an vi. cu˙’a tˆa.p n phˆ . `an tu˙’ phˆan biˆe.t l`a n(n − 1)(n − 2) · · · (n − r + 1). 2 - i.nh l´ V´ı du. 1.2.6 Theo D y 1.2.4, sˆo´ c´ac 2-ho´an vi. cu˙’a X = {a, b, c} l`a P (3, 2) = 3 · 2 = 6. S´au ho´an vi. n`ay l`a ab, ac, ba, bc, ca, cb. V´ı du. 1.2.7 C´o bao nhiˆeu c´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´o chu˙’ ti.ch, mˆo.t thu. k´ y v`a mˆo.t ˙ ’ thu qu˜y t`. . . u mˆo.t nh´om 10 ngu `o i? Ch´ ung ta cˆ`an d¯ˆe´m sˆo´ c´ac c´ach c´o th´u. tu.. cu˙’a 4 ngu.`o.i d¯u.o..c cho.n t` u. mˆo.t nh´om gˆ `om 10 . . - ngu `o i. Theo Di.nh l´ y 1.2.4 sˆo´ c´ac c´ach cho.n l`a P (10, 4) = 10 · 9 · 8 · 7 = 5040. Ch´ uy ung c´o thˆe˙’ suy ra kˆe´t qua˙’ tru..c tiˆe´p t` ´ rˇ`a ng c˜ u. nguyˆen l´ y t´ıch (ta.i sao?). 16
V´ı du. 1.2.8 Mˆo.t ngu.`o.i b´an h`ang rong cˆ ˆ ta c´o thˆe˙’ d¯i `an d¯i qua 7 d¯i.a d¯iˆe˙’m kh´ac nhau. Ong theo th´ . . u tu. bˆa´t k` y. C´o bao nhiˆeu h`anh tr`ınh kh´ac nhau? u. tˆa.p gˆ Sˆo´ c´ac h`anh tr`ınh c´o thˆe˙’ c´o l`a sˆo´ c´ac ho´an vi. t` `an tu˙’.: `om 7 phˆ P (7, 7) = 7! = 5040. Nˆe´u chˇa˙’ng ha.n ˆong ta muˆo´n t`ım h`anh tr`ınh c´o d¯oˆ. d`ai ngˇa´n nhˆa´t, ˆong ta cˆ `an t´ınh to´an v`a ˙ ’ ˙ ’ so s´anh 5040 h`anh tr`ınh ca thay!(?). Ta c´o thˆe˙’ viˆe´t P (n, r) = n(n − 1)(n − 2) · · · (n − r + 1) n(n − 1)(n − 2) · · · (n − r + 1)(n − r) · · · 2 · 1 = (n − r) · · · 2 · 1 n! = . (n − r)! - i.nh ngh˜ıa 1.2.5 X´et tˆa.p X := {x1 , x2 , . . . , xn } ch´ D u.a n phˆ `an tu˙’. phˆan biˆe.t. Mˆo.t r-tˆo˙’ ho..p cu˙’a tˆa.p X l`a mˆo.t bˆo. r phˆ `an tu˙’., khˆong phˆan biˆe.t th´u. tu..µ , lˆa´¶y t`u. tˆa.p n`ay. Sˆo´ c´ac r-tˆo˙’ ho..p n `om n phˆ cu˙’a tˆa.p gˆ `an tu˙’. phˆan biˆe.t k´y hiˆe.u l`a C(n, r) hay . r Ch´ ung ta s˜e x´ac d¯i.nh cˆong th´u.c cho C(n, r) bˇ`a ng c´ach d¯ˆe´m sˆo´ c´ac r-ho´an vi. cu˙’a tˆa.p gˆ `om ` ˙ ’. n phˆan tu theo hai c´ach. Th´ . ´ ˙ ’ . u nhˆa t, su du.ng cˆong th´ . u c P (n, r). C´ach th´ . ´ ´ u hai l`a d¯ˆem sˆo c´ac `an tu˙’. c´o liˆen quan v´o.i C(n, r). T` `om n phˆ r-ho´an vi. cu˙’a tˆa.p gˆ u. d¯o´ s˜e suy ra kˆe´t qua˙’. Ta c´o thˆe˙’ xˆay du..ng r-ho´an vi. cu˙’a tˆa.p n phˆ `an tu˙’. phˆan biˆe.t qua hai bu.´o.c liˆen tiˆe´p: D- `ˆau . tiˆen, cho.n mˆo.t r-tˆo˙’ ho. p cu˙’a X (tˆa.p con r phˆ . `an tu˙’ khˆong phˆan biˆe.t th´ . . u tu. ) v`a sau d¯o´ sˇa´p th´ u tu. n´o. Chˇa˙’ng ha.n, d¯ˆe˙’ xˆay du. ng mˆo.t 2-ho´an vi. cu˙’a {a, b, c, d} ta c´o thˆe˙’ cho.n 2-tˆo˙’ ho..p . . . v`a sau d¯´o sˇa´p th´ u. tu.. n´o. Theo nguyˆen l´ y t´ıch, sˆo´ c´ac r-ho´an vi. bˇ`a ng t´ıch cu˙’a sˆo´ c´ac r-tˆo˙’ . ho. p v`a sˆo´ c´ac c´ach sˇa´p th´ . . `an tu˙’.. T´ u tu. cu˙’a r phˆ u.c l`a P (n, r) = C(n, r)r!. Vˆa.y P (n, r) C(n, r) = . r! - i.nh l´ Do d¯´o theo D y 1.2.4 ta c´o - .inh l´ D y 1.2.6 Sˆo´ c´ac r-ho´ `an tu˙’. phˆan biˆe.t l`a an vi. cu˙’ a tˆa.p n phˆ n! C(n, r) = , r ≤ n. (n − r)!r! 17
× × × × ×....... ... ... .. ... . × × × × × ....................................... .... ... ... ... ... .. × × × × .......................................................................... .... ... × ... ... ... ... × × ... ... × × × ... ... ... ... .. × × ...................................... × × × H`ınh 1.1: V´ı du. 1.2.9 C´o bao nhiˆeu c´ach cho.n 5 ngu.`o.i t` u. 10 ngu.`o.i d¯ˆe˙’ lˆa.p th`anh mˆo.t d¯oˆ. i b´ong (khˆong phˆan biˆe.t th´. . u tu. )? Cˆau tra˙’ l`o.i l`a bˇa` ng sˆo´ tˆo˙’ ho..p chˆa.p 5 cu˙’a 10 phˆ `an tu˙’. 10! C(10, 5) = = 252. 5!5! `om hai ngu.`o.i n˜ V´ı du. 1.2.10 C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`oˆng gˆ u. v`a ba ngu.`o.i nam t`. . . u mˆo.t nh´om nˇam ngu `o i n˜. . . u v`a s´au ngu `o i nam? Sˆo´ c´ach cho.n hai ngu.`o.i n˜ u. v`a ba ngu.`o.i nam tu.o.ng u ´.ng l`a C(5, 2) = 10 v`a C(6, 3) = 20. Hˆo.i d¯`oˆng d¯u.o..c xˆay du..ng qua hai bu.´o.c liˆen tiˆe´p: Cho.n ngu.`o.i n˜ u.; cho.n ngu.`o.i nam. Theo nguyˆen l´ y t´ıch, tˆo˙’ng sˆo´ c´ac hˆo.i d¯`oˆng l`a 10 · 20 = 200. u.a ch´ınh x´ac bˆo´n bit 1? V´ı du. 1.2.11 C´o bao nhiˆeu chuˆo˜i t´am bit ch´ Mˆo.t chuˆo˜i t´am bit ch´u.a bˆo´n bit 1 d¯u.o..c x´ac d¯i.nh duy nhˆa´t ngay khi ch´ ung ta biˆe´t c´ac bit ` . ` ˙ ’ . ˙ ’. n`ao bˇa ng 1. Nhu ng d¯iˆeu n`ay c´o thˆe thu. c hiˆe.n bo i C(8, 4) c´ach. V´ı du. 1.2.12 C´o bao nhiˆeu h`anh tr`ınh t` u. g´oc du.´o.i bˆen tr´ai cu˙’a mˆo.t b`an c`o. vuˆong k´ıch thu.´o.c n × n d¯ˆe´n g´oc trˆen bˆen pha˙’i nˆe´u ch´ ung ta chı˙’ d¯i theo c´ach sang pha˙’i v`a lˆen trˆen? Mˆo.t h`anh tr`ınh nhu vˆa.y trˆen b`an c`o 4 × 4 d¯u o..c cho trong H`ınh 1.1. . . . Mˆo˜i h`anh tr`ınh c´o thˆe˙’ d¯u.o..c mˆo ta˙’ bo˙’.i mˆo.t chuˆo˜i d¯oˆ. d`ai 2n cu˙’a n k´ y tu.. R v`a n k´ y tu.. U. Chˇa˙’ng ha.n, h`anh tr`ınh trong H`ınh 1.1 tu.o.ng u ´.ng chuˆo˜i RU U RRU RU. Mˆo.t chuˆo˜i nhu. vˆa.y c´o thˆe˙’ nhˆa.n d¯u.o..c bˇ`a ng c´ach cho.n n vi. tr´ı d¯ˆo´i v´o.i R (khˆong phˆan biˆe.t th´ u. tu..) trong sˆo´ 2n vi. tr´ı cho ph´ep cu˙’a chuˆo˜i v`a sau d¯´o ch`en n k´ . y tu. U v`ao nh˜ . u ng vi. tr´ı c`on la.i. Do d¯´o sˆo´ h`anh tr`ınh l`a C(2n, n). 18
B` ai tˆ a.p 1. C´o bao nhiˆeu ho´an vi. cu˙’a a, b, c, d? Liˆe.t kˆe c´ac ho´an vi. n`ay. 2. C´o bao nhiˆeu 3-ho´an vi. cu˙’a a, b, c, d? Liˆe.t kˆe c´ac ho´an vi. n`ay. 3. C´o bao nhiˆeu ho´an vi., 5-ho´an vi. cu˙’a 11 d¯oˆ´i tu.o..ng kh´ac nhau? 4. C´o bao nhiˆeu c´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´o chu˙’ ti.ch v`a mˆo.t thu. k´ u. mˆo.t nh´om y t` . . 11 ngu `o i? 5. C´o bao nhiˆeu c´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´o chu˙’ ti.ch, mˆo.t kˆe´ to´an v`a mˆo.t thu. k´ y t`. . . u mˆo.t nh´om 12 ngu `o i? 6. C´o bao nhiˆeu chuˆo˜i c´o phˆan biˆe.t th´ u. tu.. d¯u.o..c ta.o ra t` u. c´ac k´ y tu.. ABCDE nˆe´u: (a) Ch´u.a chuˆo˜i con ACE. (b) Ch´u.a c´ac k´y tu.. ACE theo th´ u. tu.. t`uy y ´. (c) Ch´u.a c´ac chuˆo˜i con DB v`a AE. (d) Ch´u.a hoˇa.c chuˆo˜i con AE hoˇa.c EA. y tu.. A xuˆa´t hiˆe.n tru.´o.c k´ (e) K´ y tu.. D. Chˇa˙’ng ha.n BCAED, BCADE. (f) Khˆong ch´ u.a c´ac chuˆo˜i con AB, CD. y tu.. A xuˆa´t hiˆe.n tru.´o.c k´ (g) K´ y tu.. C v`a C xuˆa´t hiˆe.n tru.´o.c E. - ˇa.t X := {a, b, c, d}. 7. D (a) T`ım sˆo´ c´ac 3-tˆo˙’ ho..p cu˙’a X. Liˆe.t kˆe c´ac tˆo˙’ ho..p n`ay. (b) T`ım mˆo´i quan hˆe. gi˜ u.a c´ac 3-tˆo˙’ ho..p v`a 3-ho´an vi. cu˙’a X. `om ba ngu.`o.i t` 8. C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`oˆng gˆ u. nh´om 11 ngu.`o.i? `om bˆo´n ngu.`o.i t` 9. C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`oˆng gˆ u. nh´om 12 ngu.`o.i? `om s´au ngu.`o.i nam v`a ba˙’y ngu.`o.i n˜ 10. Mˆo.t cˆau la.c bˆo. gˆ u.. (a) C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`ˆong gˆ`om nˇam ngu.`o.i? (b) C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`ˆong gˆ`om ba nam v`a bˆo´n n˜ u.? `om bˆo´n ngu.`o.i v`a ´ıt nhˆa´t mˆo.t n˜ (c) C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`ˆong gˆ u.? (d) C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`ˆong gˆ`om bˆo´n ngu.`o.i v´o.i nhiˆ `eu nhˆa´t mˆo.t nam? `om bˆo´n ngu.`o.i c´o ca˙’ nam v`a n˜ (e) C´o bao nhiˆeu c´ach cho.n mˆo.t hˆo.i d¯`ˆong gˆ u.? u.a ch´ınh x´ac ba bit 0? 11. (a) C´o bao nhiˆeu chuˆo˜i 8 bit ch´ u.a ba bit 0 v`a 5 bit 1? (b) C´o bao nhiˆeu chuˆo˜i 8 bit ch´ u.a ´ıt nhˆa´t hai bit 0? (c) C´o bao nhiˆeu chuˆo˜i 8 bit ch´ 19
12. Mˆo.t cu˙’.a h`ang c´o 50 m´ay t´ınh trong d¯o´ c´o bˆo´n bi. ho˙’ng. (a) C´o bao nhiˆeu c´ach cho.n bˆo´n m´ay t´ınh? (b) C´o bao nhiˆeu c´ach cho.n bˆo´n m´ay t´ınh khˆong ho˙’ng? (c) C´o bao nhiˆeu c´ach cho.n bˆo´n m´ay t´ınh trong d¯´o c´o hai chiˆe´c bi. ho˙’ng? (d) C´o bao nhiˆeu c´ach cho.n bˆo´n m´ay t´ınh trong d¯´o c´o ´ıt nhˆa´t mˆo.t chiˆe´c bi. ho˙’ng? 13. X´et mˆo.t h`anh tr`ınh trˆen b`an c`o. k´ıch thu.´o.c m × n t` u. g´oc tr´ai bˆen du.´o.i d¯ˆe´n g´oc trˆen bˆen pha˙’i v`a theo hu.´o.ng hoˇa.c sang pha˙’i hoˇa.c lˆen trˆen. (a) Sˆo´ h`anh tr`ınh c´o thˆe˙’ l`a bao nhiˆeu? ´ du.ng d¯ˆe˙’ ch´ (b) Ap u.ng minh d¯aˇ˙’ ng th´ u.c n X C(k + m − 1, k) = C(m + n, m). k=0 14. Ch´u.ng minh rˇa` ng sˆo´ c´ac chuˆo˜i bit d¯oˆ. d`ai n ≥ 4 ch´ u.a ch´ınh x´ac hai lˆ `an xuˆa´t hiˆe.n cu˙’a chuˆo˜i bit 10 l`a C(n + 1, 5). 15. Ch´u.ng minh rˇ`a ng sˆo´ c´ac chuˆo˜i bit d¯ˆo. d`ai n ch´ u.a ch´ınh x´ac k bit 0 sao cho hai bit 0 khˆong xuˆa´t hiˆe.n liˆen tiˆe´p l`a C(n − k + 1, k). u.ng minh rˇa` ng t´ıch cu˙’a k sˆo´ nguyˆen liˆen tiˆe´p chia hˆe´t cho k!. 16. Ch´ 17. Ch´ u.ng minh rˇ`a ng c´o (2n − 1)(2n − 3) · . . . · 3 · 1 c´ach cho.n n cˇa.p t` u. 2n phˆ `an tu˙’. phˆan biˆe.t. 18. Gia˙’ su˙’. c´o n d¯ˆo´i tu.o..ng trong d¯o´ c´o r d¯oˆ´i tu.o..ng phˆan biˆe.t v`a n − r l`a d¯`ˆong nhˆa´t. Ch´ u.ng minh cˆong th´ u.c P (n, r) = r!C(n, r) bˇ`a ng c´ach d¯ˆe´m sˆo´ c´o phˆan biˆe.t th´ u. tu.. cu˙’a n d¯ˆo´i tu.o..ng theo hai c´ach: +D u. tu.. c´ac vi. tr´ı cu˙’a r d¯ˆo´i tu.o..ng phˆan biˆe.t. - `ˆau tiˆen d¯ˆe´m sˆo´ c´o phˆan biˆe.t th´ +D u. tu.. c´ac vi. tr´ı cu˙’a n − r d¯ˆo´i tu.o..ng d¯`ˆong nhˆa´t. - `ˆau tiˆen d¯ˆe´m sˆo´ c´o phˆan biˆe.t th´ 1.3 C´ ac thuˆ a.t to´ an sinh ra ho´ an vi. v` o˙’ ho..p a tˆ Nh´om nha.c rock cu˙’a tru.`o.ng D - a.i ho.c D - `a La.t c´o n b`ai h´at cˆ `an ghi lˆen mˆo.t d¯˜ıa CD. C´ac b`ai h´at chiˆe´m th`o i gian (t´ınh bˇ`a ng giˆay) tu.o.ng u . ´.ng l`a t1 , t 2 , . . . , t n . (1.1) 20