BẢNG PHÂN CÔNG CÔNG VIỆC
Stt Họ và Tên Công việc
Chữ
ký
Nhận xét của GV
1 Trần Bá Định Chương I
2 Trương Thị Kim Ngọc Chương II
3 Huỳnh Thị Phấn Chương III
4 Phạm Thị Quý Chương III
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
MỤC LỤC
Trang

MỞ ĐẦU
Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc chuyên
nghiên cứu sự sắp xếp các đối tượng.Thông thường các phần tử này là hữu hạn
và việc phân bố chúng phải thoả mãn những điều kiện nhất định nào đó, tùy theo
yêu cầu của bài toán cần nghiên cứu. Chủ đề này được nghiên cứu từ thế kỷ 17
khi những câu hỏi về tổ hợp được nêu ra trong những công trình nghiên cứu của
các trò chơi may rủi. Liệt kê, đếm, sắp xếp các đối tượng có những tính chất nào
đó là một phần quan trọng của lý thuyết tổ hợp.
Một bài toán khác trong lý thuyết tổ hợp là việc tạo ra các cách sắp xếp theo
một kiểu nào đó. Vấn đề này rất quan trọng trong các mô phỏng máy tính. Chúng
ta cũng sẽ đưa ra những thuật toán tạo các cách sắp xếp theo nhiều kiểu khác
nhau.
Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp
khổng lồ. Việc giải chúng đòi hỏi một khối lượng tính toán khổng lồ (có trường
hợp mất hàng chục năm). Vì vậy trong thời gian dài, khi mà các ngành toán học
như phép tính vi phân, phép tính tích phân, phương trình vi phân…phát triển như
vũ bảo, thì nó như nằm ngoài sự phát triển và ứng dụng của toán học. Tình thế
thay đổi từ khi xuất hiện máy tính và sự phát triển của toán học hữu hạn. Nhiều

nhau, đĩa nhỏ nằm trên đĩa lớn. Hãy chuyển các đĩa từ cọc thứ nhất sang cọc thứ
ba, sử dụng cọc trung gian thứ hai, sao cho luôn đảm bảo đĩa nhỏ trên đĩa lớn.
Hãy đếm số lần di chuyển đĩa. Tìm phương án di chuyển đĩa tối ưu.
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 3
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Ta có số lần di chuyển là: 2
n
– 1. Khi n = 64, ta có số lần di chuyển là :
18 446 744 073 709 551 615
2. Bài toán xếp n cặp vợ chồng
Bài toán này cũng do Lucas đưa ra vào năm 1891. Bài toán phát biểu như
sau : Có n cặp vợ chồng cần xếp vào bàn tròn sao cho không có cặp nào ngồi gần
nhau. Có bao nhiêu cách xếp như vậy ?
Từ yêu cầu của bài toán dẫn đến việc nghiên cứu một khái niệm quan
trọng là số phân bố và mãi đến năm 1934 mới có lời giải. Số cách xếp là :
2.n ! .U
n
trong đó U
n
là số phân bố. Ta có bảng giá trị sau nó nói lên sự bùng nổ tổ hợp
ghê gớm của số phân bố
n = 4 5 6 7 8 9 10 11
U
n
= 2 13 80 579 4 738 43 387 439 792 4 890 741
3. Bài toán đường đi quân ngựa trên bàn cờ
Cho bàn cờ vua với kích thước 8  8 = 64 ô. Tìm đường đi của quân ngựa
qua tất cả các ô, mỗi ô chỉ 1 lần, và quay về ô xuất phát. Người ta chứng minh
tổng quát được rằng : 7
Trên bàn cờ vua có số cạnh chẵn lớn hơn hoặc bằng 6 bao giờ cũng tồn tại

cột đầu là 1, 2,…, n. Bảng sau đây là hình vuông la tinh chuẩn cấp 7
1 2 3 4 5 6 7
2 3 4 5 6 7 1
3 4 5 6 7 1 2
4 5 6 7 1 2 3
5 6 7 1 2 3 4
6 7 1 2 3 4 5
7 1 2 3 4 5 6
Công thức tính số hình vuông la tinh đến nay vẫn còn bỏ ngơ. Tuy nhiên ta có
thể lập chương trình liệt kê tất cả hình vuông la tinh chuẩn. Dưới đây là một số
giá trị:
n = 1 2 3 4 5 6 7
l
n
= 1 1 1 4 56 9 408 16 942 080
(l
n
là số hình vuông la tinh chuẩn cấp n)
II. SƠ LƯỢC VỀ TOÁN HỌC TỔ HỢP
Qua các bài toán trên ta thấy bài toán tổ hợp rất đa dạng, liên quan tới
nhiều lĩnh vực khoa học và đời sống khác nhau. Nói một cách tổng quát thì lý
thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử của một hoặc nhiều
tập hợp, thỏa mãn một số điều kiện nào đó. Mỗi cách phân bố, sắp xếp như thế
gọi là một cấu hình tổ hợp.
1. Cấu hình tổ hợp
Cho các tập hợp A
1
, …, A
n
. Giả sử S là sơ đồ sắp xếp các phân tử của A

Ví dụ. Cho n là số nguyên dương
A là tập hợp n x n điểm: A = { [i, j] | i, j = 1, , n }
S là tập hợp 2n điểm trong A
R là điều kiện không có 3 điểm trong S thẳng hàng
Với
2 15n
≤ ≤
cấu hình tổ hợp tồn tại. Nhưng bài toán vẫn chưa có lời giải với
n>15.
2.2. Bài toán đếm
Nội dung bài toán đếm là trả lời câu hỏi “Có bao nhiêu cấu hình tổ hợp
thuộc dạng đang xét”. Phương pháp đếm cấu hình thường dựa vào một số quy
tắc, nguyên lí đếm và phân rã đưa về các cấu hình tổ hợp đơn giản. Khi việc xác
định chính xác số cấu hình tổ hợp gặp khó khăn, có thể ước lượng cận trên và cận
dưới của nó. Bài toán đếm được áp dụng vào những công việc như tính xác suất
hay tính độ phức tạp thuật toán
Ví dụ. Đếm số nghiệm nguyên dương của phương trình: x + y +z = 10.
2.3. Bài toán liệt kê
Các bài toán loại này nghiên cứu những thuật toán hiệu quả để xây dựng tất
cả các cấu hình tổ hợp đã cho. Nhiều vấn đề trong các lĩnh vực khác nhau thường
được đưa về bài toán liệt kê và kiểm tra xem các cấu hình tổ hợp có thỏa mãn
tính chất cho trước hay không ?
Ví dụ. Liệt kê tất cả các hoán vị của n phần tử.
2.4. Bài toán tối ưu tổ hợp
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 6
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Trong nhiều vấn đề, một cấu hình tổ hợp được gán một giá trị bằng số
(chẳng hạn như hiệu quả sử dụng hay chi phí thực hiện ). Khi đó bài toán tối ưu
tổ hợp nghiên cứu những thuật toán tìm cấu hình tổ hợp có giá trị tối ưu (lớn nhất
hoặc nhỏ nhất).

có thứ tự gồm k thành phần lấy từ n phần tử đã cho. Các thành phần có thể được
lặp lại.
Một chỉnh hợp lặp chập k của n có thể xem như một phần tử của tích Đề - các X
k
,
với X là tập n phần tử. Như vậy số tất cả các chỉnh hợp lặp chập k của n là:
AR(n,k) = n
k
Ví dụ 1. Tính số các dãy nhị phân có độ dài n:
Mỗi dãy nhị phân có độ dài n là một bộ có thứ tự gồm n thành phần được chọn
trong tập {0, 1}. Do đó số dãy nhị phân có độ dài n là: 2
n
Ví dụ 2.
Biển số ô tô có 6 chữ cái và 2 chứ cái đầu tiên trong 26 chữ cái (không dùng
chữ O và I). Hỏi số ô tô được đăng ký nhiều nhất là bao nhiêu?
Giải.
Gọi X là tập hợp các chữ cái nằm trong bảng đăng ký., suy ra X có 24 phần tử
(Vì không dùng chữ O và I). Vì vậy ta có AR(24, 2) = 24
2
cách chọn 2 chữ số đầu
tiên. Gọi Y là tập hợp các chữ số dùng tỏng bản đăng ký, suy ra Y có 10 phần tử.
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 7
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Vì vậy có AR(10, 6)= 10
6
cách chọn 6 chữ số. Do đó theo quy tắc nhân có tất cả
24
2
. 10
6

A(6,4) = 6.5.4.3=360

4.3. Hoán vị
Định nghĩa. Một hoán vị của n phần tử khác nhau là một cách sắp xếp thứ
tự các phần tử đó.
Hoán vị có thể coi như trường hợp riêng của chỉnh hợp không lặp chập k của n
trong đó k = n. Ta có số hoán vị là:
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 8
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
P(n) = n!
Ví dụ.
Có bốn người rủ nhau đi chụp ảnh là A, B C, D. Hãy tính xem có bao
nhiêu kiểu ảnh chụp mà tất cả bốn người đứng thành một hàng ?
Giải.
Số kiểu ảnh là một hoán vị của 4 người. Vậy số kiểu ảnh là 4! = 24.
4.4. Tổ hợp
Định nghĩa. Một tổ hợp chập k của n phần tử khác nhau là một bộ không
kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử đã cho. Nói cách khác ta
có thể coi một tổ hợp chập k của n phần tử khác nhau là một tập con có k phần tử
từ n phần tử đã cho.
Ký hiệu số tổ hợp chập k của n phần tử là C(n, k). Ta có
A(n, k) = C(n, k).k!
Suy ra
C(n, k) =
n!
k!(n k)!
−
Ví dụ 1.
a. Có n đội thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu trận đấu?
b. Có bao nhiêu xâu nhị phân độ dài 32 mà trong đó có đúng 6 số 1?

1
lần, số phần tử thứ 2 lặp n
2
lần, , số phần tử thứ k lặp n
k
lần là:
P( n; n
1
, n
2
, n
k
) =
1 2
!
! ! !
k
n
n n n
với n = n
1 +
n
2+
….+ n
k
Hệ quả. Giả sử tập S có n phần tử khác nhau, trong đó có n
1
phần tử kiểu 1, n
2
phần tử kiểu 2, , n

2
phần tử loại 2 vào hoán vị, còn lại n – n
1
– n
2
chỗ trống.
Tiếp tục đặt các phần tử loại 3, 4,…, k – 1 vào chỗ trống hoán vị. Cuối cùng có
C(n – n
1
- … - n
k-1
, n
k
) cách đặt n
k
phần tử loại k vào hoán vị. Theo quy tắc nhân
ta có các hoán vị là:
C(n, n
1
) . C(n- n
1
, n
2
) . … .C(n – n
1
- … - n
k-1
, n
k
) =

Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau là một nhóm không
phân biệt thứ tự gồm k phần tử trích từ n phần tử đã cho, trong đó các phần tử có
thể được lặp lại.
Định lý. Giả sử X có n phần tử khác nhau. Khi đó số tổ hợp lặp chập k từ
n phần tử của X, ký hiệu CR(n, k) là:
CR(n, k) = C(k + n - 1, n - 1) = C(k + n - 1, k).
Chứng minh.
Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n
−
1
thanh đứng và k ngôi sao. Ta dùng n
−
1 thanh đứng để phân cách các ngăn.
Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện
trong tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi:
* * | * | | * * *
mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần tử
thứ 3 và 3 phần tử thứ tư của tập hợp.
Mỗi dãy n
−
1 thanh và k ngôi sao ứng với một xâu nhị phân độ dài n + k
−
1
với k số 1. Do đó số các dãy n
−
1 thanh đứng và k ngôi sao chính là số tổ hợp
chập k từ tập n + k
−
1 phần tử. Đó là điều cần chứng minh
Ví dụ 1.

x
3
phần tử loại 3
Số bộ nghiệm là tổ hợp lặp chập 11 của 3. Số nghiệm là:
CR(3, 11) = C(3+11- 1, 3-1) = C(13, 2) = 78
3. Phân hoạch thứ tự tổ hợp
Định nghĩa. Cho X là tập n phần tử khác nhau, r
≤
n và
S X
⊂
có r phần
tử. Một phân hoạch {S
1
, S
2
, , S
k
} có thứ tự của S gọi là một phân hoạch thứ tự
tổ hợp chập r của X. Nếu r = n, thì gọi là phân hoạch thứ tự của X.
Cho các số nguyên dương n
1
, n
2
, , n
k
thoả
1 2

k

phần tử từ X \S
1
cho S
2
, có C(n
−
n
1
, n
2
) khả năng.

Bước k: Chọn n
k
phần tử từ
( )
1 2 1
\
k
X S S S
−
∪ ∪ ∪
cho S
k
, có
C(n
−
n
1
−

1
−
n
2
−

−
n
k
−
1
, n
k
)
=
)!!.(! !.
!
21
rnnnn
n
k
−
= P(n; n
1
, n
2
, , n
k
, n
−

, n
2
, , n
k
) được gọi là hệ số đa thức.
Ví dụ.
Có 17 sinh viên đi dạ hội bằng 5 xe khác nhau theo thứ tự có số chỗ ngồi
tương ứng là 4, 3, 3, 4, 1. Hãy xác định số cách chở 17 sinh viên bằng 5 xe, trong
đó có 2 sinh viên phải đi bằng phương tiện khác?
Giải.
Mỗi cách chở là một phân hoạch thứ tự tổ hợp chập 15 của 17 với số phần tử
trong mỗi tập con tương ứng là 4, 3, 3, 4, 1. Vì vậy số cách chở là:
C(17; 4, 3, 3, 4, 1) =
!2!.1!.4!.3!.3!.4
!17
= 8 576 568 000.
4. Phân hoạch không thứ tự
Định nghĩa. Cho X là tập n phần tử khác nhau, các số nguyên dương n
1
,
n
2
, , n
k
và p
1
, p
2
, , p
k

1
tập lực lượng n
1
, p
2
tập lực lượng
n
2
, , p
k
tập lực lượng n
k
là
( )
!! !
, ,, ,, ,,, ,;
21
2211
k
kk
ppp
nnnnnnnC
=
( ) ( ) ( )
k
p
kk
pp
npnpnp
n

tập lực
lượng n
2
, , p
k
tập lực lượng n
k
sẽ sinh ra p
1
!p
2
! p
k
! phân hoạch có thứ tự của
X với p
1
tập lực lượng n
1
, p
2
tập lực lượng n
2
, , p
k
tập lực lượng n
k
. Mặt khác
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 13
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
( )

!3
)4,4,4;12(C
=
( )
!3!4
!12
3
(phân hoạch không thứ tự).
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 14
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
CHƯƠNG III. ỨNG DỤNG
I. CẤU HÌNH TỔ HỢP CƠ BẢN
Bài toán 1. Bài toán đếm cách xếp chỗ
1. Một tổ sinh viên có 7 nam và 5 nữ xếp thành hàng dọc. Hỏi có bao nhiêu
cách xếp hàng để không có hai sinh viên nữ đứng gần nhau?
Giải. Mỗi cách xếp hàng tương ứng với một hoán vị của 7 (SV nam A1,
A2, ,A7) và một chỉnh hợp chập 5 (SV nữ) của 8 (khoảng trống ký hiệu bằng
dấu gạch ngang):
_A1_A2_A3_A4_A5_A6_A7_
Như vậy ta có tất cả
7!. A(8,5) = 5040 . 6720 = 33 868 800
cách xếp hàng.
Tổng quát.
Ta có thể đưa ra và giải bài toán tổng quát hơn cho bài trên: Cho tập A có m
phần tử khác nhau và tập B có n phần tử khác nhau. Hỏi có bao nhiêu cách xếp
m + n phần tử trên thành hàng ngang sao cho không có hai phần tử nào của B
đứng cạnh nhau
Giải. Xếp m phần tử của tập A lên hàng ngang có : m! cách. Để các phần
tử của tập B không đứng cạnh nhau ta xếp các phần tử của tập B vào khoảng giữa
các phần tử của tập A và 2 đầu. Có tổng cộng m + 1 vị trí nên số cách xếp là:

( 1; 1) ( , ) ( , )
( 1)!.( )!
m
C m k C m k C m k
k m k
−
− − + = +
− −
. ( , ) ( , ) . ( , )
k k m
C m k C m k C m k
m m
+
= + =
Chú ý rằng để có lời giải phải thoả m ≥ k .
Bài toán 2. Bài toán đếm số đường đi
Bài 1. Xét một bảng hình chữ nhật gồm m

n ô vuông. Hỏi có bao nhiêu
đường đi khác nhau từ nút (0, 0), đến nút (n, m) nếu chỉ cho phép đi trên cạnh các
ô vuông theo chiều sang phải hoặc lên trên.
Giải.
Mỗi đường đi gồm m + n đoạn, trong đó có m đoạn lên trên, và n đoạn sang
phải. Tương ứng tổ hợp chập m (lên trên) từ m + n phần tử. Hai đường đi khác
nhau bởi sự luân phiên của các đoạn đứng và đoạn ngang. Vậy số đường đi là:
C(n+m, m). Sau đây là một đường đi từ nút (0, 0) đến nút (n, m):
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 16
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Bài 2. Cho lưới các ô
vuông kích thước n x n. Các đường đi từ nút (0, 0) đến (n, n) gọi là tốt nếu nó

Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Số G
n
gọi là số Catalan (mang tên nhà toán học Bỉ Eugene
Catalan,1814−1894).
Bài toán 3. Bài toán phân phối
1. Có bao nhiêu cách phân phối n quả cầu giống nhau và m hộp phân biệt ?
Giải.
• TH1. Nếu hộp nào cũng có quả cầu, khi đó điều kiện
n m≥
Ta biểu diễn n quả cầu A liên tiếp có n-1 vạch phân chia.
A A A A A
− − − − −
Mỗi cách phân phối là một cách chọn m-1 vạch từ n-1 vạch.
Vậy ta có:
( 1, 1)C n m− −
(cách).
• TH2. Nếu có thể có hộp rỗng, khi đó không có điều kiện ràng buộc giữa
m và n.
Ta biểu diễn n quả cầu A và m số 0 liên tiếp thì có m+n-1 vạch phân chia,
chẳng hạn:
0 0 0 0A A A A− − − − − − − −
Mỗi cách phân phối có thể có hộp rỗng là một cách chọn m-1 vạch từ m+n
-1 vạch. Vậy ta có:
( 1, 1)C n m m+ − −
(cách).
2. Có bao nhiêu cách xếp đặt k.n vật khác nhau thành k nhóm, mỗi nhóm có
đúng n vật?
Giải. Ta chứng minh bằng quy nạp.
Gọi

Vậy số cách xếp đặt là:
( . )!
( . ; , , , )
! ! !
k n
C k n n n n
n n n
=
II. CẤU HÌNH TỔ HỢP NÂNG CAO
1. Hoán vị lặp
Bài toán 4 . Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao
cho có n
i
vật được đặt vào trong hộp thứ i, với i = 1, 2, , k bằng
)! !.(! !.
!
121 kk
nnnnnn
n
−−−
.
Ví dụ. Có 12 bóng đèn, trong đó có 4 bóng đèn đỏ, 3 bóng đèn vàng và 5
bóng đèn xanh được lắp vào 18 ổ cắm trên một hàng. Hãy đếm số phương án lắp
các bóng đèn.
Giải.
Khi lắp 12 bóng đèn thì 18 ổ cắm bao gồm 4 loại: 4 bóng đèn đỏ, 3 bóng
đèn vàng, 5 bóng đèn xanh và 6 ổ cắm rỗng. Như vậy mỗi phương án lắp các
bóng đèn là một hoán vị lặp .Ta có số phương án lắp bóng đèn là:
P(18;4;3;5;6)=
!6!5!3!.4

n
là một số nguyên.
Giải: Xét n ký hiệu x
1
, x
1
, x
2
, x
2
, . . ., x
k
, x
k
. Ta có số hoán vị có lặp của n ký
hiệu này là:

! !
2!2! 2! 2
k
k lân
n n
=
14 2 43
Suy ra rằng
!
2
k
n
là một số nguyên

3. Có bao nhiêu cách chia 5 viên kẹo đỏ giống nhau và 7 viên kẹo xanh
giống nhau cho 3 em bé?
Giải. Mỗi cách chia 5 viên kẹo đỏ cho 3 em bé tương ứng với một cách chọn
5 phần tử, trong đó phần tử kiểu i lặp lại n
i
lần (i=1 3). Nên số cách chia kẹo đỏ
cho 3 em bé là số tổ hợp lặp chập 5 của 3 phần tử. Số cách chia kẹo đỏ là:
CR(3, 5) = C(7, 2)
Tương tự, số cách chia kẹo xanh là: CR(3, 7) = C(9, 2)
Theo nguyên lí nhân, số cách chia kẹo là: C(7, 2).C(9, 2) = 756.
4. Có bao nhiêu cách chia 10 viên kẹo giống nhau cho 3 em bé sao cho em
nào cũng có kẹo?
Giải. Mỗi cách chia 10 viên kẹo cho 3 em bé sao cho em nào cũng có kẹo có
thể coi như cách đặt 2 dấu | vào 9 vị trí xen giữa các viên kẹo. Do đó, số cách
chia kẹo là số tổ hợp chập 2 của 9 phần tử. Vậy số cách chia là:
C(9, 2) = 36.
Bài toán 9.
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 21
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Tìm số bộ nghiệm nguyên dương, nguyên không âm của phương trình,
bất phương trình.
1. Tìm số bộ nghiệm không âm của phương trình: x
1
+ x
2
+ x
3
= 11.
Giải. Mỗi bộ nghiệm nguyên không âm của phương trình tương ứng với một
cách chọn 1 phần tử của 1 tập có 3 loại sao cho có

+ y
2
+ y
3
+ y
4
= 16 (2)
Ta thấy mối bộ nghiệm nguyên dương của phương trình (1) tương ứng 1-1 với
một bộ nghiệm nguyên không âm của phương trình (2). vậy số bộ nghiêm
nguyên dương của phương trình (1) cũng là số bộ nghiệm nguyên không âm của
phương trình (2) và bằng:
CR(4, 6) = C(6+4-1, 4-1)) = C(9,3) =
( )
9!
3! 9 3 !−
=
9.8.7
3.2.1
= 84
3. Tìm số nghiệm nguyên không âm của phương trình
x
1
+ x
2
+ x
3
+ x
4
= 20 (1)
thỏa điều kiện: x

3
lần lượt là số nghiệm nguyên không âm của phương trình (1)
thỏa điều kiện (*), (**), (***). Ta có S
1
= S
2
- S
3
. Đặt x
1
’ = x
1
, x
2
’ = x
2
– 2, x
3
’ =
x
3
– 5, x
4
’ = x
4
. Kết hợp (**) phương trình (1) trở thành: x
1
’ + x
2
’ + x

1
’ + x
2
’ + x
3
’ + x
4
’ = 9 (3). Số nghiệm nguyên không
âm của phương trình (1) thỏa điều kiện (***) bằng số nghiệm nguyên không âm
của phương trình (3). Vậy số nghiệm nguyên không âm của phương trình (1)
thỏa điều kiện (***) là:
CR(4, 9) = C(9+4-1, 4-1) = C(12, 3) = 220 = S
3
Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện (*) là
S
1
= S
2
– S
3
= 560 – 220 =340.
4. Bất phương trình :
1 2 3
11 (1)x x x+ + ≤
có bao nhiêu bộ nghiệm nguyên không âm?
Giải.
Cách1. Ta đưa về các bài toán:
Phương trình thứ k:
1 2 3
x x x k+ + =

như sau:
Cách 2. Ta chọn một ẩn phụ
4
x
sao cho:
1 2 3 4
11 (2)x x x x+ + + =
. (Tức là với
mỗi bộ số
1 2 3
( , , )x x x
thoả bất phương trình (1),
4 1 2 3
11 ( )x x x x= − + +
).
Nhóm Học viên: Nhóm 7_ PP Toán Sơ Cấp K24 Trang 23
Đề Tài: Cấu hình tổ hợp nâng cao & ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Khi đó, số bộ nghiệm nguyên không âm của bất phương trình (1) tương ứng
với số bộ nghiệm nguyên không âm của phương trình (2). Như vậy ta có kết quả:
4 11 14 3 364= =( , ) ( , )CR C
Bài toán 10 . Trong kỳ thi kết thúc môn toán tổ hợp có 10 câu hỏi. Có bao nhiêu
cách gán điểm cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi câu ít nhất 5
điểm.
Giải .
Ta gọi
i
x
là số điểm cần gán cho câu thứ i,
1 10i =
thoả:

.
3. Phân hoạch thứ tự và không thứ tự
Bài toán 11. Có bao nhiêu cách chia 12 sinh viên thành 3 nhóm, mỗi nhóm 4
sinh viên, trong đó có 2 nhóm học tiếng Anh, một nhóm học tiếng Pháp?
Giải. Chọn 2 nhóm trong 3 nhóm để bố trí học tiếng Anh có C(3, 2) cách.
Mỗi phương án chia 12 sinh viên thành 3 nhóm, mỗi nhóm 4 sinh viên là
một phân hoạch không thứ tự tổ hợp của 12 với 3 tập lực lượng 4.
Như vây, số cách chia là
( )
3
12!
.C(3, 2)=17325
3! 4!
.
Bài toán 12. Chứng minh Ðịnh lý đa thức : Nếu n là một số nguyên dương thì

1 2
1 2
1 2 1 2 1 2

( ) ( , , , , )
m
m
r
r r
n
m m m
r r r n
x x x C n r r r x x x
+ + + =

m
r r r n+ + + =
.
Số hạng như thế xuất hiện từ việc chọn
1
r
nhân tử
1
x
,
2
r
nhân tử
2
x
, ,
m
r

nhân tử
m
x
. Mỗi cách chọn như trên là một phân hoạch thứ tự tổ hợp chập n của
n với số phần tử trong mỗi tập con tương ứng là
1 2
, , ,
m
r r r
. Vậy có
1 2

3!2!2!
C − = =
Cách 2. Sử dụng nhị thức Newton
Ta có:
7 7
7 7 7
7 7
1 1 1
( 2 3 ) ( 2 ) ( 3 ) (2 ) ( 3 )
k
k k k k i i k i k
k
k k i
x y z C x y z C C x y z
− − −
= = =
+ − = + − = −
∑ ∑∑

7
7 7
7
1 1
( 3) 2
k
k k k i i i k i k
k
k i
C C x y z
− − − −

3 2 2
x y z
là:
2 5 2 3
7 5
( 3) . .2 . 7560C C− =
.
Áp dụng 2. Có bao nhiêu số hạng trong khai triển của biểu thức
100
( )x y z+ +
?
Giải. Ta có:
31 2
1 2 3
100
1 2 3
100
( ) (100; , , )
rr r
r r r
x y z C r r r x y z
+ + =
+ + =
∑
Nhận xét rằng, số các số hạng trong khai triển tương ứng với số bộ số
nguyên không âm
1 2 3
( , , )r r r
khác nhau thoả điều kiện:
1 2 3