01.3.Tổ hợp

Giới thiệu

Lý thuyết tập hợp là một nhánh rất lớn của Toán học.  Được khởi xướng bởi Cantor và Dedekind  vào khoản đầu thế kỷ 19, lý thuyết bắt nguồn từ mối quan hệ nhị phân cơ bản của một phần tử o và một tập hợp A. Nếu o là một thành viên của A thì ta ký hiệu o ∈ A.  Trong đó một tập hợp A là một nhóm các phần tử phân biệt với nhau.

Từ đây, người ta phát triển lý thuyết này qua việc nghiên cứu các quan hệ giữa các tập hợp, các phương pháp đếm, các phép toán trên tập hợp cũng như các cách kết hợp các phần tử của tập hợp tạo thành các tập con của nó.

Trong lập trình thi đấu (Programming contest), lý thuyết tập hợp được dùng nhiều chủ yếu ở các bài toán dựa trên các cách kết hợp phần tử. Ưu điểm của việc sử dụng các quy tắc đếm này vào giải quyết bài toán là chúng ta sẽ giải được chúng trong độ phức tạp thời gian ngắn, nhưng nhược điểm là rất khó để nhìn ra được các quy tắc này vì chúng thường nằm ẩn sâu bên trong bài toán. Qua chủ đề này, chúng ta sẽ cùng thảo luận một số ví dụ liên quan để có thể giúp các em quen dần cách phân tích để nhìn ra các nguyên tắc đếm này trong các bài toán thực tế sau này.

Tập hợp

Là nhóm các phần tử rời rạc nhau, nhưng thông thường chúng có chung một hay nhiều đặc tình gì đó. Ví dụ như tập hợp các số nguyên, tập hợp các số thực,...

Quan hệ giữa các tập hợp

Quan hệ bao hàm

Nếu tất cả các thành viên của tập A cũng là thành viên của tập B , thì A là một Tập hợp con của B , được biểu thị  A ⊂  B, và tập hợp B bao hàm tập hợp A. Ví dụ, {1, 2} là một tập hợp con của {1, 2, 3}, và {2} cũng vậy, nhưng { 1, 4} thì không. (Nguồn: Wikipedia)

Quan hệ bằng nhau

Nếu A là tập con của B và B cũng là tập con của A thì ta gọi A và B là hai tập hợp bằng nhau, ký hiệu A = B.

Các phép toán trên tập hợp

• Hợp (Union): Hợp của A và B là tập hợp gồm tất cả các phần tử thuộc ít nhất một trong hai tập hợp A và B, ký hiệu A ∪ B

Ta có A ∪ B = {x: x ∈ A hoặc x ∈ B}, hợp của {1, 2, 3} và {2, 3, 4} là tập {1, 2, 3, 4}.

• Giao (Intersection): Giao của hai tập hợp A và B là tập hợp tất cả các phần tử vừa thuộc A, vừa thuộc B, ký hiệu A ∩ B

Ta có A ∩ B = {x: x  ∈ A và x ∈ B}, giao của {1, 2, 3} và {2, 3, 4} là tập { 2, 3}.

• Hiệu (Difference): Hiệu của tập hợp A với tập hợp B là tập hợp tất cả các phần tử thuộc A nhưng không thuộc B, ký hiệu A∖B

Ta có: A \ B = {x: x ∈ A và x ∉ B}

Lưu ý, A \ B ≠ B \ A

• Phần bù (Complement): là hiệu của tập hợp con. Nếu A ⊂ B thì B \ A được gọi là phần bù của A trong B, ký hiệu CAB (hay CB A) 

(Nguồn: Wikipedia)

Các quy tắc đếm (Các nguyên lý cơ bản)

Quy tắc cộng

Ví dụ 1. Một đoàn vận động viên gồm 2 môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Nam có 10 người. Số vận động viên thi bắn súng (kể cả nam và nữ) là 14. Số nữ vận động viên thi bơi bằng số nam vận động viên thi bắn súng. Hỏi toàn đoàn có bao nhiêu người?

lGiải: Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lại được chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số nam thi bắn súng (2 số này bằng nhau theo đầu bài), ta được số nữ bằng tổng số đấu thủ thi bắn súng. Từ đó, theo nguyên lý cộng, toàn đoàn có 10 + 14 = 24 người.

lVí dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ nhiệm Khoa công bố danh sách các đề tài bao gồm 80 đề tài về chủ đề "xây dựng hệ thông tin quản lý", 10 đề tài về chủ đề "thiết kế phần mềm dạy học" và 10 đề tài về chủ đề "Hệ chuyên gia". Hỏi một sinh viên có bao nhiêu khả năng lựa chọn đề tài?

lGiải: Sinh viên có thể lựa chọn đề tài theo chủ đề thứ nhất bởi 80 cách, theo chủ đề thứ hai bởi 10 cách, theo chủ đề thứ ba bởi 10 cách. Vậy tất cả có 100 cách lựa chọn.

lVí dụ 3. Hỏi rằng giá trị của k sẽ là bao nhiêu sau khi đoạn chương trình PASCAL sau được thực hiện?

  n1:=10; n2:=20;   n3:=30;

  k:=0;

  for i1:= 1 to n1 do k:=k+1;

  for i2:= 1 to n2 do k:=k+1;

  for i3:= 1 to n3 do k:=k+1;

lGiải: Đầu tiên giá trị của k được gán bằng 0. Có 3 vòng lặp for độc lập. Sau mỗi lần lặp của mỗi một trong 3 vòng for, giá trị của k tăng lên 1. Vòng for thứ nhất lặp 10 lần, vòng for thứ hai lặp 20 lần, vòng for thứ ba lặp 30 lần. Vậy, kết thúc 3 vòng lặp for giá trị của k sẽ là 10+20+30= 60.

Nguyên lý nhân

lTrong nhiều bài toán đếm, chỉ sau khi xây dựng xong thành phần thứ nhất ta mới biết cách xây dựng thành phần thứ hai, sau khi xây dựng xong hai thành phần đầu ta mới biết cách xây dựng thành phần thứ ba,... Trong trường hợp đó có thể sử dụng nguyên lý nhân tổng quát:

lGiả sử ta xây dựng bộ có thứ tự k thành phần (a1, a2, ..., ak) theo từng thành phần và

•a1 có thể chọn bởi n1 cách;

•Sau khi a1 đã chọn, a2 có thể chọn bởi n2 cách;

•...

•Sau khi a1, a2,...,ak-1 đã chọn, ak có thể chọn bởi nk cách;

•Như vậy số bộ được tạo ra là tích số n1n2 ... nk.

lVí dụ 1. Từ Hà nội đến Huế có 3 cách đi: máy bay, ô tô, tàu hoả. Từ Huế đến Sài gòn có 4 cách đi: máy bay, ô tô, tàu hoả, tàu thuỷ. Hỏi từ Hà nội đến Sài gòn (qua Huế) có bao nhiêu cách đi?

lGiải:  Mỗi cách đi từ Hà nội đến Sài gòn (qua Huế) được xem gồm 2 chặng: Hà nội - Huế và Huế - Sài gòn. Từ đó, theo nguyên lý nhân, số cách đi từ Hà nội đến Sài gòn là  3 ´ 4 = 12 cách.

Ví dụ 2. Hỏi rằng giá trị của k sẽ là bao nhiêu sau khi đoạn chương trình PASCAL sau được thực hiện?

   n1:=10; n2:=20; n3:=30;

   k:=0;

   for i1:=1 to n1 do

      for i2:=1 to n2 do

     for i3:=1 to n3 do k:=k+1;

Giải:  Đầu tiên giá trị của k được gán bằng 0. Có 3 vòng lặp for  lồng nhau. Sau mỗi lần lặp của vòng for, giá trị của k tăng lên 1. Vòng for thứ nhất lặp 10 lần, vòng for thứ hai lặp 20 lần, vòng for thứ ba lặp 30 lần. Vậy, theo nguyên lý nhân, kết thúc 3 vòng lặp for lồng nhau, giá trị của k sẽ là 10 ´ 20 ´ 30 = 6000.

Nhiệm vụ 1: lHỏi có bao nhiêu lá cờ gồm 3 vạch mầu, mầu của mỗi vạch lấy từ ba mầu xanh, đỏ, trắng sao cho:

  a) Không có hai vạch liên tiếp nào cùng màu

  b) Không có hai vạch nào cùng màu

Nhiệm vụ 2: Có bao nhiêu xâu gồm 4 chữ số thập phân 

a) Không chứa một chữ số nào hai lần.

b) Kết thúc bởi chữ số chẵn

Nhiệm vụ 3: Có 10 người tham gia vào việc chụp ảnh kỹ niệm ở một đám cưới, trong đó có cô dâu và chú rể. Ta xét bức ảnh chỉ gồm 6 người trong họ. 

a) Có bao nhiêu bức ảnh có mặt cô dâu?

b) Có thể chụp bao nhiêu bức ảnh trong đó có mặt cả cô dâu lẫn chú rễ?

c) Có bao nhiêu bức ảnh trong đó chỉ có mặt một cô dâu hoặc chú rễ?

Các cấu hình tổ hợp cơ bản

Chỉnh hợp lặp

lĐịnh nghĩa. Ta gọi chỉnh hợp lặp chập m của n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X.

lKý hiệu số lượng chỉnh hợp lặp chập m của n phần tử là Anm

lTheo định nghĩa, một chỉnh hợp lặp chập m của n phần tử của X có thể biểu diễn bởi

      (a1, a2, ..., am), ai  ∈  X, i = 1, 2, ..., m.

lDễ thấy tập tất cả các chỉnh hợp lặp chập m của n phần tử của X chính là Xm. Vì vậy, theo nguyên lý nhân ta có

lĐịnh lý 1. Anm = nm.

Ví dụ 1.  Tính số ánh xạ từ tập m phần tử U = {u1, u2, ..., um} vào tập n phần tử V.

Giải:  Mỗi ánh xạ f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ..., f(um)), trong đó f(ui) Î V, i=1, 2, ..., m. Từ đó nhận được số cần tìm là nm.

Ví dụ 2.  Tính số dãy nhị phân độ dài n.

Giải:  Mỗi dãy nhị phân độ dài n là một bộ gồm n thành phần, trong đó mỗi thành phần chỉ nhận một trong hai giá trị (1 hoặc 0). Từ đó suy ra số các dãy nhị phân độ dài n  là 2n.

Do mỗi tập con của tập n phần tử tương ứng với một vectơ đặc trưng là một xâu nhị phân độ dài n, nên ta có

Hệ quả: Số lượng tập con của tập n phần tử là 2n.

Nhiệm vụ 4. Cần phải phân bố 100 sinh viên vào 4 nhóm thực tập ACCESS, FOXPRO, EXCEL, LOTUS. Mỗi sinh viên phải tham gia vào đúng một nhóm và mỗi nhóm có thể nhận một số lượng không hạn chế sinh viên. Hỏi có bao nhiêu cách phân bố sinh viên như vậy?

Chỉnh hợp không lặp

lĐịnh nghĩa. Ta gọi chỉnh hợp không lặp chập m của n phần tử của X là bộ có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi.

lKý hiệu số lượng chỉnh hợp không lặp chập m của n phần tử là Pnm. Rõ ràng, để tồn tại chỉnh hợp không lặp, thì m ≤  n.

lTheo định nghĩa, một chỉnh hợp không lặp chập m của n phần tử của X có thể biểu diễn bởi

      (a1, a2, ..., am), ai  ∈  X, i = 1, 2, ..., m, ai ≠  aj, i ≠  j.

lViệc đếm số lượng chỉnh hợp không lặp chập m của n phần tử có thể thực hiện theo nguyên lý nhân. Ta có

Định lý 2. 

Ví dụ 1.  Tính số đơn ánh từ tập m phần tử U = {u1, u2, ..., um} vào tập n phần tử V.

Giải:  Mỗi đơn ánh f cần đếm được xác định bởi bộ ảnh (f(u1), f(u2), ..., f(um)), trong đó f(ui) ∈  V, i=1, 2, ..., m, f(ui)≠ f(uj), i≠ j. Từ đó nhận được số cần tìm là n(n-1)...(n-m+1).

Nhiệm vụ 5: Có bao nhiêu cách xếp 4 học sinh vào ngồi sau một cái bàn có 10 chỗ ngồi với điều kiện không được ghép ngồi lòng.

Hoàn vị

lĐịnh nghĩa. Ta gọi hoán vị từ n phần tử của X là bộ có thứ tự gồm n thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi.

lKý hiệu số lượng hoán vị từ n phần tử là Pn.

lTheo định nghĩa, một hoán vị từ n phần tử của X có thể biểu diễn bởi

      (a1, a2, ..., an), ai  ∈ X, i = 1, 2, ..., n, ai ≠ aj, i ≠ j.

lRõ ràng Pn = Pnn. Vì vậy, ta có

Định lý 3. 

Ví dụ 1. 6 người đứng xếp thành một hàng ngang để chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu?

Giải: Mỗi kiểu ảnh là một hoán vị của 6 người. Từ đó nhận được số kiểu ảnh có thể bố trí là 6! = 720.

Ví dụ 2. Cần bố trí việc thực hiện n chương trình trên một máy vi tính. Hỏi có bao nhiêu cách?

Giải: Đánh số các chương trình bởi 1, 2,..., n. Mỗi cách bố trí việc thực hiện các chương trình trên máy có thể biểu diễn bởi một hoán vị của 1, 2, ..., n. Từ đó suy ra số cách bố trí cần tìm là n!

Nhiệm vụ 6: Có bao nhiêu song ánh từ tập n phần tử X vào chính nó? (Mỗi song ánh như vậy được gọi là một phép thế). 

Nhiệm vụ 7: Có bao nhiêu cách bố trí n thợ thực hiện n việc sao cho mỗi thợ thực hiện một việc và mỗi việc do đúng một thợ thực hiện 

Tổ hợp

lĐịnh nghĩa. Ta gọi tổ hợp chập m của n phần tử của X là bộ không có thứ tự gồm m thành phần, mỗi thành phần đều là phần tử của X, các thành phần khác nhau từng đôi.

lKý hiệu số lượng tổ hợp chập m của n phần tử là Cnm (đôi khi ta sẽ sử dụng ký hiệu C(n,m))

lTheo định nghĩa, một tổ hợp chập m của n phần tử của X có thể biểu diễn bởi bộ không có thứ tự

      {a1, a2, ..., am}, ai  ∈ X, i = 1, 2, ..., m, ai ≠ aj, i ≠ j.

lVới giả thiết X={1, 2,...,n}, một tổ hợp chập m của n phần tử của X có thể biểu diễn bởi bộ có thứ tự

 (a1, a2, ..., am), ai ∈  X, i = 1, 2, ..., m, 1 ≤  a1 < a2 < ...<am  ≤  n. 

Việc đếm các tổ hợp có khó khăn hơn so với việc đếm các cấu hình đã trình bày, tuy nhiên cách đếm dưới đây cho biết cách vận dụng các nguyên lý cùng với các kết quả đếm đã biết trong việc đếm một cấu hình mới.

Xét tập hợp tất cả các chỉnh hợp không lặp chập m của n phần tử. Chia chúng thành những lớp sao cho hai chỉnh hợp  thuộc cùng một lớp chỉ khác nhau về thứ tự. Rõ ràng các lớp này là một phân hoạch trên tập đang xét và mỗi lớp như thế là tương ứng với một tổ hợp chập m của n. Số chỉnh hợp trong mỗi lớp là bằng nhau và bằng m! (số hoán vị). Số các lớp là bằng số tổ hợp chập m của n. Theo nguyên lý cộng, tích của m! với số này là bằng số các chỉnh hợp không lặp chập m của n, nghĩa là bằng n(n-1)...(n-m+1). Từ đó nhận được số tổ hợp chập m  của n  là :

Định lý 4: 

Người ta còn gọi C(n, m) là hệ số tổ hợp.

Ví dụ 1. Có n đội bóng thi đấu vòng tròn. Hỏi phải tổ chức bao nhiêu trận đấu?

Giải: Cứ 2 đội thì có một trận. Từ đó suy ra số trận đấu sẽ bằng số cách chọn 2 đội từ n đội, nghĩa là bằng

                      C(n,2) = n(n-1)/2.

Nhiệm vụ 8: Hỏi có bao nhiêu giao điểm của các đường chéo của một đa giác lồi n (n >= 4) đỉnh nằm ở trong đa giác, nếu biết rằng không có ba đường chéo nào đồng quy tại điểm ở trong đa giác?

Nhiệm vụ 9: Cần thả n quả bóng giống nhau vào k phòng: Room1, Room2, …, Roomk. Hỏi có bao nhiêu cách phân bổ khác nhau? 

Hệ số tổ hợp

Hệ số tổ hợp như chúng ta nhắc đến ở trên có những tính chất cơ bản sau đây:

Các tính chất cơ bản

a) Đối xứng

  C(n,m) = C(n,n-m)

b) Điều kiện đầu (hệ số cơ sở)

      C(n,0) = 1;  C(n,n) = 1, n ≥  0        

c) Công thức hồi qui

      C(n,m) = C(n-1,m) + C(n-1, m-1),  n > m > 0

lTừ b) và c), ta có thể tính tất cả các hệ số tổ hợp chỉ bằng phép cộng. Các hệ số này  được tính và viết lần lượt theo từng dòng (mỗi dòng ứng với một giá trị n=0, 1, ...), trên mỗi dòng chúng được tính và viết lần lượt theo từng cột (mỗi cột ứng với một giá trị m = 0, 1, ..., n) theo bảng tam giác dưới đây:

Các hệ số tổ hợp có liên quan chặt chẽ với việc khai triển luỹ thừa của một nhị thức. Thật vậy, trong tích

         (x+y)n = (x+y) (x+y) . . . (x+y)

hệ số của  xm yn-m  sẽ là số cách chọn m nhân tử (x + y) mà từ đó ta lấy ra x và đồng thời trong n-m nhân tử còn lại ta lấy ra y, nghĩa là:

Công thức trên được gọi là khai triển nhị thức Newton và các hệ số tổ hợp còn được gọi là các hệ số nhị thức. 

Nhiệm vụ 10: Rook1

Trên một bảng ô vuông kích thước M ×N, hãy đếm số cách xếp K quân xe sao cho cả hai điều kiện sau được thỏa mãn:

 • Không có hai quân xe nào đứng ở cùng vị trí.

• Không có hai quân xe nào tấn công được nhau. Hai quân xe được gọi là tấn công được nhau nếu chúng ở cùng hàng hoặc cùng cột.

Dữ liệu: Vào từ file ROOK1.INP

• Dòng đầu tiên gồm số nguyên dương T (1 ≤ T ≤ 150) là số test.

• T dòng sau, mỗi dòng gồm ba số nguyên dương M, N, K (1≤ M,N≤50, 1≤K≤100).

Kết quả: Ghi ra file ROOK1.OUT

Gồm T dòng, mỗi dòng đưa ra số cách xếp xe thỏa mãn, sau khi lấy phần dư trong phép chia cho 1000001. 

Ví dụ:

ROOK1.INP

2

2 2 2

1 4 1

ROOK1.OUT

2 4

Nhiệm vụ 11. Xổ số (HSG lớp 9 TPHCM - năm học 2022-2023)

Hội xuân tại trường năm nay có gian hàng xổ số trúng điểm thưởng. Có N phiếu, mỗi phiếu có một mặt giống nhau, mặt còn lại ghi một số nguyên không âm ngẫu nhiên. Ban đầu mặt ghi số được đặt úp xuống mặt bàn. Người chơi được chọn K phiếu bất kỳ và nhận được số điểm thưởng là số lớn nhất trong K phiếu trên. Hùng rất hào hứng với trò chơi này và muốn biết tổng điểm thưởng mình được nhận là bao nhiêu nếu Hùng thử hết tất cả các cách chọn.

Gọi S là tổng điểm thưởng được nhận nếu Hùng thử hết tất cả các cách chọn phiếu. Xét ví dụ với N = 4, K = 2 và giá trị của các phiếu lần lượt là 6, 7, 6, 5 thì Hùng có 6 cách chọn và tổng điểm thưởng S là 39, giá trị điểm thưởng của từng cách được cho trong bảng sau: 

Yêu cầu: Hãy viết một chương trình cho biết phần dư khi chia S cho 109+7.

Dữ liệu: Vào từ file văn bản XOSO.INP dòng đầu chứa hai số nguyên N và K. Dòng thứ hai chứa N số nguyên Xi, (0 ≤  Xi  ≤ 106) lần lượt cho biết giá trị của N phiếu.

Kết quả: Ghi ra file văn bản XOSO.OUT trên một dòng là phần dư khi chia S cho 109+7.

Ràng buộc:

•  30% test ứng với 30% số điểm của bài có N ≤ 1000 và 1 ≤ K ≤ 3

•  20% test ứng với 20% số điểm của bài có N ≤ 25 và 1 ≤ K ≤ 12

• 50% test ứng với 50% số điểm của bài có N ≤ 100 000 và 1 ≤ K ≤ 50 

Ví dụ:

Nhiệm vụ 12. Pass Word (codeforce)

Tóm tắt:

Monocarp quên pass điện thoại cậu ấy. Password gồm 4 ký số (0-->9) và có thể bắt đầu từ '0'. Cậu ấy nhớ là pass có đúng hai loại ký tự khác nhau và mỗi ký tự xuất hiện 2 lần trong chuỗi pass. Cậu cũng nhớ rằng một số ký tự khác không được dùng trong password.

Bạn hãy tính toán số chuỗi 4 ký số có thể là password điện thoại của Monocarp.

Input:

• Dòng đầu tiên chứa số nguyên t (t<=100) là số lượng testcase.

• Dòng đầu trong mỗi test case chứa số nguyên n (1<=n<=8) là số lượng các ký số không được dùng trong password.

• Dòng thứ 2 chứa n số nguyên a1, a2,...,an (0<=ai<=9) là các ký số không được dùng. Dãy a được sắp xếp tăng dần.

Output:

• Gồm t dòng, mỗi dòng là kết quả của một testcase thỏa mãn đề bài.

Ví dụ:

Input:

2

8

0 1 2 4 5 6 8 9

1

8

Output:

6

216

Note

In the first example, all possible passwords are: "3377", "3737", "3773", "7337", "7373", "7733".

Nhiệm vụ 13. Infinite Replacement (Codeforce)

Tóm tắt:

Bạn được cho một xâu s chỉ gồm các ký tự 'a', và một xâu t chứa các ký tự in thường.

Một lẫn chuyển dịch, bạn có thể thay thể ký tự 'a' bất kỳ nào trong s bởi xâu t. Tức nhiên sau khi thay xong thì xâu s sẽ chứa những ký tự khác 'a'. 

Bạn có thể thực hiện số lần dịch chuyển tùy ý (kể cả không dịch chuyển). Có bao nhiêu xâu khác nhau bạn có thể nhận được? In ra số lần hoặc thông báo số lượng vô cùng lớn.

Input:

Dòng đầu tiên chứa số nguyên q (q<=10^4) là số lượng testcase

mỗi test trong q test chứa hai dòng:

• Dòng đầu là xâu s

• Dòng tiếp theo là xâu t

Output:

Gồm q dòng, mỗi dòng là kết quả của một testcase tương ứng

Ví dụ:

Input:

3

aaaa

a

aa

abc

a

b

Output:

1

-1

2