number of subset forming polygon

Question

Given a set $S = \{ 1 , 2 , 3,\ldots, n\}$. How can I find number of subsets of size $K$ ($K < n$) whose elements taken as length of edges can form a convex polygon ($K$-sided).

Answer 1

An approach: Let $a_1,...,a_k$ the subset with $a_i<a_j$ if $i<j$. If you can construct a polygon then $a_k<\sum_{i=1}^{k-1}a_i$.

But this sum is $\leq (a_k-1)+...+(a_k-(k-1))=(k-1)a_k-k(k-1)/2$.

Answer 2

Some recursions (too long for comment):

Let $f(n,k,s)$ denote the number of $k$-sets $\{a_1,\ldots, a_{k}\}\subseteq \{1,\ldots,n\}$ with $a_1+\ldots +a_{k}\ge s$. Then we have the recursion $$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} $$ Let $F(n,k)$ denote the number of $k$-sets $\{a_1,\ldots, a_{k}\}\subseteq \{1,\ldots,n\}$ that can form a convex polygon. The polygon condition is equivalent to the largest element being strictly less than the sum of the remaining elements. Hence we find $$ F(n,k)=\sum_{m=1}^n f(m-1,k-1,m+1)$$