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

[hxthanh]

Cho đa giác lồi $n$ đỉnh ($n-$giác). Gọi số $k-$giác tạo ra bởi tập hợp $k$ đỉnh của $n-$giác sao cho cạnh của $k-$giác không phải cạnh của $n-$giác là $S(n,k)$
Tính $S(n,k)$
——
Ghi chú:
$\bullet \;\;k=0$ thì $S(n,0)=1$ (tập rỗng)
$\bullet \;\;k=1$ thì $S(n,1)=n$
$\bullet \;\;k=2$ thì $S(n,2)$ là số “đường chéo”

[hxthanh]

Đây là một bài toán tiêu biểu cho trường hợp phải lập “công thức truy hồi 2 biến”
Xét một đỉnh $A$ của $n-$giác
- Trường hợp $k-$giác có chứa đỉnh $A$. Khi đó hai đỉnh kề với $A$ sẽ bị loại bỏ. Ta còn phải chọn $k-1$ đỉnh trong $n-2-$giác. Số này là $S(n-2,k-1)$
- Trường hợp $k-$giác không chứa đỉnh $A$. Khi đó đỉnh $A$ bị loại bỏ. Ta phải chọn $k-$giác thoả từ $n-1-$giác. Số này là $S(n-1,k)$
Như vậy ta có:
\begin{equation}\label{s1}
S(n,k)=S(n-1,k)+S(n-2,k-1)
\end{equation}
… Các bạn thử nghĩ xem chúng ta phải làm gì với \eqref{s1}?…
Mình sẽ trở lại sau!

[hxthanh]

Thực chất \eqref{s1} hoàn toàn tương tự như biểu thức (4) post #4
Và việc chứng minh tương tự kết quả của biểu thức (10) post #5. Ta có:
$$S(n,k)=\dfrac{n}{n-k} {n-k\choose k}$$