Công cụ máy tính tổ hợp

Có nhiều cách khác nhau để tính số cách chọn các phần tử từ một tập hợp nhất định trong toán học. Vậy có bao nhiêu cách chúng ta có thể chọn r kết quả từ n khả năng? Nó phụ thuộc vào yếu tố thứ tự sắp xếp có quan trọng hay không, và các giá trị có được lặp lại hay không.

Số cách chọn r kết quả và không quan trọng thứ tự sắp xếp từ n khả năng được gọi là tổ hợp và được viết là C (n, r). Nó còn được gọi là hệ số nhị thức. Công cụ máy tính này cho phép bạn tính toán số tổ hợp của r phần từ từ tập hợp n phần từ.

Quy tắc sử dụng công cụ máy tính tổ hợp

Đối với một tập hợp các phần tử nhất định, có một số cách nhất định để sắp xếp hoặc chọn một số hoặc tất cả chúng theo một thứ tự hoặc đặc điểm kỹ thuật nào đó. Công cụ máy tính tính toán số cách chọn r phần tử từ một tập hợp n phần tử mà không xẩy ra sự lặp lại và thứ tự sắp xếp không được xem là quan trọng. Máy tính này yêu cầu hai đầu vào:

• n = số lượng phần tử riêng biệt để lựa chọn, và
• r = số lượng phần tử cần chọn.

Một tiêu chí quan trọng khi nhập dữ liệu vào máy tính tổ hợp là

$$0 ≤ r ≤ n$$

Nếu bạn nhập r lớn hơn n, máy tính sẽ đưa ra thông báo

"Vui lòng nhập 0 ≤ r ≤ n".

Nguyên tắc đếm cơ bản

Nguyên tắc đếm cơ bản hướng dẫn chúng ta số cách hoàn thành các nhiệm vụ khác nhau. Có hai quy tắc đếm cơ bản.

Quy tắc tổng

Công việc thứ nhất có thể thực hiện theo m cách, công việc thứ hai có thể thực hiện theo n cách. Nếu các công việc không thể được thực hiện đồng thời thì số cách có thể được tính là (m + n).

Quy tắc nhân

Công việc thứ nhất có thể thực hiện theo m cách và công việc thứ hai có thể thực hiện theo n cách. Nếu cả hai công việc có thể được thực hiện đồng thời thì có (m × n) cách thực hiện.

Ví dụ

Quầy phục vụ có bán 3 loại bánh và 4 loại đồ uống. Trong đó có bánh táo, bánh dâu và bánh việt quất. Và nước cam, nước nho, nước anh đào và nước dứa. Mỗi đồ uống và bánh đều được bán với giá 2 đô la. Bạn chỉ mang theo 2 đô la, ngoài ra không có thêm một xu nào. Vì vậy, bạn có 3 + 4 = 7 cơ hội lựa chọn.

Giả sử bạn muốn đếm số cách tung đồng xu và tung xúc xắc. Số mặt lật đồng xu là 2 vì đồng xu có 2 mặt. Tương tự như vậy, xúc xắc có 6 mặt lật khác nhau. Nếu có thể thực hiện cả hai việc cùng một lúc thì có 2 × 6 = 12 cách để bạn có thể lật một đồng xu và tung xúc xắc.

Nếu bạn muốn rút 2 lá bài từ bộ bài 52 lá mà không thay thế chúng thì có 52 cách rút lá thứ nhất và 51 cách rút lá thứ hai. Do đó, số cách rút hai lá bài là 52 × 51 = 2.652.

Không gian mẫu

Không gian mẫu là danh sách tất cả các kết quả có thể xảy ra và được biểu thị bằng chữ in hoa S. Không gian mẫu khi tung đồng xu và tung xúc xắc đồng thời là

S = {{H,1}, {H,2}, {H,3}, {H,4}, {H,5}, {H,6}, {T,1}, {T,2 }, {T,3}, {T,4}, {T,5}, {T,6}}

Có mười hai cách có thể. Nguyên tắc đếm cho phép chúng ta tìm ra số cách, số trường hợp xẩy ra mà không cần phải liệt kê ra chi tiết.

Tổ hợp

Số cách có thể chọn r kết quả không lặp lại từ n khả năng khi thứ tự sắp xếp không được xem là quan trọng được gọi là tổ hợp. Tổ hợp của các phần tử được viết là C (n, r). Nó còn được gọi là hệ số nhị thức. Công thức tổ hợp được định nghĩa là:

$$C(n,r)=\frac{n!}{r!(n-r)!}$$

Dấu "!" sau một số hoặc một chữ cái có nghĩa là chúng ta đang ám chỉ giai thừa của một số nào đó. Ví dụ, n! là giai thừa của số n - hoặc tích của các số tự nhiên từ 1 đến n. Giai thừa của số 2 là 1 × 2. Giai thừa của số 3 là 1 × 2 × 3. Giai thừa của số 4 là 1 × 2 × 3 × 4. Giai thừa của số 5 là 1 × 2 × 3 × 4 × 5. Giai thừa chỉ có thể được tính đối với số nguyên không âm.

Một đặc điểm quan trọng khi tính toán tổ hợp bằng công thức này là không được phép lặp lại các phần tử và thứ tự sắp xếp được xem là không quan trọng.

Ví dụ 1

Giả sử bạn có một tập hợp bốn số

{1, 2, 3, 4}

Có bao nhiêu cách để kết hợp hai phần tử từ tập hợp này nếu phần tử giống nhau không được lặp lại trong một cặp, như (1,1), (2,2)... là không hợp lệ?

Nếu thứ tự của các phần tử được coi là quan trọng, chúng ta sẽ có các nhóm được hình thành theo cách hoán vị:

(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)

Nếu thứ tự không được coi là quan trọng - chúng ta nhận được các nhóm được hình thành theo cách tổ hợp:

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)

Có 6 sự tổ hợp. Bạn có thể sử dụng công thức ở trên để tìm số lượng tất cả các tổ hợp có thể có. Trong ví dụ này, $n=4$, $r=2$. Vì vậy,

$$C(4,2)=\frac{4!}{2!(4-2)!}=\frac{4!}{2!2!}=\frac{4 × 3 × 2 × 1}{(2× 1)(2× 1)}=\frac{24}{4}=6$$

Đây chính xác là kết quả mà Công cụ máy tính tổ hợp này tính ra.

Ví dụ 2

Tổ hợp 3 chữ cái trong số các chữ cái A, B, C và D là gì? Có 24 hoán vị có thể xảy ra khi thứ tự được xem là yếu tố quan trọng. Trong khi việc xác định các tổ hợp thì thứ tự không được xem là yếu tố quan trọng. Do đó, chỉ có hàng đầu tiên là phù hợp, tức là chỉ có 4 tổ hợp mà thôi.

ABC	ABD	ACD	BCD
ACB	ADB	ADC	BDC
BAC	BAD	CAD	CBD
BCA	BDA	CDA	CDB
CAB	DAB	DAC	DBC
CBA	DBA	DCA	DCB

Thay vì liệt kê tất cả các cách sắp xếp có thể xẩy ra, chúng ta có thể tính số cách sắp xếp có thể (trong đó thứ tự không quan trọng) bằng cách sử dụng công thức tổ hợp ở trên. Ở đây, có n=4 phần tử và bạn đang lấy r=3 phần tử cùng một lúc. Vì vậy,

$$C\left(n,r\right)=C\left(4,3\right)=\frac{4!}{\left(4-3\right)!3!}=\frac{4!}{1!3!}=4$$

Hoán vị

Hoán vị xác định cách sắp xếp các phần tử khi thứ tự của các phần tử được xem là quan trọng. Công thức hoán vị khi chọn r phần tử từ danh sách n phần tử như sau:

$$P\left(n,r\right)=\frac{n!}{\left(n-r\right)!}$$

Hai đặc điểm chính khi tính toán hoán vị bằng công thức này là không được phép lặp lại bất kỳ một phần tử nào và thứ tự của các phần tử được xem là yếu tố quan trọng.

Ví dụ 3

Giả sử có 4 ứng viên trong một cuộc phỏng vấn xin việc. Nhiệm vụ của hội đồng tuyển chọn là xếp hạng các ứng viên từ 1 đến 4. Dưới đây là các khả năng có thể xẩy ra:

• Ứng viên thứ 1 - có 4 cách chọn
• Ứng viên thứ 2 – có 3 cách chọn
• Ứng viên thứ 3 – có 2 cách chọn
• Ứng viên thứ 4 - chỉ có một cách chọn

Chúng ta có thể áp dụng quy tắc nhân để cho ra tổng số cách chọn, tức là 4 × 3 × 2 × 1 = 24 tương ứng với 4!. Gọi các ứng cử viên là

{A, B, C, D}

Không gian mẫu của bài toán hiển thị tất cả các hoán vị có thể có, được hiển thị bên dưới:

A ở vị trí thứ nhất	B ở vị trí thứ nhất	C ở vị trí thứ nhất	D ở vị trí thứ nhất
ABCD	BACD	CABD	DABC
ABDC	BADC	CADB	DACB
ACBD	BCAD	CBAD	DBAC
ACDB	BCDA	CBDA	DBCA
ADBC	BDAC	CDAB	DCAB
ADCB	BDCA	CDBA	DCBA

Thay vì liệt kê tất cả các cách sắp xếp có thể có như ở trong bảng trên, chúng ta có thể tính số cách sắp xếp bằng cách sử dụng công thức hoán vị. Đối với ví dụ trên, có n = 4 phần tử và bạn lấy r = 4 phần tử cùng một lúc. Vì vậy,

$$P\left(n,r\right)=P\left(4,4\right)=\frac{4!}{\left(4-4\right)!}=\frac{4!}{ 0!}=24$$

Sự khác biệt giữa Tổ hợp và Hoán vị

Sự khác biệt chính giữa tổ hợp và hoán vị là: trong tổ hợp, thứ tự của các phần tử không được xem là quan trọng, trong khi trong hoán vị, thứ tự sắp xếp của các phần tử lại được xem là quan trọng.