Cho số nguyên dương n. Có bao nhiêu bộ thứ tự ($x_{1}$;$x_{2}$;...;$x_{n}$) thỏa mãn đồng thời các điều kiện sau đầy:
a) $x_{i}\epsilon$ {-1;1} với mọi i=1,2,3,...n
b) $x_{1}+x_{2}+...+x_{k}\geq 0$ với mọi k=1,2,3...n
c) $x_{1}+x_{2}+...+x_{n}=0$
Cho số nguyên dương n. Có bao nhiêu bộ thứ tự ($x_{1}$;$x_{2}$;...;$x_{n}$) thỏa mãn đồng thời các điều kiện sau đầy:
a) $x_{i}\epsilon$ {-1;1} với mọi i=1,2,3,...n
b) $x_{1}+x_{2}+...+x_{k}\geq 0$ với mọi k=1,2,3...n
c) $x_{1}+x_{2}+...+x_{n}=0$
Bài này thoạt nhìn có vẻ "lạ lẫm" nhưng sau khi phân tích thì thấy rất đỗi quen thuộc
Rõ ràng theo điều kiện c) thì ta chỉ cần xét với $n$ chẵn $n=2m$
Khi đó thì bộ $(x_1, x_2, ..., x_n)$ có đúng $m$ số $1$ và $m$ số $-1$
Cho tương ứng số $1$ bởi vecto $\vec{u}=(1,0)$ và số $-1$ bởi vecto $\vec{v}=(0,1)$
Như vậy mỗi bộ $(x_1, x_2, ..., x_n)$ tương ứng với một con đường đi từ điểm $O(0,0)$ đến điểm $M(m,m)$ bởi các vecto đơn vị sao cho đường đi không vượt qua đường thẳng $y=x$
Số cách đi như vậy chính là số Catalan $C_m=\dfrac{(2m)!}{m!(m+1)!}$
Bài này thoạt nhìn có vẻ "lạ lẫm" nhưng sau khi phân tích thì thấy rất đỗi quen thuộc
Rõ ràng theo điều kiện c) thì ta chỉ cần xét với $n$ chẵn $n=2m$
Khi đó thì bộ $(x_1, x_2, ..., x_n)$ có đúng $m$ số $1$ và $m$ số $-1$
Cho tương ứng số $1$ bởi vecto $\vec{u}=(1,0)$ và số $-1$ bởi vecto $\vec{v}=(0,1)$
Như vậy mỗi bộ $(x_1, x_2, ..., x_n)$ tương ứng với một con đường đi từ điểm $O(0,0)$ đến điểm $M(m,m)$ bởi các vecto đơn vị sao cho đường đi không vượt qua đường thẳng $y=x$
Số cách đi như vậy chính là số Catalan $C_m=\dfrac{(2m)!}{m!(m+1)!}$
Bạn có thể giới thiệu mình chỗ để tìm hiểu về số Catalan được không?
ToHop_NTNA.pdf 567.93K 141 Số lần tải
0 thành viên, 1 khách, 0 thành viên ẩn danh