Nếu bạn chưa quen với việc chia mặt phẳng, cứ vào ở đây trước đã. Chỉ cần 10 giây để hiểu thôi.
Tôi đang gặp một chút rắc rối với một bài toán mà tôi đã xem xét. Khi bạn thử nghiệm với việc cắt mặt phẳng, bạn sẽ thấy rằng có nhiều cách khác nhau để cắt mặt phẳng.
Ví dụ, với 3 đường cắt, bạn có thể làm cho tất cả chúng song song, tất cả chúng đi qua cùng một điểm, hai đường song song và một đường cắt cả hai, và tất cả cắt nhau thành một tam giác. Tóm lại, có 4 cách để chia mặt phẳng bằng 3 đường thẳng.
Với 0 đường, 1 cách
L(1)=1
L(2)=2
L(3)=4
L(4)=9 8
L(5)=~~~49~~ 16
Rõ ràng, có một sự bùng nổ tổ hợp.
Vấn đề là, tôi không thể tìm thấy một dãy số toán học nào khác khớp với dãy này. 5 số hạng đầu tiên khớp với số Motzkin (Và ban đầu tôi nghĩ đó là câu trả lời), nhưng rõ ràng số hạng thứ 6 lớn hơn nhiều so với 21.
Vậy có tên gọi cho dãy này không?
Đã có ai giải được công thức chưa?
Cảm ơn trước.
CHỈNH SỬA: Như ai đó đã chỉ ra, tôi đã không giải thích “khác nhau” một cách rõ ràng.
Tôi định nghĩa khác nhau là: Khi tôi lấy mỗi vùng làm đỉnh của một đồ thị, và nối các đỉnh liền kề (qua các cạnh), chúng tạo thành một đồ thị không đẳng cấu với mọi đồ thị khác.
Ngoài ra, nếu bạn muốn, tôi có thể cho bạn xem tôi đã đi xa đến đâu nếu bạn đủ can đảm để kiểm tra L(5).
_____________________
-==TÓM TẮT QUÁ DÀI==-
Trong khi tìm kiếm câu trả lời, chúng tôi nhận ra rằng cách tốt nhất để tìm kiếm các cách sắp xếp khác nhau là xem xét tập hợp đỉnh cho mỗi cách sắp xếp các đường thẳng.
Ví dụ, tập hợp đỉnh cho cách sắp xếp này trên 4 đường thẳng sẽ là {3,1,1,1}. Bất kỳ đỉnh nào có nhiều hơn hai đường thẳng đều được tính là tổng của mỗi đường thẳng giao với mọi đường thẳng khác như sau.
Có một trường hợp đặc biệt nữa cần giải quyết. Các đường thẳng song song được tính theo họ, tương tự như các đỉnh có nhiều đường thẳng. Chúng có thể được coi là một “hương vị” khác, vì những đường này chỉ cắt nhau ở vô cực. Ví dụ, cách sắp xếp này trên 4 đường thẳng có tập hợp đỉnh là {3,1,1,1}, trong đó bất kỳ số nào không in đậm, in nghiêng là một đỉnh ở vô cực (hai hoặc nhiều đường thẳng song song với nhau).
Để kiểm tra xem một tập hợp đỉnh tùy ý trên n đường thẳng có hợp lệ hay không, chúng ta phải tạo một đồ thị có hướng với n+v đỉnh, trong đó n là số đường thẳng và v là số đỉnh (lực lượng của tập hợp đỉnh). Tương tự như [thuật toán Havel-Hakimi](http://en.wikipedia.org/wiki/Degree_(graph_theory)(#Degree_sequence), bạn có thể tạo một đồ thị có hướng cho thấy các đường A, B, C, v.v. tương tác với nhau như thế nào. [sẽ được giải thích chi tiết hơn sau]
Từ đây, rõ ràng là tổng của mỗi phần tử của tập hợp đỉnh phải là n(n-1)/2, và một tập hợp đỉnh phải được tạo thành từ 1, 3, 6, 10, v.v. (Số tam giác), và các biến thể đường song song.
Các vấn đề lớn chưa được giải quyết:
Có công thức hoặc thuật toán nào cho bạn phân hoạch của một số tam giác thành các số tam giác không?
Có thuật toán nào nhanh hơn để kiểm tra tính hợp lệ của một tập hợp đỉnh tương tự như định lý Erdős-Gallaikhông?
Có bất kỳ quy tắc nào chi phối số lượng của bất kỳ một số nào có thể có trong một tập hợp đỉnh không? [ví dụ: có luôn phải có nhiều số 1 hơn các số khác không?]
Các họ song song và các họ đa đỉnh có liên quan đến nhau như thế nào? Có luôn phải có nhiều đỉnh ‘bình thường’ hơn các họ song song không?
