Chủ đề này có 3 trả lời

[jumjihoo]

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$

[hxthanh]

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)!}$

[jumjihoo]

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?

[hxthanh]

LV: Một số chuyên đề về tổ hợp

 ToHop_NTNA.pdf   567.93K   141 Số lần tải