imported>Bluetpp: Đã lùi lại sửa đổi của ~2026-38261-70 (thảo luận) quay về phiên bản cuối của TheSecondFunnyYellowBot

2026-07-06T02:00:12Z

Đã lùi lại sửa đổi của ~2026-38261-70 (thảo luận) quay về phiên bản cuối của TheSecondFunnyYellowBot

Trang mới

[[Tập tin:Noncrossing partitions 5.svg|thumb|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 trong nhiều bài toán đếm, thường bao gồm những đối tượng đệ quy. Chúng được đặt tên theo nhà toán học [[Bỉ]] [[Eugène Charles Catalan]] (1814–1894).

Số Catalan thứ ''n'' được định nghĩa như sau:

<math>C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} = \prod_{k=2}^{n}\frac{n+k}{k} \text{ với } n \ge 0</math>

Những số catalan đầu tiên với ''n'' = 0, 1, 2, 3, …là:

:[[1 (số)|1]], 1, [[2 (số)|2]], [[5 (số)|5]], [[14 (số)|14]], [[42 (số)|42]], [[132 (số)|132]], 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (dãy [[oeis:A000108|A000108]] trên trang OEIS).

== Tính chất ==
Biểu thức thay thế cho ''C''''n'': <math>C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1} \binom{2n}{n} \text{ với } n \ge 0</math>

nó tương đương với biểu thức bên trên vì <math>\tbinom{2n}{n+1}=\tfrac{n}{n+1}\tbinom{2n}n</math>. Công thức này 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. Biểu thức này hình thành nền tảng cho bài chứng minh sự đúng đắn của công thức.

Số catalan thỏa mãn hệ thức truy hồi sau:

<math>C_0=1 \text{ và } C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} \text{ với } n \ge 0,</math>

<math>\sum_{ {i}_{1}+... + {i}_{m}=n, {i}_{1},...,{i}_{m} \ge 0 }^{} C_{i_{1}}...C_{i_{m}} =
\begin{cases} \frac{m(n+1)(n+2)...(n+m/2-1)}{2(n+m/2+2)(n+m/2+3)...(n+m)}C_{n+m/2} & m \text{ chẵn} \\
\frac{m(n+1)(n+2)...(n+(m-1)/2)}{(n+(m+3)/2)(n+(m+3)/2+1)...(n+m)}C_{n+(m-1)/2} &m \text{ lẻ} \end{cases} </math>

(phát biểu thành lời vế trái: tổng của tất cả tích của các số catalan có tổng chỉ số bằng n)

và

<math>C_0=1 \text{ và } C_{n+1} = \frac{2(2n+1)}{n+2} C_{n} </math>

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

<math>C_{n} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}</math>

Ý nghĩa của biểu thức trên là thương khi chia số Catalan thứ ''n'' cho biểu thức bên phải sẽ tiến tới 1 khi <math>n \rightarrow \infty</math>. Một vài tài liệu chỉ viết rằng <math>C_n \sim \frac{4^n}{n^{3/2}}</math>.<ref>{{chú thích sách|title = Introduction to Algorithms|url = https://archive.org/details/automaticconceal03corm|last = Cormen|first = Thomas H.|last2 = Leiserson|first2 = Charles E.|last3 = Rivest|first3 = Ronald L.|publisher = The MIT Press|isbn = 0262031418|year = 1990|location = Cambridge, Massachusetts|page = [https://archive.org/details/automaticconceal03corm/page/n304 304]|chapter = Dynamic Programming}}</ref> Điều này có thể chứng minh bằng cách dùng [[Xấp xỉ Stirling|phép tính xấp xỉ của Stirling]] với ''n''!, hoặc thông qua các hàm sinh.

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

Chỉ có 2 số Catalan là [[số nguyên tố]]: ''C''''2'' = 2 và ''C''''3'' = 5.[''citation needed[[Wikipedia:Citation needed|<nowiki/>]]'']

Số Catalan có cách biểu diễn khác dưới dạng tích phân:

<math>C_n = \int_{0}^{4} x^n \rho(x)dx,</math>

trong đó <math>\rho(x)=\tfrac 1{2\pi}\sqrt{\tfrac{4-x}{x}}.</math> Nghĩa là số Catalan là lời giải của [[bài toán mômen Hausdorff]] trên đoạn [0, 4] thay vì [0, 1].

== Ứng dụng trong toán tổ hợp ==
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 ''C''3 = 5 và ''C''4 = 14.
[[Tập tin:Dyck lattice D4.svg|thumb|Mạng lưới 14 từ Dyck với độ dài 8 - ''được biểu đạt bằng các nét lên, xuống.'']]
* ''C''''n'' là số '''từ Dyck'''<ref>{{Chú thích web |url=http://www.findstat.org/DyckPaths |ngày truy cập=2015-07-14 |tựa đề=Equivalent definitions of Dyck paths |archive-date=2020-12-03 |archive-url=https://web.archive.org/web/20201203194735/https://www.findstat.org/DyckPaths |url-status=dead }}</ref> với độ dài 2''n''. 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 nào của chuỗi có nhiều ký tự Y hơn so với X. Ví dụ các từ Dyck độ dài 6:
<div class="center" id="cx128" data-source="128" data-cx-state="source" data-cx-weight="52" contenteditable="true" data-cx-draft="true"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>
* 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ố biểu thức chứa n cặp dấu ngoặc đúng:
<div class="center" id="cx134" data-source="134" data-cx-state="source" data-cx-weight="52" contenteditable="true" data-cx-draft="true"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>
* ''C''''n'' cũng là số cách khác nhau để đặt dấu ngoặc giữa n+1 phần tử (hay là số cách để sắp xếp n phép khai triển của một toán tử 2 ngôi). Ví dụ, với n = 3, chúng ta có 5 cách khác nhau để chia 4 phần tử:
<div class="center" id="cx143" data-source="143" data-cx-state="source" data-cx-weight="60" contenteditable="true" data-cx-draft="true"><big>((ab)c)d     (a(bc))d     (ab)(cd)     a((bc)d)     a(b(cd))</big></div>
[[Tập tin:Tamari lattice, trees.svg|thumb|Cây có 5 lá.]]

* Phép khai triển liên tiếp của một toán tử 2 ngôi có thể biểu diễn dưới dạng một 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). Dẫn đến Cn là số cây nhị phân đầy đủ có n+1 lá:[[Tập tin:Catalan number binary tree example.png|giữa|nhỏ|496x496px]]
* ''C''''n'' là số cây có thứ tự, không giống nhau (về mặt 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)<ref>Stanley p.221 example (e)</ref>
* ''C''''n'' là số đường đi đơn điệu dọc theo các cạnh 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 bên trái, kết thúc ở góc trên bên phải, chỉ đi theo hướng qua phải hoặc đi lên. Đếm số đường đi cũng tương tự đếm từ Dyck: 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:
 
[[Tập tin:Catalan number 4x4 grid example.svg|giữa|513x513px]]

Có thể biểu diễn lại bằng cách liệt kê các phần tử Catalan theo độ cao cột:<ref>{{chú thích tạp chí|last = ˇCrepinˇsek|first = Matej|author2 = Luka Mernik|title = AN EFFICIENT REPRESENTATION FOR SOLVING CATALAN NUMBER RELATED PROBLEMS|journal = International Journal of Pure and Applied Mathematics|year = 2009|volume = 56|issue = 4|url = http://www.ijpam.eu/contents/2009-56-4/11/11.pdf}}</ref><div id="cx179" style="text-align: center;" class="" data-source="179" data-cx-state="source" data-cx-weight="36" data-cx-draft="true" contenteditable="true">[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]
</div>[[Tập tin:Tamari lattice, hexagons.svg|thumb|Các tam giác phụ thuộc vào các nút của cây nhị phân]]
* ''C''''n'' 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:
* ''C''''n'' 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 ''w'' = ''unv'' trong đó ''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.
* ''C''''n'' 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. Với ''n'' = 4, chúng là 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321.
* ''C''''n'' là số cách phân chia không cắt nhau của tập {1, ..., ''n''}. ''Tất nhiên,'' ''C''''n'' không bao giờ lớn hơn [[số Bell]] thứ n. ''C''''n'' cũng là số cách phân tập không cắt nhau của {1, ..., 2''n''} trong trường hợp mỗi khối kích cỡ 2.
* ''C''''n'' 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:
* ''C''''n'' 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..
* ''C''''n ''là 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.
<div align="center">
{| class="wikitable
|+ Mountain Ranges
|-
| <math>n = 0:</math>
| style="font-family:monospace;" |*
| 1 way
|-
| <math>n = 1:</math>
| style="font-family:monospace;" |/\
| 1 way
|-
| <math>n = 2:</math>
| style="font-family:monospace;" |{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\ /\/\,{{0}}/{{0}}{{0}}\
|2 ways
|-
| <math>n = 3:</math>
| style="font-family:monospace;" |{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\ {{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\{{0}}{{0}}{{0}}{{0}}/\{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\/\{{0}}{{0}}{{0}}{{0}}/{{0}}{{0}}\ /\/\/\,{{0}}/\/{{0}}{{0}}\,{{0}}/{{0}}{{0}}\/\,{{0}}/{{0}}{{0}}{{0}}{{0}}\,{{0}}/{{0}}{{0}}{{0}}{{0}}\
|5 ways
|}
</div>
* ''C''''n'' 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
* ''C''''n'' is the number of ways that the vertices of a convex 2''n''-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). ''(tạm dịch: C_n là số cách để ghép cặp các đỉnh của một đa giác lồi có 2n đỉnh sao cho những đoạn thẳng nối các cặp đỉnh không giao nhau. Đây chính xác là điều kiện đủ để chỉ ra những cạnh nối có thể hình thành một mặt phẳng genus không kín (khối lưỡng cầu tôpô))''
* ''C''''n'' is the number of semiorders on ''n'' unlabeled items.<ref>{{citation
|last1 = Kim|first1 = K. H.|last2 = Roush|first2 = F. W.|mr = 538212|issue = 2|journal = Journal of Combinatorics, Information &System Sciences|pages = 58–61|title = Enumeration of isomorphism classes of semiorders|volume = 3|year = 1978}}.</ref>

== Chứng minh công thức ==

== Xem thêm ==

== Ghi chú ==
{{tham khảo}}

[[Thể loại:Chuỗi số nguyên]]
[[Thể loại:Giai thừa]]

Số Catalan - Lịch sử thay đổi

imported>Bluetpp: Đã lùi lại sửa đổi của ~2026-38261-70 (thảo luận) quay về phiên bản cuối của TheSecondFunnyYellowBot