108 Bài tập Toán tổ hợp

Sigma - MATHS MệC LệC

Mửc lửc

1 Kián thực côn bÊn 2

2 CĂc b i toĂn ám. 4

3 Biºu ç Ven - Logic 6

4 Nguyản lỵ Dirichlet 7

5 CĂc b i toĂn trản b n cớ 8

6 Tờ hủp - Hẳnh hồc 10

7 Trỏ chìi Games 11

8 Qui nÔp 12

9 Mini Combinatorics 13

¢ sỷa chỷa v bờ sung nhúng lội chẵnh tÊ bÔn ồc gâp þ! ChƠn th nh cÊm ìn cĂc bÔn!

1

ThuVienDeThi.com

Sigma - MATHS 1 KI˜N THÙC C‹N BƒN

1 Kián thực côn bÊn

1. ành nghắa: n phƯn tỷ khĂc nhau cừa mởt têp hủp ữủc xáp th nh h ng ữủc gồi l hoĂn và khổng l°p ( hoĂn và) cừa n phƯn tỷ.

ành lỵ: Số cĂc hoĂn và khổng l°p lÔi cừa n phƯn tỷ kỵ hiằu l Pn. Pn = 1.2.3. . . n= n! (quy ành 0!=1)

2. ành nghắa: Náu mởt têp gỗm n phƯn tỷ sao cho giúa chúng câ k1, k2, . . . , kr(k1 + k2 + . . . + kr ≤n) nhõm cĂc phƯn tỷ bơng nhau. Khi â mởt sưp xáp n phƯn tỷ n y v o mởt h ng ữủc gồi l giao hoĂn l°p cừa bở n phƯn tỷ n y.

ành lỵ: Náu mởt têp gỗm n phƯn tỷ sao cho giúa chúng câ k1, k2, . . . , kr(k1 +k2 +. . .+ kr ≤n) nhõm cĂc phƯn tỷ bơng nhau. Kỵ hiằu số giao hoĂn l°p cừa nhõm n phƯn tỷ n y l Pn(k1, k2, . . . , kr) . Khi â

Pn(k1, k2, . . . , kr) = n! k1!k2! . . . kr!

3. ành nghắa: Náu cho trữợc n phƯn tỷ khĂc nhau, tứ â chồn ra k phƯn tỷ, v sưp xáp k phƯn tỷ n y th nh h ng thẳ ta nhên ữủc ch¿nh hủp khổng l°p bêc k cừa n phƯn tỷ.

ành lỵ: Kỵ hiằu số cĂc ch¿nh hủp khổng l°p bêc k cừa n phƯn tỷ l Vn k , khi â

Vn k = n! (n −k)!

4. ành nghắa: Náu cho trữợc n phƯn tỷ, tứ â chồn ra k phƯn tỷ sao cho mội phƯn tỷ câ thº chồn nhiãu lƯn, v sưp xáp k phƯn tỷ ữủc chồn n y th nh h ng thẳ ta nhên ữủc â l ch¿nh hủp l°p bêc k cừa n phƯn tỷ.

ành lỵ: Kỵ hiằu số cĂc ch¿nh hủp khổng l°p bêc k cừa n phƯn tỷ l Wn k khi â

Wn k = nk

5. ành nghắa: Náu cho trữợc n phƯn tỷ khĂc nhau, tứ â chồn ra k phƯn tỷ sao cho mội phƯn tỷ ch¿ ữủc chồn mởt lƯn ( khổng quan tƠm án xáp hÔng cĂc phƯn tỷ), thẳ ta nhên ữủc tờ hủp khổng l°p bêc k cừa n phƯn tỷ.

ành lỵ: Kỵ hiằu số cĂc tờ hủp khổng l°p bêc k cừa n phƯn tỷ l Cn k , khi â

Cn k = n! (n −k)!

2

ThuVienDeThi.com

Sigma - MATHS 1 KI˜N THÙC C‹N BƒN

6. ành nghắa: Náu cho trữợc n phƯn tỷ khĂc nhau, tứ â chồn ra k phƯn tỷ sao cho mội phƯn tỷ câ thº ữủc chồn nhiãu lƯn ( khổng quan tƠm án xáp hÔng cĂc phƯn tỷ), thẳ ta nhên ữủc tờ hủp l°p bêc k cừa n phƯn tỷ.

ành lỵ: Kỵ hiằu số cĂc tờ hủp l°p bêc k cừa n phƯn tỷ l Dn k , khi â

Dn k = (n + k −1)!

k!(n −1)! = Ck n+k−1

CĂc nguyản lỵ cỡ bÊn.

Cho X l mổt têp húu hÔn. A, B l cĂc têp con cừa X.

Nguyản lỵ bò trứ : |X\A| = |X| −|A| Nguyản lỵ cởng: Náu A v B l hai têp khổng giao nhau (A ∩B = ⊘) thẳ

|A ∪B| = |A| + |B|

Nguyản lỵ nhƠn: |A.B| = |A|.|B| Nguyản lỵ Thảm bợt: |A ∪B| = |A| + |B| −|A ∩B|

3

ThuVienDeThi.com

Sigma - MATHS 2 CC B€I TON ˜M.

2 CĂc b i toĂn ám.

1. Tứ nôm chú số 1, 2, 3, 4, 5 mội chú số sỷ dửng mởt lƯn viát tĐt cÊ cĂc số câ 5 chú số. a) Náu º cĂc số theo thù tỹ tông dƯn, thẳ số n o ùng thù 100 ? b) Số 42531 ùng thù tỹ bao nhiảu? c) Tẵnh têng tĐt cÊ cĂc số n y .

2. Viằc n o câ khÊ nông xÊy ra lợn hìn giúa: Tung xúc xưc ữủc số 6, hay tung hai lƯn liản tiáp ữủc cũng mởt số ?

3. 10 hồc sinh rút thôm º nhên 4 quyºn sĂch,mội hồc sinh khổng ữủc nhiãu quĂ 1 quyºn. Họi câ bao nhiảu cĂch câ thº xây ra?

4. Câ bao nhiảu số câ 4 chú số m giúa cĂc chú số câ chú số 0?

5. Tổi nghắ mởt số nguyản x vợi 0 < x < 17. Họi cƯn ẵt nh§t bao nhiảu cƠu họi m ch¿ ữủc ph²p trÊ lới óng - sai º ngữới ta xĂc ành ữủc tổi nghắ án số n o?

6. Câ bao nhiảu cĂch iãn cĂc số 1,2,. . . ,8 v o giúa cĂc d§u quan hằ . . . .<. . . .<. . . .<. . . .>. . . .>. . . .>. . . .>. . . . ? 7. Tổi nghắ hai số giúa 1 v 10. Họi phÊi cƯn bao nhiảu cƠu họi ( dÔng óng sai) º bÔn câ thº biát hai số tổi nghắ l gẳ?

8. Trản b n cớ 8x8 câ bao nhiảu hẳnh chú nhêt?

9. Trản giĂ câ 10 quyºn sĂch. Câ bao nhiảu cĂch º l§y xuống 3 quyºn sĂch khổng câ hai quyºn n o ùng cÔnh nhau?

10. Câ bao nhiảu số câ ba chú số sao cho chú số ð giúa lợn hìn chú số ùng Ưu v ùng cuối?

11. Câ bao nhiảu số abc ( ba chú số) sao cho b<a+c, c<b+a, a< b+c ?

12. Câ bao nhiảu cĂch i lản mởt cƯu thang 8 bêc …