Có bao nhiêu cách khác nhau để sắp xếp hoặc chọn ra các phần tử từ một tập hợp? Hãy cùng tìm hiểu về hai khái niệm này trong toán học: Permutation và Combinations.
Permutation
Permutation là sự sắp xếp các đối tượng trong một tập hợp theo một trật tự nhất định. Nếu chúng ta có một tập hợp gồm n đối tượng và muốn sắp xếp r đối tượng từ tập hợp này theo một trật tự, ta gọi đó là một Permutation r hoặc một Permutation của n đối tượng được lấy r tại một thời điểm.
Ký hiệu cho Permutation là P(n, r).
Định lý: Chứng minh rằng số Permutation của n đối tượng là n!.
Ví dụ:
Làm thế nào để tính số cách xếp chữ số 1, 2, 3 thành một số gồm 3 chữ số mà không được phép lặp chữ số?
Lời giải:
Chúng ta có 3 vị trí để xếp các chữ số. Với vị trí đầu tiên, chúng ta có 3 lựa chọn (1, 2, 3). Với vị trí thứ hai, chúng ta chỉ còn 2 lựa chọn (vì đã sử dụng một chữ số ở vị trí đầu tiên). Cuối cùng, với vị trí thứ ba, chúng ta chỉ còn 1 lựa chọn (vì đã sử dụng hai chữ số ở vị trí trước đó).
Tổng số cách xếp chữ số là 3 2 1 = 6.
Permutation có hạn chế:
Có bao nhiêu số thỏa mãn điều kiện sau: gồm 6 chữ số từ các chữ số 0, 1, 2, 3, 4, 5, 6, 7, 8, mà không có số nào bắt đầu bằng ’30’ và không có số nào được lặp lại?
Lời giải: Tất cả các số bắt đầu bằng ’30’ đã bị loại trừ. Vì vậy, chúng ta chỉ có thể chọn 4 chữ số từ 7 chữ số còn lại.
Tổng số các số thỏa mãn là 7P4.
Permutation với các đối tượng lặp lại:
Định lý: Chứng minh rằng số Permutation của n đối tượng phân biệt được thực hiện tại một thời điểm với việc lặp lại một số lần bất kỳ là nr.
Chứng minh: Giả sử chúng ta có n đối tượng và cần điền vào r vị trí, cho phép lặp lại đối tượng.
Do đó, số cách để điền vào vị trí thứ nhất là n.
Số cách để điền vào vị trí thứ hai là n.
…
Số cách để điền vào vị trí thứ r là n.
Tổng số cách điền r vị trí với n đối tượng là n n … * n (r lần) = nr.
Permutation tròn:
Nếu chúng ta thực hiện một Permutation xung quanh một vòng tròn, ta gọi đó là Permutation tròn.
Ví dụ: Có bao nhiêu cách xếp các chữ cái a, b, c, d, e, f, g, h, i, j thành một hình tròn?
Lời giải: (10 – 1)! = 9!.
Định lý: Chứng minh rằng số Permutation tròn của n đối tượng khác nhau là (n-1)!.
Chứng minh: Với mỗi Permutation tròn, có n Permutation tuyến tính tương ứng. Điều này có nghĩa là chúng ta bắt đầu từ mọi đối tượng trong một Permutation tròn. Vì vậy, với K Permutation tròn, ta có K … n Permutation tuyến tính.
Combination
Combinations là sự lựa chọn một số hoặc tất cả các đối tượng từ một tập hợp đã cho, trong đó thứ tự của các đối tượng không quan trọng. Số lượng Combinations của n đối tượng, chọn r tại một thời điểm được biểu diễn bằng nCr hoặc C(n, r).
Chứng minh: Số Permutation của n đối tượng khác nhau, chọn r tại một thời điểm được cho bởi
Vì không có vấn đề gì về thứ tự sắp xếp các đối tượng, do đó, với mọi lựa chọn của r đối tượng, ta có r! sắp xếp, tức là,
Ví dụ: Một người nông dân muốn mua 3 con bò, 2 con lợn và 4 con gà mái từ một người đàn ông có 6 con bò, 5 con lợn và 8 con gà mái. Tìm số cách mà người nông dân có thể chọn.
Người nông dân có thể chọn bò theo cách C(6, 3), lợn theo cách C(5, 2) và gà mái theo cách C(8, 4). Do đó, số cách chọn là:
Tổng số cách chọn = C(6, 3) C(5, 2) C(8, 4).
Một số câu hỏi phổ biến về Permutation và Combinations
-
Permutation và combinations là gì?
Permutation và combinations là hai khái niệm trong toán học để đếm số cách sắp xếp hoặc chọn ra các phần tử từ một tập hợp cho trước. -
Permutation là gì?
Permutation là số cách sắp xếp các phần tử của một tập hợp theo một trật tự nhất định. Số permutation của một tập hợp n phần tử là n! (n giai thừa). -
Combinations là gì?
Combinations là số cách chọn ra k phần tử từ một tập hợp n phần tử mà không quan tâm đến thứ tự. Số combinations của một tập hợp n phần tử và k phần tử được tính bằng công thức C(n, k) = n!/[(n-k)!k!]. -
Công thức chung để tính số permutation và combinations là gì?
- Số permutation của n phần tử được tính bằng n!.
- Số combinations của n phần tử và k phần tử được tính bằng C(n, k) = n!/[(n-k)!k!].
- Permutation và combinations khác nhau như thế nào?
- Permutation liên quan đến sự sắp xếp các phần tử trong một tập hợp, trong khi combinations liên quan đến sự lựa chọn các phần tử trong một tập hợp mà không quan trọng đến thứ tự.
- Số permutation của một tập hợp n phần tử là n!, trong khi số combinations của một tập hợp n phần tử và k phần tử được tính bằng công thức C(n, k) = n!/[(n-k)!k!].
- Trong Python, có thư viện nào hỗ trợ tính số permutation và combinations không?
Trong Python, thư viện math hỗ trợ tính số permutation và combinations thông qua các hàm math.perm() và math.comb().
-
Hàm math.perm() trong Python trả về số permutation của n phần tử và k phần tử. Nó được tính bằng công thức n!/(n-k)!.
-
Hàm math.comb() trong Python trả về số combinations của n phần tử và k phần tử. Nó được tính bằng công thức n!/[(n-k)!k!].
- Làm thế nào để tính số permutation hoặc combinations trong Python nếu không sử dụng thư viện math?
Nếu không sử dụng thư viện math, ta có thể sử dụng đệ quy để tính số permutation hoặc combinations. Ví dụ: