Lý thuyết tập hợp và tổ hợp

Author

Duc Nguyen | tuhocr.com

Published

October 15, 2026

Tài liệu biên soạn trong chuyên đề R Statistics

1 Lý thuyết tập hợp (Set theory)

1.1 Vector trong R là tập hợp

Gọi \(G\) là tập hợp, với các phần tử 3, 5, 6, 1. Ta ký hiệu là:

\[G = \{3, 5, 6, 1\}\]

Trong R thì ta gán các giá trị này vào vector G

G <- c(3, 5, 6, 1)
G
[1] 3 5 6 1

Các ký hiệu thường gặp:

\(x \in G\) đọc là: \(x\) thuộc (belong) tập hợp \(G\).

Ví dụ: Phần tử (element) \(3\) thuộc tập hợp (vector) \(G\)

# lệnh %in% sẽ so sánh số 3 lần lượt với từng thành phần trong G
# nếu có thành phần nào bằng y chang "identical" thì trả về TRUE
3 %in% G
[1] TRUE
3 == G
[1]  TRUE FALSE FALSE FALSE

\(x \notin G\) đọc là: \(x\) không thuộc (does not belong) tập hợp \(G\).

Ví dụ: Phần tử (element) \(33\) không thuộc tập hợp (vector) \(G\)

33 %in% G
[1] FALSE
33 == G
[1] FALSE FALSE FALSE FALSE

Tuy nhiên “tập hợp” sẽ không quan tâm đến thứ tự các thành phần, còn “vector” sẽ quan tâm đến thứ tự các thành phần.

G1 <- c(3, 5, 6, 1)
G1
[1] 3 5 6 1
G2 <- c(1, 6, 3, 5)
G2
[1] 1 6 3 5
# lệnh này kiểm tra hai tập hợp có giống nhau không
setequal(G1, G2)
[1] TRUE

Hai tập hợp giống nhau thì ký hiệu là \(G1 = G2\) (Chứng minh)

Nếu dùng lệnh identical(x, y) trong R thì hai đối tượng này chỉ y chang nhau khi có cùng trật tự.

identical(G1, G2)
[1] FALSE
identical(sort(G1), sort(G2))
[1] TRUE
G3 <- c(1, 6, 3, 5, 6)
G3
[1] 1 6 3 5 6
# lưu ý là nếu có nhiều thành phần trong G3 thì
# lệnh kiểm tra tập hợp này cũng trả về TRUE
# vì nó chỉ kiểm tra các thành phần unique giống nhau là được
setequal(G1, G3)
[1] TRUE
G1
[1] 3 5 6 1
# lệnh này trả về các phần tử xuất hiện ít nhất 1 lần trong G3
unique(G3)
[1] 1 6 3 5

Nếu ta có tập hợp \(G3\) có thành phần số \(6\) xuất hiện 2 lần thì về bản chất nó cũng gồm các thành phần y chang tập hợp \(G1\), vì nếu xét theo số lần xuất hiện của một phần tử không quan trọng, thì một phần tử xuất hiện nhiều lần vẫn tính là một phần tử của tập hợp đó.

\(G1 = G3 \Leftrightarrow \forall x, (x \in G1 \Leftrightarrow x \in G3)\)

1.2 Các lệnh tập hợp trong R

A <- c(2, 0, 9, 3, 7, 8, 8, 1, 9)
A
[1] 2 0 9 3 7 8 8 1 9
B <- c(2, 3, 0, 1)
B
[1] 2 3 0 1

Ta nói \(B\) là tập hợp con (subset) của \(A\), ký hiệu \(B \subset A\)

Hình minh họa (draw.io)

\[ A \backslash B = \{7, 8, 9 \} \]

# setdiff(x, y) trả về thành phần có trong x mà không có trong y
# chú ý: nếu thành phần nào trùng nhau thì sẽ được 
# unique (lấy phần tử đại diện xuất hiện ít nhất 1 lần)
setdiff(A, B)
[1] 9 7 8
# subset các thành phần của B có trong A
A[A %in% B]
[1] 2 0 3 1
# subset các thành phần không có trong B, từ trong vector A
# kết quả trả về là toàn bộ thành phần mà không phải unique
# ta có thể nghịch đảo lại lệnh %in%
A[!(A %in% B)]
[1] 9 7 8 8 9

Vì \(B\) là tập hợp con của \(A\) nên phần khác biệt (có trong \(B\) mà không có trong \(A\) là tập hợp rỗng)

\[B \subset A \implies B \backslash A = \emptyset \]

setdiff(B, A)
numeric(0)

\[A \cap B \]

intersect(A, B)
[1] 2 0 3 1

\[A \cup B\]

union(A, B)
[1] 2 0 9 3 7 8 1
setequal(A, B)
[1] FALSE

Các công thức lý thuyết tập hợp

1.3 Phân tích phần giao nhau

C <- c(0, 3, 4, 2, 1)
D <- c(8, 7, 4, 9, 2, 1)

\[C \backslash D = \{0, 3\}\]

setdiff(C, D)
[1] 0 3

\[D \backslash C = \{8, 7, 9\}\]

setdiff(D, C)
[1] 8 7 9

\[C \cap D = \{4, 2, 1\}\]

intersect(C, D)
[1] 4 2 1
intersect(D, C)
[1] 4 2 1

\[C \cup D = \{0, 3, 4, 2, 1, 8, 7, 9 \}\]

union(C, D)
[1] 0 3 4 2 1 8 7 9

\[(C \cup D) \backslash (C\cap D) = \{0, 3, 8, 7, 9 \}\]

setdiff(union(C, D), intersect(C, D))
[1] 0 3 8 7 9

Tham khảo chuyên đề R cơ bản về các lệnh reshape và merge dữ liệu (session 6)

2 Lý thuyết tổ hợp (Combinatorics)

“Lý thuyết tổ hợp” tiếng Anh là Combinatorics, nghiên cứu cách đếm, sắp xếp và phân chia các đối tượng.

Các từ liên quan:

  • Combination:Tổ hợp

  • Permutation: Chỉnh hợp / Hoán vị (tùy ngữ cảnh)

  • Arrangement: Cách sắp xếp

  • Counting principles: Các nguyên lý đếm

  • Binomial coefficient: Hệ số nhị thức

  • Inclusion–exclusion principle: Nguyên lý bao hàm–loại trừ Wikipedia

2.1 Quy tắc cộng (Addition Principle)

Một công việc được thực hiện bằng một trong các phương án không trùng nhau.

Nếu phương án 1 có \(m\) cách, phương án 2 có \(n\) cách thì tổng số cách là:

\[\text{Tổng số cách thực hiện} = m + n\]

Ví dụ: Có 3 bút bi và 4 bút chì. Chỉ được chọn 1 chiếc bút (bất kể là bút bi hay bút chì) thì có 3 + 4 = 7 cách chọn.

2.2 Quy tắc nhân (Multiplication Principle)

Giả sử một công việc chia thành 2 công đoạn A và B. Công đoạn A có thể thực hiện \(m\) cách và ứng với mỗi cách thực hiện công đoạn A thì có \(n\) cách thực hiện công đoạn B. Khi đó:

\[\text{Tổng số cách thực hiện} = m \times n\]

Ví dụ: Có 3 áo và 4 quần. Chọn 1 áo và 1 quần thì có 3 × 4 = 12 phương án phối bộ quần áo.

2.3 Giai thừa

Giai thừa (factorial) của một số nguyên không âm \(n\), ký hiệu \(n!\) là tích của tất cả các số nguyên dương từ \(1\) đến \(n\).

\[n! = 1 \times 2 \times 3 \cdots \times n-1 \times n\]

Ví dụ:

\[6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720\]

factorial(x = 6)
[1] 720
1 * 2 * 3 * 4 * 5 * 6
[1] 720

2.4 Tổ hợp chập

Tổ hợp chập \(k\) của \(n\), tiếng Anh là combination/combinator \(n\) objects taken \(k\) at a time, (có bao nhiêu cách) chọn \(k\) phần tử từ tập hợp gồm \(n\) phần tử.

\[\mathrm{C}_{n}^{k} = C(n, k) = \binom{n}{k}=\frac{n!}{k!(n-k)!}\]

\[\binom{n}{k}\]

đọc là “n choose k” hay là “tổ hợp chập k của n”, hay là “k-combination of n elements”

Ta tìm “số tổ hợp chập k của n”, “number of combination/combinator \(n\) elements taken \(k\) at a time.

Ví dụ: Tổ hợp chập 2 của 4. Ta có 4 bạn A, B, C, D. Chọn 2 bạn để tham gia một đội. Hỏi có bao nhiêu cách chọn?

Làm thủ công ta sẽ có 6 cách chọn như sau:

  • AB hay BA được xem là 1 cách chọn vì tổ hợp chập không quan tâm thứ tự.
  • AC
  • AD
  • BC
  • BD
  • CD

\[\mathrm{C}_{4}^{2} = C(4, 2) = \binom{4}{2}=\frac{4!}{2!(4-2)!} = \frac{24}{2 \times 2} = 6\]

choose(n = 4, k = 2)
[1] 6
library(combinat)

# generate all combinations of the elements of x taken m at a time.
# kết quả tổ hợp xếp theo cột
# tính tổng số cột bằng lệnh ncol()

kq <- combinat:::combn(x = c("A", "B", "C", "D"),
                       m = 2)

kq
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,] "A"  "A"  "A"  "B"  "B"  "C" 
[2,] "B"  "C"  "D"  "C"  "D"  "D" 
ncol(kq)
[1] 6

2.5 Hoán vị và chỉnh hợp

Đây là cách chọn phần tử từ tập hợp, có xét đến thứ tự, do đó AB và BA là 2 cách chọn khác nhau.

3 Tài liệu tham khảo

  1. Lý thuyết tập hợp (Wikipedia)

  2. https://www.mathsisfun.com/combinatorics/combinations-permutations.html

  3. Combinatorics: an upper-level introductory course in enumeration, graph theory, and design theory PDF