Bài viết này sẽ tập trung vào một phần toán học đặc biệt được gọi là tổ hợp. Công thức, quy tắc, ví dụ về giải quyết vấn đề - tất cả những điều này bạn có thể tìm thấy ở đây bằng cách đọc đến cuối bài báo.
Vậy, phần này là gì? Phép tổ hợp giải quyết vấn đề đếm bất kỳ đối tượng nào. Nhưng trong trường hợp này, các đối tượng không phải là mận, lê hay táo, mà là một thứ khác. Phép toán tổ hợp giúp chúng ta tìm xác suất của một sự kiện. Ví dụ khi đánh bài, xác suất đối phương có quân bài tẩy là bao nhiêu? Hoặc một ví dụ như vậy - xác suất bạn nhận được chính xác màu trắng từ một túi hai mươi quả bóng là bao nhiêu? Đối với loại nhiệm vụ này, chúng ta cần biết ít nhất những kiến thức cơ bản của phần toán học này.
Cấu hình kết hợp
Xem xét vấn đề các khái niệm và công thức cơ bản của tổ hợp, chúng ta không thể không chú ý đến các cấu hình tổ hợp. Chúng không chỉ được sử dụng để xây dựng công thức mà còn được sử dụng để giải các bài toán tổ hợp khác nhau. Ví dụ về các mô hình như vậy là:
- vị trí;
- hoán vị;
- kết hợp;
- thành phần số;
- chia số.
Chúng ta sẽ nói chi tiết hơn về ba phần đầu tiên ở phần sau, nhưng chúng tôi sẽ chú ý đến bố cục và cách chia nhỏ trong phần này. Khi họ nói về thành phần của một số nhất định (giả sử, a), họ có nghĩa là biểu diễn của số a dưới dạng tổng có thứ tự của một số số dương. Và một phép chia là một tổng không có thứ tự.
Phần
Trước khi chúng ta đi thẳng vào các công thức của tổ hợp và xem xét các vấn đề, chúng ta cần chú ý đến thực tế là tổ hợp, giống như các phần khác của toán học, có các phần phụ riêng của nó. Chúng bao gồm:
- liệt kê;
- cấu;
- cực;
- Lý thuyết Ramsey;
- xác suất;
- tôpô;
- vô hạn.
Trong trường hợp đầu tiên, chúng ta đang nói về tổ hợp liệt kê, các bài toán xem xét liệt kê hoặc đếm các cấu hình khác nhau được tạo thành bởi các phần tử của tập hợp. Theo quy định, một số hạn chế được áp dụng đối với các tập hợp này (khả năng phân biệt, không thể phân biệt, khả năng lặp lại, v.v.). Và số lượng các cấu hình này được tính bằng cách sử dụng quy tắc cộng hoặc nhân, mà chúng ta sẽ nói về một chút sau. Tổ hợp cấu trúc bao gồm các lý thuyết về đồ thị và ma trận. Một ví dụ về bài toán tổ hợp cực trị là kích thước lớn nhất của đồ thị thỏa mãn các tính chất sau là gì … Trong đoạn thứ tư, chúng tôi đã đề cập đến lý thuyết Ramsey, lý thuyết nghiên cứu sự hiện diện của các cấu trúc thông thường trong các cấu hình ngẫu nhiên. Xác suấttổ hợp có thể trả lời câu hỏi - xác suất mà một tập hợp nhất định có một đặc tính nhất định là bao nhiêu. Như bạn có thể đoán, tổ hợp tôpô áp dụng các phương pháp trong tôpô. Và cuối cùng, điểm thứ bảy - tổ hợp nội bộ nghiên cứu việc áp dụng các phương pháp tổ hợp cho các tập hợp vô hạn.
Quy tắc cộng
Trong số các công thức của tổ hợp, ta có thể tìm thấy những công thức khá đơn giản mà chúng ta đã quen thuộc từ lâu. Một ví dụ là quy tắc tổng. Giả sử chúng ta được cung cấp hai hành động (C và E), nếu chúng loại trừ lẫn nhau, thì hành động C có thể được thực hiện theo một số cách (ví dụ, a) và hành động E có thể được thực hiện theo cách b, thì bất kỳ hành động nào trong số chúng (C hoặc E) có thể được thực hiện theo các cách a + b.
Về lý thuyết, điều này khá khó hiểu, chúng tôi sẽ cố gắng truyền đạt toàn bộ điểm bằng một ví dụ đơn giản. Hãy lấy số học sinh trung bình trong một lớp - giả sử là hai mươi lăm. Trong số đó có mười lăm cô gái và mười chàng trai. Một người phục vụ được chỉ định cho lớp hàng ngày. Có bao nhiêu cách phân công một bạn chủ nhiệm lớp hôm nay? Giải pháp cho vấn đề khá đơn giản, chúng ta sẽ dùng đến quy tắc cộng. Nội dung của nhiệm vụ không nói rằng chỉ con trai hay chỉ con gái mới có thể làm nhiệm vụ. Do đó, nó có thể là bất kỳ cô gái nào trong số mười lăm cô gái hoặc bất kỳ ai trong số mười chàng trai. Áp dụng quy tắc tổng, chúng ta nhận được một ví dụ khá đơn giản mà một học sinh tiểu học có thể dễ dàng đối phó với: 15 + 10. Nhẩm tính, ta được đáp số: 25. Đó là, chỉ có 25 cáchchỉ định một lớp nhiệm vụ cho ngày hôm nay.
Quy tắc nhân
Quy tắc nhân cũng thuộc các công thức cơ bản của tổ hợp. Hãy bắt đầu với lý thuyết. Giả sử chúng ta cần thực hiện một số hành động (a): hành động đầu tiên được thực hiện theo 1 cách, hành động thứ hai - theo 2 cách, hành động thứ ba - theo 3 cách, v.v. cho đến khi hành động a cuối cùng được thực hiện theo nhiều cách. Sau đó, tất cả các hành động này (mà chúng ta có tổng số) có thể được thực hiện theo N cách. Làm thế nào để tính N chưa biết? Công thức sẽ giúp chúng ta điều này: N \u003d c1c2c3…ca.
Một lần nữa, không có gì rõ ràng về mặt lý thuyết, hãy chuyển sang một ví dụ đơn giản về việc áp dụng quy tắc nhân. Chúng ta hãy học cùng một lớp có hai mươi lăm người, trong đó mười lăm nữ và mười nam học. Chỉ lần này chúng ta cần chọn hai tiếp viên. Họ có thể là chỉ trai hoặc gái, hoặc trai với gái. Chúng tôi chuyển sang giải pháp cơ bản của vấn đề. Chúng tôi chọn người phục vụ đầu tiên, như chúng tôi đã quyết định trong đoạn cuối, chúng tôi có 25 lựa chọn khả thi. Người thứ hai làm nhiệm vụ có thể là bất kỳ người nào trong số những người còn lại. Chúng tôi có hai mươi lăm học sinh, chúng tôi chọn một học sinh, có nghĩa là bất kỳ ai trong số hai mươi bốn người còn lại đều có thể là người thứ hai làm nhiệm vụ. Cuối cùng, chúng tôi áp dụng quy tắc nhân và thấy rằng hai người tham dự có thể được chọn trong sáu trăm cách. Chúng tôi nhận được số này bằng cách nhân với hai mươi lăm và hai mươi bốn.
Hoán đổi
Bây giờ chúng ta sẽ xem xét một công thức tổ hợp nữa. Trong phần này của bài viết, chúng tôiHãy nói về hoán vị. Hãy xem xét vấn đề ngay lập tức bằng một ví dụ. Hãy lấy quả bóng bi-a, chúng ta có số thứ n của chúng. Chúng ta cần tính toán: có bao nhiêu lựa chọn để sắp xếp chúng thành một hàng, nghĩa là tạo thành một tập hợp có thứ tự.
Hãy bắt đầu, nếu chúng ta không có bóng, thì chúng ta cũng không có lựa chọn vị trí nào. Và nếu chúng ta có một quả bóng, thì cách sắp xếp cũng giống nhau (về mặt toán học, điều này có thể được viết như sau: Р1=1). Hai quả bóng có thể được sắp xếp theo hai cách khác nhau: 1, 2 và 2, 1. Do đó, Р2=2. Ba quả bóng có thể được xếp theo sáu cách (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Và nếu không có ba quả bóng như vậy, mà là mười hoặc mười lăm? Để liệt kê tất cả các tùy chọn có thể là rất dài, sau đó tổ hợp sẽ hỗ trợ chúng tôi. Công thức hoán vị sẽ giúp chúng ta tìm ra câu trả lời cho câu hỏi của mình. Pn=nP (n-1). Nếu chúng ta cố gắng đơn giản hóa công thức, chúng ta nhận được: Pn=n(n - 1) …21. Và đây là tích của các số tự nhiên đầu tiên. Một số như vậy được gọi là giai thừa và được ký hiệu là n!
Hãy xem xét vấn đề. Người lãnh đạo mỗi sáng xây dựng đội của mình thành một hàng (hai mươi người). Có ba người bạn thân nhất trong biệt đội - Kostya, Sasha và Lesha. Xác suất để chúng ở cạnh nhau là bao nhiêu? Để tìm câu trả lời cho câu hỏi, bạn cần chia xác suất của một kết quả "tốt" cho tổng số kết quả. Tổng số các hoán vị là 20!=2,5 tạ tỷ. Làm thế nào để đếm số lượng kết quả "tốt"? Giả sử rằng Kostya, Sasha và Lesha là một siêu nhân. Sau đó chúng tôiChúng tôi chỉ có mười tám môn học. Số hoán vị trong trường hợp này là 18=6,5 phần tư. Với tất cả những điều này, Kostya, Sasha và Lesha có thể tùy ý di chuyển giữa mình trong bộ ba không thể phân chia của họ, và đây là 3 người nữa!=6 tùy chọn. Vì vậy, chúng tôi có tổng cộng 18 chòm sao "tốt"!3! Chúng ta chỉ cần tìm xác suất mong muốn: (18!3!) / 20! Con số này xấp xỉ 0,016. Nếu quy đổi thành phần trăm, nó hóa ra chỉ là 1,6%.
Chỗ ở
Bây giờ chúng ta sẽ xem xét một công thức tổ hợp khác rất quan trọng và cần thiết. Chỗ ở là vấn đề tiếp theo của chúng tôi, mà chúng tôi khuyên bạn nên xem xét trong phần này của bài viết. Chúng ta sẽ trở nên phức tạp hơn. Giả sử rằng chúng ta muốn xem xét các hoán vị có thể xảy ra, không chỉ từ toàn bộ tập (n), mà từ một tập nhỏ hơn (m). Tức là, chúng ta coi các hoán vị của n mục bằng m.
Các công thức cơ bản của tổ hợp không nên chỉ học thuộc mà phải hiểu. Ngay cả khi thực tế là chúng trở nên phức tạp hơn, vì chúng ta không có một tham số, mà là hai. Giả sử rằng m \u003d 1, sau đó A \u003d 1, m \u003d 2, sau đó A \u003d n(n - 1). Nếu chúng ta đơn giản hóa công thức hơn nữa và chuyển sang ký hiệu bằng cách sử dụng giai thừa, chúng ta sẽ nhận được một công thức khá ngắn gọn: A \u003d n! / (n - m)!
Kết hợp
Chúng tôi đã xem xét gần như tất cả các công thức cơ bản của tổ hợp với các ví dụ. Bây giờ chúng ta hãy chuyển sang giai đoạn cuối cùng của việc xem xét khóa học cơ bản của tổ hợp - làm quen với tổ hợp. Bây giờ chúng ta sẽ chọn m mục từ n mà chúng ta có, trong khi chúng ta sẽ chọn tất cả chúng theo tất cả các cách có thể. Vậy thì điều này khác với chỗ ở như thế nào? Chúng tôi sẽ khôngxem xét đơn đặt hàng. Tập hợp không có thứ tự này sẽ là sự kết hợp.
Giới thiệu ngay kí hiệu: C. Chúng ta diễn ra các vị trí của m quả bóng trong số n. Chúng tôi ngừng chú ý đến thứ tự và nhận được các kết hợp lặp lại. Để có số kết hợp, chúng ta cần chia số vị trí cho m! (m giai thừa). Đó là, C \u003d A / m! Như vậy, có một số cách chọn từ n quả bóng, xấp xỉ bằng số cách chọn hầu hết mọi thứ. Có một cách diễn đạt hợp lý cho điều này: lựa chọn một chút cũng giống như việc vứt bỏ hầu hết mọi thứ. Điều quan trọng cần đề cập tại thời điểm này là số lượng kết hợp tối đa có thể đạt được khi cố gắng chọn một nửa số mục.
Làm thế nào để chọn một công thức để giải quyết một vấn đề?
Chúng ta đã xem xét chi tiết các công thức cơ bản của tổ hợp: vị trí, hoán vị và tổ hợp. Bây giờ nhiệm vụ của chúng ta là tạo điều kiện cho việc lựa chọn công thức cần thiết để giải bài toán trong tổ hợp. Bạn có thể sử dụng lược đồ khá đơn giản sau:
- Tự hỏi bản thân: thứ tự của các yếu tố có được tính đến trong nội dung của bài toán không?
- Nếu câu trả lời là không, thì hãy sử dụng công thức kết hợp (C=n! / (M!(N - m)!)).
- Nếu câu trả lời là không, thì bạn cần trả lời thêm một câu hỏi nữa: có phải tất cả các phần tử được đưa vào tổ hợp không?
- Nếu câu trả lời là có, thì hãy sử dụng công thức hoán vị (P=n!).
- Nếu câu trả lời là không, thì hãy sử dụng công thức phân bổ (A=n! / (N - m)!).
Ví dụ
Chúng tôi đã xem xét các yếu tố của tổ hợp, công thức và một số vấn đề khác. Bây giờ chúng ta hãy chuyển sangđang xem xét một vấn đề thực tế. Hãy tưởng tượng rằng bạn có một quả kiwi, một quả cam và một quả chuối trước mặt bạn.
Câu hỏi một: chúng có thể được sắp xếp lại theo bao nhiêu cách? Để làm điều này, chúng tôi sử dụng công thức hoán vị: P=3!=6 cách.
Câu hỏi hai: một loại trái cây có thể được chọn trong bao nhiêu cách? Đây là điều hiển nhiên, chúng tôi chỉ có ba lựa chọn - chọn kiwi, cam hoặc chuối, nhưng chúng tôi áp dụng công thức kết hợp: C \u003d 3! / (2!1!)=3.
Câu ba: Có bao nhiêu cách chọn hai loại trái cây? Chúng tôi có những lựa chọn nào? Kiwi và cam; kiwi và chuối; cam và chuối. Đó là, ba tùy chọn, nhưng điều này rất dễ kiểm tra bằng cách sử dụng công thức kết hợp: C \u003d 3! / (1!2!)=3
Câu hỏi bốn: Có bao nhiêu cách chọn ba loại trái cây? Như bạn thấy, chỉ có một cách để chọn ba loại trái cây: lấy một quả kiwi, một quả cam và một quả chuối. C=3! / (0!3!)=1.
Câu hỏi năm: Bạn có thể chọn ít nhất một loại trái cây bao nhiêu cách? Điều kiện này ngụ ý rằng chúng ta có thể lấy một, hai hoặc cả ba quả. Do đó, chúng ta thêm C1 + C2 + C3=3 + 3 + 1=7. Tức là chúng ta có bảy cách để lấy ít nhất một miếng trái cây từ bảng.
