Mối quan hệ giữa Tam giác Pascals và sự kết hợp
|
Trong bài viết trước về tam giác Pascal, tôi đã trình bày cách rút ra các công thức cho hoán vị và tổ hợp và tại sao chúng tương ứng với các hệ số nhị thức. Các công thức này rất dễ rút ra. Khi làm bài tập, tôi đã thử rút ra công thức cho các kết hợp cho phép lặp lại và thấy rất khó. Tôi gần như đã bỏ cuộc nhưng một người bạn đã động viên tôi rằng “Bạn đã dành một tháng cho nó rồi, bạn có thể tiếp tục. ” Không chắc đó là lời khuyên hợp lý nhưng tôi rất vui vì đã làm theo vì nó đã mang lại kết quả. Bài đăng này đi sâu hơn vào tam giác trêu ngươi Show Một lời nhắc nhở. (5 chọn 3) cho phép lặp lại có nghĩa là. chọn 3 biểu tượng từ 5 biểu tượng, cho phép lặp lại. (5 chọn 3) với các lần lặp lại sử dụng các ký hiệu ABCDE, chúng ta có thể bắt đầu liệt kê các kết hợp như vậy Công thức thông thường cho các kết hợp (n chọn k) không cho phép lặp lại và là Tôi đã cố gắng xem liệu có mối quan hệ tương tự giữa các hoán vị và tổ hợp khi cho phép lặp lại hay không nhưng tôi không thể xác định các nhóm có cùng kích thước trong số các hoán vị, tức là. Tôi không thể tìm thấy một yếu tố chung Tôi đã cố gắng tìm kiếm các mẫu khác nhưng tôi gặp khó khăn. tôi đã thất vọng. Tôi đã hỏi những người bạn toán của tôi. Một trong số họ đã nói điều gì đó về cách những thứ này hình thành từ một trường hợp cơ bản. Tôi không biết làm thế nào để sử dụng lời khuyên đó. Một người bạn khác trấn an tôi rằng đó là một vấn đề không tầm thường và tôi không nên bỏ cuộc. Tôi biết có một công thức, vì vậy tôi biết điều đó là có thể. Nó giống như biết rằng người khác đã leo lên thành công một ngọn núi mà dường như tôi không thể leo lên được Tôi quay lại bảng vẽ và cố gắng hiểu cách các kết hợp được xây dựng theo cách đệ quy. Tôi đã thử các ví dụ nhỏ và thấy cấu trúc đệ quy là Tôi sử dụng r ở đây có nghĩa là (n chọn k) cho phép lặp lại. Tôi tìm thấy cấu trúc này bằng cách sử dụng các ví dụ nhỏ, như Hãy tìm hiểu kỹ vấn đề này để hiểu tại sao nó lại như vậy (nếu nội dung này làm bạn khó chịu, hãy bỏ qua phần tiếp theo). (3 chọn 2)r cho ta 6 tổ hợp sau Cột đầu tiên là các kết hợp của (3 chọn 1)r và chúng ta chỉ cần dán chữ A trước chúng - đó là tất cả các kết hợp có thể có liên quan đến A. Sau đó, chúng tôi lấy A ra và làm điều tương tự. cột thứ hai là các tổ hợp của (2 chọn 1)r, tại đó là tất cả các tổ hợp liên quan đến B. Sau đó, chúng tôi chỉ còn lại C, đó là (1 chọn 1)r Khi chúng ta (n chọn k) cho phép lặp lại, k thực sự có thể lớn hơn n. Công thức đệ quy cũng hoạt động cho những ví dụ đó Khi tôi đang xác minh công thức đệ quy với các ví dụ phức tạp hơn, tôi nhận thấy một số con số trông quen thuộc Đó là những con số từ tam giác Pascal Điều đó có nghĩa là chúng tương ứng với các tổ hợp bình thường-không-lặp lại, (n chọn k), số. Tôi đã viết ra một ánh xạ từ một số ví dụ Và tìm thấy mối tương quan là Có nghĩa là công thức là Tôi đã rất phấn khích khi tìm thấy điều này vì đây là câu đố khó nhất mà tôi đã phải vật lộn trong một thời gian. Tôi đã xác minh công thức của mình bằng cách so sánh kết quả với hàm trong mô-đun tổ hợp python cho n và k lớn Tôi muốn hiểu tại sao các công thức hoạt động. Tôi tò mò tại sao (n chọn k) cho phép lặp lại bằng (n+k-1 chọn k). Tôi nhìn chằm chằm vào một số kết hợp với sự lặp lại cho đến khi tôi tìm ra cách tạo ra mối tương quan. Tôi đã thay thế các ký hiệu lặp lại bằng các ký hiệu mới và nhận được mối tương quan Điều này cho thấy (3 chọn 2)r = (4 chọn 2). Một ví dụ phức tạp hơn Điều này cho thấy (3 chọn 3)r = (5 chọn 3) Nếu chúng ta liệt kê các kết hợp theo thứ tự, chúng ta có thể thay thế các lần lặp lại bằng cách giới thiệu một ký hiệu mới có nghĩa là “lặp lại ký hiệu ở vị trí x”. Để có thể lặp lại một biểu tượng trước đó, chúng ta cần tồn tại ít nhất biểu tượng đầu tiên, nghĩa là chúng ta có thể có tối đa k-1 biểu tượng mới. Và đó là một cách giải thích tại sao (n chọn k) có lặp lại tương đương với (n+k-1 chọn k) không có lặp lại. Gọn gàng, phải không? Các số biểu thị các tổ hợp cho phép lặp lại là các số trong tam giác Pascal, giống như các số biểu thị các tổ hợp không lặp lại. Hãy so sánh các “ánh xạ”. Đây là ánh xạ thông thường cho các kết hợp không lặp lại (các hệ số nhị thức) Ta có thể áp dụng ánh xạ (n chọn k) = (n + k-1 chọn k) để có được ánh xạ cho các tổ hợp có số lần lặp lại Chúng ta biết rằng các số trong tam giác Pascal là tổng của hai đường chéo phía trên nó. Từ đó, chúng ta có thể rút ra quy tắc đệ quy về các kết hợp có lặp lại Hãy thuyết phục bản thân rằng điều này hiệu quả bằng cách sử dụng (3 chọn 3) cho phép lặp lại các ký hiệu ABC làm ví dụ. Nếu chúng ta liệt kê (3 chọn 2) cho phép lặp lại và dán chữ A trước chúng làm lựa chọn cuối cùng thì chúng ta có tất cả các kết hợp chứa A Những gì còn lại là các kết hợp cho phép lặp lại bằng các ký hiệu khác ngoài A Đó là 6 + 4 = 10 kết hợp, tính ra Tôi rất vui vì đã hiểu rõ hơn về công thức nhưng vẫn có điều gì đó làm tôi băn khoăn. Một trong những ý tưởng đầu tiên của tôi để tìm ra công thức là. nói rằng chúng tôi đang kết hợp các muỗng kem và cho phép lặp lại. Giả sử chúng tôi có 5 hương vị và chúng tôi muốn làm kem với 4 muỗng. Đây là (5 chọn 4) với sự lặp lại. Sau đó, một quy trình sẽ là tìm tất cả các cách chúng ta có thể tính tổng thành 4 — (4),(3,1),(2,2),(2,1,1),(1,1,1,1) và . Ví dụ, sắp xếp thứ nhất với 4 muỗng một vị, ta sẽ có 5 khả năng. Sau đó, đối với (2,1,1), chúng tôi muốn 2 muỗng có cùng hương vị và hai muỗng độc đáo khác nhau. chúng ta có (5 chọn 3) cách kết hợp hương vị, nhưng sau đó với mỗi cách kết hợp hương vị, chúng ta phải hoán đổi hương vị nào có 2 muỗng, vì vậy (5 chọn 3) * 3 Để tính toán (n chọn k) hoặc (num_flavours chọn num_scoops) với số lần lặp lại bằng quy trình này, chúng ta có thể thực hiện như sau
Loại quy trình từng bước này được gọi là thuật toán - công cụ khoa học máy tính. Nó phức tạp hơn công thức. Không có lý do gì bạn muốn tính toán nó như thế này nếu có một công thức đại số. Tôi chỉ muốn xem liệu có mối quan hệ nào giữa các số ở bước 1 (số cách tính tổng thành k bằng cách sử dụng các số tự nhiên nhỏ hơn nó) và số lần lặp lại (n chọn k). Tôi đã thầm mong những tổng-số này cũng sẽ là số tam giác Pascal. Tôi đã cố gắng tìm một công thức cho chúng nhưng không thể. Hóa ra khái niệm về các tổng-số này là Phân vùng trong lý thuyết số. Dường như không có công thức cho chúng nên chúng phải được tính toán bằng thuật toán Trong khi tôi đang cố gắng tìm một công thức cho các phân vùng, tôi đã tìm thấy một mối quan hệ thú vị khác khái quát hóa là Hãy tự thuyết phục bản thân rằng điều này phù hợp với ví dụ (4 chọn 4)r giống với (7 chọn 4) vì như thể chúng ta có thêm 3 ký hiệu cho chúng ta biết vị trí nào sẽ lặp lại (1. k-1). Chúng tôi muốn số lượng kết hợp của 4 ký hiệu trong số 7 ký hiệu này Đầu tiên hãy tưởng tượng chúng ta muốn tạo các kết hợp bằng cách sử dụng tất cả các ký hiệu phụ Chỉ còn một chỗ cho các biểu tượng ban đầu. Vậy có (4 chọn 1) cách chọn các kí hiệu chính và có (3 chọn 3) hoặc chỉ có 1 cách chọn các kí hiệu phụ. Vì vậy, có (4 chọn 1) * (3 chọn 3) kết hợp loại này. AEFG, BEFG, CEFG, DEFG. Vì các ký hiệu bổ sung của chúng tôi có nghĩa là lặp lại vị trí thứ nhất, lặp lại vị trí thứ 2 và lặp lại vị trí thứ 3, nên các kết hợp này tương ứng với AAAA, BBBB, CCCC, DDDD Bây giờ, hãy tưởng tượng chúng ta muốn tạo các kết hợp chỉ bằng hai trong số các ký hiệu phụ. Có (3 chọn 2) cách chọn từ 2 biểu tượng phụ và đối với mỗi trong số này, chúng ta có thể chèn (4 chọn 2) cặp ký hiệu chính. Ví dụ: tất cả các kết hợp có thể có từ cách sắp xếp đầu tiên là. AEFB, AEFC, AEFD, BEFC, BEFD, CEFD. Chúng tương ứng với AAAB, AAAC, AAAD, BBBC, BBBD, CCCD. Vì vậy, có (3 chọn 2) * (4 chọn 2) chuỗi loại này Chúng tôi có thể tiếp tục bằng cách tạo các kết hợp chỉ với một biểu tượng phụ và sau đó không có biểu tượng nào Cuối cùng, tôi muốn chỉ ra một thuộc tính tuyệt đẹp và đơn giản của các số đại diện cho các kết hợp Dễ thấy nhưng không rõ ràng ngay rằng các đường chéo là tổng của các tổng… (∑ i là ký hiệu tổng). Nếu chúng ta vẽ các cây tổ hợp, chúng ta có thể thấy một cách hình ảnh rằng chúng là tổng của tổng của tổng. Đây là những cây cho (5 chọn 3) Và đây là số tương đương cho (3 chọn 3) với số lần lặp lại Vấn đề là, nếu chúng ta thấy những cái cây xuất hiện như thế này, thì chúng ta biết đó phải là một số tổ hợp, một số từ Tam giác Ồ. Tất cả những gì tôi muốn làm là rút ra công thức kết hợp với các lần lặp lại như một bài tập và tôi tìm ra tất cả những điều này. Tôi cũng chưa kết thúc cuộc điều tra của mình. Tôi nóng lòng muốn xuất bản bài này để có thể bắt đầu bài tiếp theo. Tôi đang đọc qua viễn cảnh lịch sử tuyệt vời này về những đột phá của toán học vào Tam giác Tại sao các kết hợp trong tam giác Pascal?Kết hợp. Một cách khác để tìm các giá trị trong Tam giác Pascal hoặc các hệ số của khai triển nhị thức là sử dụng các kết hợp. Các tổ hợp thường được sử dụng trong xác suất để tìm số cách sắp xếp các đối tượng được chọn từ một nhóm đối tượng .
Tam giác Pascal có phải là tổ hợp không?Trong toán học, tam giác Pascal là một dãy tam giác gồm các hệ số nhị thức phát sinh trong lý thuyết xác suất, tổ hợp và đại số .
Mối quan hệ của định lý nhị thức với sự kết hợp là gì?Tổ hợp (nr) được gọi là hệ số nhị thức . Một ví dụ về hệ số nhị thức là (52)=C(5,2)=10 ( 5 2 ) = C ( 5 , 2 ) = 10.
Nêu mối quan hệ giữa khai triển tam giác Pascal và khai triển nhị thức?Tam giác Pascal cung cấp cho chúng ta các hệ số cho một nhị thức khai triển có dạng (a + b) n , trong đó n là hàng của . Định lý nhị thức cho chúng ta biết rằng chúng ta có thể sử dụng các hệ số này để tìm toàn bộ nhị thức khai triển, với một vài thủ thuật bổ sung được đưa vào. . The Binomial Theorem tells us we can use these coefficients to find the entire expanded binomial, with a couple extra tricks thrown in. |
