Bài toán về số cách sắp xếp 2n viên bi với 2 màu

[nguyenhtctb]

Đem n viên bi trắng và n viên bi đen sắp xếp thành 1 hàng, sau đó tìm cách cắt hàng đó thành 2 phần sao cho trong mỗi phần có số bi trắng và bi đen bằng nhau. Gọi A là số trường hợp không thể cắt hàng theo yêu cầu trên, còn B là so trường hợp chỉ có duy nhất 1 cách cắt theo yêu cầu. Chứng minh rằng 2A = B
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[beyondinfinity]

Nguyên văn bởi nguyenhtctb

Đem n viên bi trắng và n viên bi đen sắp xếp thành 1 hàng, sau đó tìm cách cắt hàng đó thành 2 phần sao cho trong mỗi phần có số bi trắng và bi đen bằng nhau. Gọi A là số trường hợp không thể cắt hàng theo yêu cầu trên, còn B là so trường hợp chỉ có duy nhất 1 cách cắt theo yêu cầu. Chứng minh rằng 2A = B

Không khó lắm để chứng minh điều sau:
$B_n=\sum_{i=1}^{n-1}A_iA_{n-i} $
và $A_n=2C_{n-1} $
($C_n $ là số Catalan thứ $n $)
Từ đó ta chỉ cần cm:
$2A_n=\sum_{i=1}^{n-1}A_iA_{n-i} $
Ai học về số Catalan đều phải biết công thức truy hồi của nó. Xong!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]