Chuyên đề Đại số tổ hợp

sách. 
 + Số cách chọn 6 sách từ 12 sách là: 
 + Số cách chọn sao cho không còn sách văn: 
 + Số cách chọn sao cho không còn sách nhạc: 
 + Số cách chọn sao cho không còn sách hội hoạ: 
 + Số cách chọn cần tìm là: 665280 – 85680 = 579600
 Ban cán sự lớp gồm 3 người trong lớp không có sự sắp xếp
Mỗi một ban cán sự 3 người là một tập con 3 phần tử của tập hợp 40 học sinh của lớp. Vậy có: cách lập ban cán sự lớp 3 người.
Có cách chọn 1 học sinh nam và cách chọn 2 học sinh nam. 
Do đó có cách lập một ban cán sự lớp gồm 1 nam và 2 nữ
Có cách chọn 3 nữ sinh nên có 455 cách lập ban cán sự lớp 3 người toàn nữ. Dó đó có: 9880 – 455 = 9425 cách lập ban cán sự 3 người ma trong đó có ít nhất một nam
Ví dụ 7
 Nhận xét: Việc phân công vào 1 tỉnh không có sự sắp xếp
Có cách phân công các thanh niên tình nguyện về tỉnh thứ nhất. Với mỗi cách phân công các thanh niên tình nguyện về tỉnh thứ nhất thì có cách phân công các thanh niên tình nguyện về tỉnh thứ 2. Với mỗi cách phân công các thanh niên tình nguyện về tỉnh thứ 1 và tỉnh thứ 2 thì có cách phân công các thanh niên tình nguyện về tỉnh thứ 3. 
Số cách phân công các thanh niên tình nguyện về 3 tỉnh thoả mãn yêu cầu bài toán là: 
 Bạn Hoa có 2 cách chọn bông cắm bình như sau:
Cách 1: Chọn 2 bông hồng bạch và 3 bông hồng nhung
+ Số cách chọn 2 bông hồng bạch trong 10 bông: 
+ Với mỗi cách chọn 2 bông hồng bạch lại có cách chọn 3 bông hồng nhung trong 10 bông. 
Vậy cách 1 có . cách chọn bông. 
Cách 2: Chọn 3 bông hồng bạch và 2 bông hồng nhung. Lập luận tương tự như trên, ta cũng có . cách chọn bông. 
Vậy bạn Hoa có số cách chọn bông là: cách chọn
 Nhận xét: Nội dung đề không phụ thuộc vào việc sắp xếp thứ tự câu hỏi.
Mỗi đề kiểm tra phải có số câu dễ là 2 hoặc 3, nên có các trường hợp sau:
 - Đề có 2 câu dễ, 2 câu trung bình, 1 câu khó, thì số cách chọn là: 
 - Đề có 2 câu dễ, 1 câu trung bình, 2 câu khó, thì số cách chọn là:
 - Đề có 3 câu dễ, 1 câu trung bình, 1 câu khó, thì số cách chọn là: 
Vì các cách chọn trên đôi một khác nhau, nên số đề kiểm tra có thể lập được là:
Ví dụ 7
	23625 + 10500 + 22750 = 56875
 B/ Bài toán đếm số phương án có liên quan đến hình học.
 Cho 7 điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng
a. Có bao nhiêu đường thẳng mà mỗi đường thẳng đi qua 2 trong 7 điểm nói trên?
b. Có bao nhiêu tam giác với các đỉnh là 3 trong 7 điểm nói trên ?
 Tìm số giao điểm tối đa của :
10 đường thẳng phân biệt?
6 đường tròn phân biệt?
10 đường thẳng và 6 đường tròn trên?
 a. Có bao nhiêu đường chéo trong một đa giác lồi n cạnh?
b. Có bao nhiêu tam giác có đỉnh là đỉnh của đa giác n cạnh? Trong đó có bao nhiêu tam giác có cạnh không phải là cạnh của đa giác n cạnh ?
 (ĐH, CĐ Khối B – 2003)
Cho đa giác đều nội tiếp đường tròn (O). Biết rằng số tam giác có đỉnh là 3 trong 2n điểm nhiều gấp 20 lần số hình chữ nhật có các đỉnh là 4 trong 2n điểm , tìm n. 
 (ĐHCSND - 1999 - 2000):Cho tam giác ABC, xét tập hợp 4 đường thẳng song song với AB, 5 đường thẳng song song với BC và 6 đường thẳng song song với AC. Hỏi các đường thẳng này tạo được:
Bao nhiêu tam giác ?
 b. Bao nhiêu hình thang ( Không kể hình bình hành ) ?
 c. Bao nhiêu hình bình hành ?
 ( CĐSP -A- dự bị - 02 – 02 ): Cho đa giác lồi n cạnh. Xác định n để đa giác có số đường chéo gấp đôi số cạnh ?
 ( ĐHNT- 01 – 02 ):Trong mặt phẳng cho thập giác lồi . Xét tất cả các tam giác mà 3 đỉnh của nó là đỉnh của thập giác. Hỏi trong số các tam giác đó có bao nhiêu tam giác mà 3 cạnh của nó đều không phải là cạnh của thập giác ?
 ( HVNH- D- 2000 ):Trong mặt phẳng cho đa giác đều (H) có 20 cạnh. Xét các tam giác mà 3 đỉnh của nó lấy từ các đỉnh của (H).
Có tất cả bao nhiêu tam giác như vậy ? Có bao nhiêu tam giác có đúng 2 cạnh là cạnh của (H) ? 
Có bao nhiêu tam giác có đúng 1 cạnh là cạnh của (H) ? 
Có bao nhiêu tam giác không có cạnh nào là cạnh của (H) ?
 Cho 2 đường thẳng song song.Trên đường thứ nhất có 10 điểm. Trên đường thứ hai có 20 điểm. Có bao nhiêu tam giác tạo bởi các điểm đã cho ?
 (ĐHCĐ - B - 2002):Cho đa giác đều ( , n nguyên ) nội tiếp đường tròn ( 0). Biết rằng số tam giác có các đỉnh là 3 trong 2n điểm nhiều gấp 20 lần số hình chữ nhật có các đỉnh là 4 trong 2n điểm , tìm n.
Lời giải:
 Bài toán đếm số phương án có liên quan đến hình học
 a. Mỗi cặp điểm không kể thứ tự, trong 7 điểm đã cho xác định một đường thẳng và ngược lại. Vậy, số đường thẳng đi qua 2 trong 7 điểm nói trên bằng: 
 đường thẳng. 
 b. Mỗi bộ 3 điểm không kể thứ tự, trong 7 điểm đã cho xác định một tam giác và ngược lại. Vậy số tam giác có đỉnh là 3 trong 7 điểm nói trên bằng:
 a. Hai đường thẳng phân biệt có tối đa 1 giao điểm. Số giao điểm tối đa của 10 đường thẳng phân biệt là số tổ hợp chập 2 của 10, do đó bằng:
 điểm
 b. Hai đường tròn phân biệt có tối đa 2 giao điểm. Số giao điểm tối đa của 6 đường tròn phân biệt gấp 2 lần số tổ hợp chập 2 của 6, do đó bằng:
 điểm. 
 c. Một đường thẳng cắt một đường tròn tối đa tại 2 điểm. Do đó số giao điểm tối đa của 10 đường thẳng phân biệt với 6 đường tròn phân biệt bằng:
=120 điểm
	Khi đó, số các giao điểm bằng: 45 + 30 +120 = 195 điểm
 a. Ta có: * Mỗi đa giác lồi n cạnh thì có n đỉnh. 
 *Mỗi đoạn thẳng nối 2 đỉnh bất kỳ, không kể thứ tự, thì hoặc là 1 cạnh, hoặc là một đường chéo của đa giác đó. 
 Vậy số đường chéo của đa giác n cạnh bằng: 
 b. Số tam giác có đỉnh là đỉnh của đa giác n cạnh là số tổ hợp n chập 3:
	Số tam giác có ít nhất 1 cạnh là cạnh của đa giác gồm 2 loại:
 * Số tam giác chỉ có 1 cạnh bằng 
 * Số tam giác 2 cạnh bằng 
Suy ra, số tam giác có 1 hoặc 2 cạnh của đa giác là: 	
Vậy, số tam giác có cạnh không phải là đa giác là:
 Số tam giác có các đỉnh là 3 trong 2n đỉểm là 
Gọi đường chéo của đa giác đều đi qua tâm đường tròn (O) là đường chéo lớn thì đa giác đã cho có n đường chéo lớn. 
Mỗi hình chữ nhật có các đỉnh là 4 trong 2n điểm có các đường chéo là 2 đường chéo lớn. Ngược lại, với mỗi cặp đường chéo lớn ta có các đầu mút của chúng là 4 đỉnh của 1 hình chữ nhật. Vậy số hình chữ nhật nói trên bằng số cặp đường chéo lớn của đa giác , tức . 
Theo giả thiết thì: 
 .
 C/ Bài toán đếm số phương án liên quan đến số tự nhiên
êGhi nhớ:
Khi giải bài toán đếm liên quan đến số tự nhiên ta cần lưu ý:
	· Nắm vững qui tắc cộng nhân.
	· Ta thường gọi số tự nhiên cần tìm là sau đó căn cứ vào đầu bài đi chọn tờng chữ số một.Số nào yêu cầu cao thì chọn trước.
	· Khi chọn các chữ số cần phân tích câu văn đầu bài cặn kẽ, nắm chắc bản chất của từng đối tượng từ đó tìm tập xác định và các khả năng có thể.
	· Cẩn thận khi có số 0.
	· Phải luôn luôn nghĩ tới phần bù, nếu phần bù đơn giản hơn ta tìm phần bù trước.
êBài tập:
 ( ĐHQG HCM - 99) Với các số 1,2,5,7,8 có thể lập được bao nhiêu số gồm 3
 chữ số phân biệt thoả mãn điều kiện:
	a. Là 1 số chẵn. b. Là 1 số nhỏ hơn hoặc bằng 278.
	c. Là 1 số chẵn và nhỏ hơn hoặc bằng 278.
 Xét một dãy số gồm 7 chữ số ( Mỗi chữ số được chọn từ các số 0, 1 ,2, 3, 4,9 ) thoả mãn tính chất:
 - Chữ số ở vị trí thứ 3 chẵn.
 - Chữ số ở vị trí cuối cùng chia hết cho 5.
 - Các chữ số ở vị trí thứ 4, 5, 6 đôi một khác nhau. Hỏi có tất cả bao nhiêu dãy số như vậy ?
 ( ĐHCSND – 99- 99):với 10 chữ số từ 1-->9 có thể lập được thành bao nhiêu chữ số gồm 5 chữ số khác nhau?
 ( ĐH Đà Lạt – D): có 10 chữ số khác nhau 
Lập bao nhiêu chữ có 5 chữ cái ?
Lập bao nhiêu chữ có 5 chữ cái khác nhau?
 (ĐHSPV–Đ28-99-00): Cho 8 chữ số 0, 1, 2, 3, 4, 5, 6, 7. Từ 8 chữ số trên có thể lập được bao nhiêu số, mỗi số gồm 4 chũ số, đôi một khác nhau và chia hết cho 10.
 (ĐHSPV - B - 99- 00): Có 5 số tự nhiên 1, 2, 3, 4, 5 . Hỏi có bao nhiêu số có 3 chữ số đôi một khác nhau tạo thành từ 5 số đã cho?
 ( ĐHYHN – 99 – 00)
Có thể lập đợc bao nhiêu số chẵn có năm chữ số khác nhau lấy từ các số 0, 2, 3, 6, 9, 
 ( CĐSPHN - Đ36) 
Có 5 miếng bìa, trên mỗi miếng có ghi 1 trong 5 chữ số 0, 1, 2, 3, 4. Lấy 3 miếng từ 5 miếng bìa này đặt lần lợt cạnh nhau từ trái qua phải để đợc các số gồm 3 chữ số. Hỏi lập đợc bao nhiêu số có ngiã gồm 3 chữ số và trong đó có bao nhiêu số chẵn.
Chú ý: các chữ số đôi một khác nhau do mỗi số chỉ chỉ có một miếng bìa.
 (ĐHQGHCM - Đ3 – 00 – 01)
	1. Có bao nhiêu số chẵn gồm 6 chữ số khác nhau đôi một trong đó chữ số đầu tiên là chữ số lẻ?
	2. Có bao nhiêu số gồm 6 chữ số khác nhau đôi một trong đó có đúng 3 chữ số lẻ và 3 chữ số chẵn.
( ĐHSPHN2 - Đ8):
	Có thể lập đợc bao nhiêu số gồm 8 chữ số từ ctrong đó các chữ số 1 và 6 đều có mặt 2 lần các chữ số khác có mặt một lần.
 Với các số 0, 1, 2, 3, 4, ,5 ta có thể lập đợc bao nhiêu số gồm 8 chữ số trong đó số 1 có mặt 3 lần mỗi số khác có mặt 1 lần 
 ( ĐHHuế – 00 – 01 - Đ26) Cho các chữ số 0, 1, 2, 3, 4, 5 từ các chữ số đã cho lập đợc:
	1. Bao nhiêu chữ số chẵn có 4 chữ số và 4 chữ số đó khác nhau đôi một?
	2. Bao nhiêu chữ số chia hết cho 5, có 3 chữ số và 3 chữ số đó khác nhau đôi một.
	3. Bao nhiêu chữ số chia hết cho 9, có 3 chữ số và 3 chữ số đó khác nhau đôi một.
.
 Ngời ta viết các số có 6 chữ số bằng các chữ số 1, 2, 3, 4, 5 nh sau: Trong mỗi số đợc viết có một chữ số xuất hiện 2 lần còn các chữ số còn lại xuất hiện 1 lần. Hỏi có bao nhiêu số nh vậy.
 Có bao nhiêu số tự nhiên có 7 chữ số đợc viết bởi duy nhất 3 chữ số 1, 2, 3, trong đó chữ số 2 xuất hiện 2 lần.
Tự luyện:
 Có bao nhiêu số tự nhiên có 3 chữ số ?
 Cho A = {1,3,5,6,8}. 
 Có bao nhiêu số tự nhiên gồm 4 chữ số lấy từ các chữ số trong tập A ? 
 Cho A = {0,1,2,3,5,7,9}. 
 Từ tập A có bao nhiêu số tự nhiên gồm 4 chữ số đôi 1 khác nhau.
 Với tập E = {1,2,3,4,5,6,7} có thể lập được bao nhiêu số gồm 5 chữ
 số phân biệt và:
	a. Trong đó có chữ số 7.
	b. Trong đó có chữ số 7 và chữ số hàng ngàn luôn là chữ số 1.
 Với 5 chữ số 1,2,3,4,5 có thể lập được bao nhiêu số gồm 5 chữ số đôi 1 khác nhau:
	a. Không bắt đầu từ chữ số 1
Ví dụ 3 
	b. Không bắt đầu từ 123.
 Cho E = {0,1,2,3,4,5,6,7}. Có thể lập được bao nhiêu số gồm 5 chữ số đôi 1 khác nhau lấy từ E trong mỗi trường hợp sau:
	 a. Là số chẵn.
	 b. Một trong 3 số đ