HNI 14/9 Chương 37: Tổ hợp và Hoán vị
1. Mở đầu: Từ việc sắp xếp đồ vật đến quy luật toán học
Trong cuộc sống thường ngày, chúng ta thường gặp những tình huống liên quan đến việc sắp xếp, lựa chọn, hay kết hợp các phần tử. Khi xếp sách trên kệ, ta có thể đặt theo nhiều thứ tự khác nhau. Khi chọn đội bóng từ một nhóm học sinh, ta có nhiều cách chọn khác nhau. Khi đặt mật khẩu với một dãy ký tự, số khả năng có thể tạo ra là vô cùng lớn. Tất cả những vấn đề này đều thuộc về một nhánh quan trọng của Toán học: Tổ hợp và Hoán vị.
Tổ hợp và hoán vị chính là nền tảng của xác suất, thống kê, mật mã học, và cả trong đời sống hằng ngày. Đây là chiếc cầu nối giữa sự rời rạc của các đối tượng và sự chính xác của tư duy toán học. Không chỉ dừng lại ở việc “đếm số cách”, mà còn mở ra cả một thế giới về quy luật của sắp xếp và chọn lựa.
2. Khái niệm cơ bản
2.1. Hoán vị
Hoán vị của một tập hợp gồm
n
n phần tử là một cách sắp xếp toàn bộ
n
n phần tử đó theo một thứ tự nhất định.
Ví dụ: Tập
A
ABC,ACB,BAC,BCA,CAB,CBA.
Như vậy có tất cả 6 hoán vị.
Công thức tổng quát:
P
n!=n×(n−1)×(n−2)×⋯×1
2.2. Chỉnh hợp
Chỉnh hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử và sắp xếp chúng theo thứ tự.
Công thức:
A
=
(n−k)!
n!
2.3. Tổ hợp
Tổ hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử mà không quan tâm đến thứ tự.
Công thức:
=
k!(n−k)!
n!
3. Hoán vị – sự sắp xếp toàn bộ
3.1. Nguyên tắc cơ bản
Nếu ta có
n
n đối tượng khác nhau, số cách sắp xếp tất cả chúng vào
n
n vị trí khác nhau chính là
n
!
n!.
Ví dụ: Có 4 học sinh xếp hàng, số cách xếp là:
4
!
=
24
4!=24.
3.2. Hoán vị có lặp
Khi một số phần tử trùng nhau, công thức tính số hoán vị sẽ thay đổi.
Giả sử tập có
n
n phần tử, trong đó có
n
Ví dụ: Từ các chữ cái của từ “MIMI”, số hoán vị khác nhau là:
4
=6
3.3. Ứng dụng thực tiễn
Hoán vị xuất hiện trong:
Tạo mật khẩu hoặc mã PIN.
Sắp xếp lịch thi đấu thể thao.
Mã hóa dữ liệu trong an ninh mạng.
4. Chỉnh hợp – sự lựa chọn có thứ tự
4.1. Định nghĩa lại
Chỉnh hợp là sự kết hợp của việc chọn và sắp xếp. Khác với hoán vị, ta chỉ lấy ra
k
k phần tử, nhưng vẫn giữ yếu tố thứ tự.
1. Mở đầu: Từ việc sắp xếp đồ vật đến quy luật toán học
Trong cuộc sống thường ngày, chúng ta thường gặp những tình huống liên quan đến việc sắp xếp, lựa chọn, hay kết hợp các phần tử. Khi xếp sách trên kệ, ta có thể đặt theo nhiều thứ tự khác nhau. Khi chọn đội bóng từ một nhóm học sinh, ta có nhiều cách chọn khác nhau. Khi đặt mật khẩu với một dãy ký tự, số khả năng có thể tạo ra là vô cùng lớn. Tất cả những vấn đề này đều thuộc về một nhánh quan trọng của Toán học: Tổ hợp và Hoán vị.
Tổ hợp và hoán vị chính là nền tảng của xác suất, thống kê, mật mã học, và cả trong đời sống hằng ngày. Đây là chiếc cầu nối giữa sự rời rạc của các đối tượng và sự chính xác của tư duy toán học. Không chỉ dừng lại ở việc “đếm số cách”, mà còn mở ra cả một thế giới về quy luật của sắp xếp và chọn lựa.
2. Khái niệm cơ bản
2.1. Hoán vị
Hoán vị của một tập hợp gồm
n
n phần tử là một cách sắp xếp toàn bộ
n
n phần tử đó theo một thứ tự nhất định.
Ví dụ: Tập
A
ABC,ACB,BAC,BCA,CAB,CBA.
Như vậy có tất cả 6 hoán vị.
Công thức tổng quát:
P
n!=n×(n−1)×(n−2)×⋯×1
2.2. Chỉnh hợp
Chỉnh hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử và sắp xếp chúng theo thứ tự.
Công thức:
A
=
(n−k)!
n!
2.3. Tổ hợp
Tổ hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử mà không quan tâm đến thứ tự.
Công thức:
=
k!(n−k)!
n!
3. Hoán vị – sự sắp xếp toàn bộ
3.1. Nguyên tắc cơ bản
Nếu ta có
n
n đối tượng khác nhau, số cách sắp xếp tất cả chúng vào
n
n vị trí khác nhau chính là
n
!
n!.
Ví dụ: Có 4 học sinh xếp hàng, số cách xếp là:
4
!
=
24
4!=24.
3.2. Hoán vị có lặp
Khi một số phần tử trùng nhau, công thức tính số hoán vị sẽ thay đổi.
Giả sử tập có
n
n phần tử, trong đó có
n
Ví dụ: Từ các chữ cái của từ “MIMI”, số hoán vị khác nhau là:
4
=6
3.3. Ứng dụng thực tiễn
Hoán vị xuất hiện trong:
Tạo mật khẩu hoặc mã PIN.
Sắp xếp lịch thi đấu thể thao.
Mã hóa dữ liệu trong an ninh mạng.
4. Chỉnh hợp – sự lựa chọn có thứ tự
4.1. Định nghĩa lại
Chỉnh hợp là sự kết hợp của việc chọn và sắp xếp. Khác với hoán vị, ta chỉ lấy ra
k
k phần tử, nhưng vẫn giữ yếu tố thứ tự.
HNI 14/9 🌺Chương 37: Tổ hợp và Hoán vị
1. Mở đầu: Từ việc sắp xếp đồ vật đến quy luật toán học
Trong cuộc sống thường ngày, chúng ta thường gặp những tình huống liên quan đến việc sắp xếp, lựa chọn, hay kết hợp các phần tử. Khi xếp sách trên kệ, ta có thể đặt theo nhiều thứ tự khác nhau. Khi chọn đội bóng từ một nhóm học sinh, ta có nhiều cách chọn khác nhau. Khi đặt mật khẩu với một dãy ký tự, số khả năng có thể tạo ra là vô cùng lớn. Tất cả những vấn đề này đều thuộc về một nhánh quan trọng của Toán học: Tổ hợp và Hoán vị.
Tổ hợp và hoán vị chính là nền tảng của xác suất, thống kê, mật mã học, và cả trong đời sống hằng ngày. Đây là chiếc cầu nối giữa sự rời rạc của các đối tượng và sự chính xác của tư duy toán học. Không chỉ dừng lại ở việc “đếm số cách”, mà còn mở ra cả một thế giới về quy luật của sắp xếp và chọn lựa.
2. Khái niệm cơ bản
2.1. Hoán vị
Hoán vị của một tập hợp gồm
n
n phần tử là một cách sắp xếp toàn bộ
n
n phần tử đó theo một thứ tự nhất định.
Ví dụ: Tập
A
ABC,ACB,BAC,BCA,CAB,CBA.
Như vậy có tất cả 6 hoán vị.
Công thức tổng quát:
P
n!=n×(n−1)×(n−2)×⋯×1
2.2. Chỉnh hợp
Chỉnh hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử và sắp xếp chúng theo thứ tự.
Công thức:
A
=
(n−k)!
n!
2.3. Tổ hợp
Tổ hợp của
n
n phần tử lấy
k
k phần tử là một cách chọn ra
k
k phần tử từ
n
n phần tử mà không quan tâm đến thứ tự.
Công thức:
=
k!(n−k)!
n!
3. Hoán vị – sự sắp xếp toàn bộ
3.1. Nguyên tắc cơ bản
Nếu ta có
n
n đối tượng khác nhau, số cách sắp xếp tất cả chúng vào
n
n vị trí khác nhau chính là
n
!
n!.
Ví dụ: Có 4 học sinh xếp hàng, số cách xếp là:
4
!
=
24
4!=24.
3.2. Hoán vị có lặp
Khi một số phần tử trùng nhau, công thức tính số hoán vị sẽ thay đổi.
Giả sử tập có
n
n phần tử, trong đó có
n
Ví dụ: Từ các chữ cái của từ “MIMI”, số hoán vị khác nhau là:
4
=6
3.3. Ứng dụng thực tiễn
Hoán vị xuất hiện trong:
Tạo mật khẩu hoặc mã PIN.
Sắp xếp lịch thi đấu thể thao.
Mã hóa dữ liệu trong an ninh mạng.
4. Chỉnh hợp – sự lựa chọn có thứ tự
4.1. Định nghĩa lại
Chỉnh hợp là sự kết hợp của việc chọn và sắp xếp. Khác với hoán vị, ta chỉ lấy ra
k
k phần tử, nhưng vẫn giữ yếu tố thứ tự.
English