Số Catalan

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm
Tập hợp các cách nối điểm không cắt nhau (trên) và cắt nhau (dưới - 10 cách) trong tổng cộng 52 cách.

Trong toán tổ hợp, số Catalan là dãy các số tự nhiên xuất hiện nhiều trong các bài toán đếm, thường bao gồm những đối tượng đệ quy. Được đặt tên theo nhà toán học Đức Eugène Charles Catalan (1814–1894).

Số Catalan được định nghĩa như sau:

Những số catalan đầu dãy n = 0, 1, 2, 3, …là:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (sequence A000108 in OEIS).

Thuộc tính của số[sửa | sửa mã nguồn]

Định nghĩa thay thế cho Cn :

bằng với định nghĩa bên trên vì . Cho thấy Cn là một số nguyên, mà ta không thể thấy được trong công thức đầu tiên. Dưới đây là cách chứng minh đơn giản cho công thức trên.

Số catalan thỏa mãn mối quan hệ:

ta lại có,

Vì  chọn n số trong tập 2n số có thể chia làm 2 công việc: chọn i số trong n số đầu và sau đó chọn n-i số trong n số còn lại.

Ta lại có:

đây là cách dễ dàng hơn cho việc tính toán.

Một cách gần đúng, số Catalan có thể tính bằng:

Ý nghĩa của biểu thức trên là biểu thức gồm số Catalan n / biểu thức bên phải có giới hạn bằng 1 khi n → +∞. Một vài tài liệu chỉ viết rằng .[1] (Có thể chứng minh bằng phép tính xấp xỉ của Stirling với n!.)

Chỉ những số Cn có n = 2k − 1 là số lẻ. Còn lại đều là số chẵn.

Chỉ có 2 số Catalan là số nguyên tốC2 = 2 và C3 = 5.[citation needed]

Số Catalan có cách biểu diễn khác:

trong đó  Nghĩa là số Catalan là một lời giải của bài toán mômen Hausdorff trên đoạn [0, 4] thay vì [0, 1]. Các hàm đa thức trực giao có hàm trọng  trên  là

Ứng dụng trong toán tổ hợp[sửa | sửa mã nguồn]

Có nhiều bài toán tổ hợp mà kết quả là số Catalan. Quyển Enumerative Combinatorics: Volume viết bởi nhà toán học tổ hợp Richard P. Stanley gồm 66 bài toán với 66 cách diễn giải khác nhau về số Catalan. Sau đây là một số ví dụ, minh họa trường hợp C3 = 5 và C4 = 14.

Mạng lưới của 14 từ Dyck với độ dài 8 - được thể hiện theo cách lên, xuống.
  • Cn là số trong Dyck words[2] với độ dài 2n. Một từ Dyck là một chuỗi ký tự gồm n ký tự X và n ký tự Y, trong đó không có đoạn đầu dãy nào có nhiều ký tự Y hơn X. Ví dụ các dyck word độ dài 6:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  • Biểu diễn lại các từ Dyck, thay X bằng dấu mở ngoặc và Y bằng dấu đóng ngoặc, Cn đếm số cách biểu diễn các dấu mở, đóng ngoặc đúng:
((()))     ()(())     ()()()     (())()     (()())
  • Cn cũng là số cách để chia n+1 phần tử ra thành các nhóm riếng lẻ (nói cách khác là số cách thêm các dấu đỏng, mở ngoặc giữa các phần tử để được cách chia hợp lý - không bị lỗi dấu ngoặc). Ví dụ, với n = 3, chúng ta có 5 cách khác nhau để chia 4 phần tử:
((ab)c)d     (a(bc))d     (ab)(cd)     a((bc)d)     a(b(cd))
Cây có 5 lá.
  • Một ứng dụng quan trọng khác là trong cây nhị phân đầy đủ. (Một cây nhị phân là đầy đủ nếu mỗi nút đều có 2 hoặc không có nút con). Có nghĩa là Cn là số cây nhị phân đầy đủ có n+1 lá:
  • Cn là số cây có thứ tự, không giống nhau (giống về hình học) có n nút. (Một cây có thứ tự là một cây có gốc mà các nút con của mỗi nút đều được đánh thứ tự từ trái qua phải)[3]
  • Cn là số đường đi đơn điệu theo các cầu trên một lưới có n × n ô vuông, mà không đi lên khỏi đường chéo. Một đường đi đơn điệu là một đường đi bắt đầu từ góc dưới trên, kết thúc ở góc trên phải, chỉ đi theo hướng qua phải hoặc đi lên. Đếm số đường đi cũng giống như Dyck word: X biểu thị cho "qua phải" và Y biểu thị cho "đi lên".

Ảnh minh họa cho trường hợp n = 4:

Có thể biểu diễn lại bằng danh sách phần tử Catalan bơi độ cao cột:[4]

[0,0,0,0][0,0,0,1][0,0,0,2][0,0,1,1]
[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2][0,0,2,2][0,0,1,3]
[0,0,2,3][0,1,1,3] [0,1,2,2][0,1,2,3]
Các tam giác phụ thuộc vào các nút của cây nhị phân
  • Cn là số cách khác nhau để chia một đa giác lồi có n+2 cạnh thành các tam giác bằng cách nối các đỉnh của đa giác lại mà không cắt nhau (một dạng của phép đạc tam giác từ đa giác). Bên dưới là minh họa các lục giác với n = 4:
  • Cn là số hoán vị sắp xếp được trên ngăn xếp của dãy {1,..., n}. Một hoán vị sắp xếp được trên ngăn xếp nếu S(w) = (1, ..., n), khi S(w) được xác định như sau: viết wunv khi n là phần tử lớn nhất trong w và u và v ở thứ tự thấp hơn, và tập S(w) = S(u)S(v)n, với S được xem như là dãy một phần tử. Đây là những hoán vị tránh từ 231.
  • Cn số hoán vị của {1, ..., n} tránh mẫu hình 123 (hoặc bất kỳ mẫu hình có độ dài 3); có nghĩa là số hoán vị mà không có bất ký 3 ký tự tăng dần. Với n = 3, những hoán vị là 132, 213, 231, 312 and 321. For n = 4, they are 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321.
  • Cn là số cách phân chia không cắt nhau của tập  {1, ..., n}. Tất nhiên, Cn không bao giờ lớn hơn số Bell thứ n. Cn cũng là số cách phân tập không cắt nhau của {1, ..., 2n} trong trường hợp mỗi khối kích cỡ 2.
  • Cn là số cách dựng hình bậc thang độ cao n với n hình chữ nhật. Hình dưới đây minh họa trường hợp n = 4:
  • Cn là số cây nhị phân có gốc với n nút trong (n+1 lá). Minh họa trong biểu độ bên dưới là những cây với n = 0,1,2 và 3. Kết quả là 1, 1, 2, và 5 theo thứ tự. Ở đây, chúng ta xét những cây mà mỗi nút có 2 hoặc không có nút con. Những nút bên trong là những nút có 2 nút con..
  • Clà số cách để vẽ hình núi với n nét lên và n nút xuống (không vượt xuống đường biên dưới). Tức là dãy núi không thấp hơn đường chân trời.
Catalan Number
  • Cn là số hoạt cảnh của một hình của chữ nhật 2-n. Nói cách khác, là số cách xếp các số 1, 2,... và một hình chữ nhật 2-n mà mỗi hàng và mỗi cột để tăng. Như vậy, công thức được rút ra từ một trường hợp đặc biệt của công thức độ dài Hook
  • Cn is the number of ways that the vertices of a convex 2n-gon can be paired so that the line segments joining paired vertices do not intersect. This is precisely the condition that guarantees that the paired edges can be identified (sewn together) to form a closed surface of genus zero (a topological 2-sphere).
  • Cn is the number of semiorders on n unlabeled items.[5]

Proof of the formula[sửa | sửa mã nguồn]

There are several ways of explaining why the formula

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). “Dynamic Programming”. Introduction to Algorithms. Cambridge, Massachusetts: The MIT Press. tr. 304. ISBN 0262031418. 
  2. ^ Equivalent definitions of Dyck paths
  3. ^ Stanley p.221 example (e)
  4. ^ ˇCrepinˇsek, Matej; Luka Mernik (2009). “AN EFFICIENT REPRESENTATION FOR SOLVING CATALAN NUMBER RELATED PROBLEMS” (PDF). International Journal of Pure and Applied Mathematics 56 (4). 
  5. ^ Kim, K. H.; Roush, F. W. (1978), “Enumeration of isomorphism classes of semiorders”, Journal of Combinatorics, Information &System Sciences 3 (2): 58–61, MR 538212 .