número de subconjuntos que forman el polígono

Question

Dado un conjunto $S = \{ 1 , 2 , 3,\ldots, n\}$ . ¿Cómo puedo encontrar el número de subconjuntos de tamaño $K$ ( $K < n$ ) cuyos elementos tomados como longitudes de aristas pueden formar un polígono convexo ( $K$ -sided).

Answer 1

Algunas recursiones (demasiado largas para comentarlas):

Dejemos que $f(n,k,s)$ denotan el número de $k$ -sets $\{a_1,\ldots, a_{k}\}\subseteq \{1,\ldots,n\}$ con $a_1+\ldots +a_{k}\ge s$ . Entonces tenemos la recursión $$f(n,k,s)=\begin{cases} f(n-1,k,s)+f(n-1,k-1,s-n)&\text{if $n\ge k\ge0$ and $s>0$}\\n\choose k&\text{if $n\ge k\ge 0$ and $s\le 0$}\\0&\text{otherwise}\end{cases} $$ Dejemos que $F(n,k)$ denotan el número de $k$ -sets $\{a_1,\ldots, a_{k}\}\subseteq \{1,\ldots,n\}$ que pueden formar un polígono convexo. La condición de polígono equivale a que el elemento mayor sea estrictamente menor que la suma de los elementos restantes. Por lo tanto, encontramos $$ F(n,k)=\sum_{m=1}^n f(m-1,k-1,m+1)$$

Answer 2

Una aproximación: Dejemos que $a_1,...,a_k$ el subconjunto con $a_i<a_j$ si $i<j$ . Si puedes construir un polígono, entonces $a_k<\sum_{i=1}^{k-1}a_i$ .

Pero esta suma es $\leq (a_k-1)+...+(a_k-(k-1))=(k-1)a_k-k(k-1)/2$ .