Permutation and Combinatorics Problem

Question

A function $G$ is defined on a set $S$ with size $k$ : $G(a_1,a_2,a_3,\ldots,a_k)$. $G(a_1,a_2,a_3,\ldots,a_k) = 1$ if and only if a convex polygon can be created by taking these $k$ elements as the side lengths. Otherwise $G(a_1,a_2,a_3,\ldots,a_k) = 0$. You are given the identity permutation over $n$ elements - $I_n(I_n=\{1,2,3,\ldots,n\})$. Find the sum of function $G$ over all possible distinct $k$-sized subsets of $I_n$.

All I could think of involved checking all subsets of size $k$ (which is not efficient for large size of the set obviously).Checking the $G$ value for a subset is easy , you just check if the largest element is greater than the sum of all other or not. Calculating the number of such subsets doesn't seem trivial :/ I wonder if there is some pattern/theorem/recurrence involved.

Answer 1

The definitions are important here.

Let's start by assuming $k\ge 1$ here so ignoring a whether a polygon with no sides exists. Let's also assume that a convex polygon has positive area, so the subset $\{1,2,3\}$ produces a degenerate triangle and is not counted, while the subset $\{1,2,3,4\}$ can produce essentially several convex quadrilaterals but we will count it once. As leonboy commented, it is necessary and sufficient that the largest element a subset is strictly smaller than the sum of the others. That will not happen if $k <3$ and not when $n=k=3$.

Here is a table for small $n,k$:

 n \ k [,1] [,2] [,3] [,4] [,5] [,6]  [,7]  [,8]  [,9] [,10] [,11] [,12] [,13] [,14] [,15]
 [1,]    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0
 [2,]    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0
 [3,]    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0
 [4,]    0    0    1    1    0    0     0     0     0     0     0     0     0     0     0
 [5,]    0    0    3    5    1    0     0     0     0     0     0     0     0     0     0
 [6,]    0    0    7   14    6    1     0     0     0     0     0     0     0     0     0
 [7,]    0    0   13   32   21    7     1     0     0     0     0     0     0     0     0
 [8,]    0    0   22   63   56   28     8     1     0     0     0     0     0     0     0
 [9,]    0    0   34  112  126   84    36     9     1     0     0     0     0     0     0
[10,]    0    0   50  185  251  210   120    45    10     1     0     0     0     0     0
[11,]    0    0   70  289  459  462   330   165    55    11     1     0     0     0     0
[12,]    0    0   95  431  785  924   792   495   220    66    12     1     0     0     0
[13,]    0    0  125  620 1273 1716  1716  1287   715   286    78    13     1     0     0
[14,]    0    0  161  865 1976 3003  3432  3003  2002  1001   364    91    14     1     0
[15,]    0    0  203 1176 2959 5004  6435  6435  5005  3003  1365   455   105    15     1

The third column is essentially OEIS A002623 offset and its first difference is, as Alexander Burstein commented, OEIS A002620.

My reading of the question is that you are interested in the numbers for $n$, i.e. the row sums. This starts $$0, 0, 0, 2, 9, 28, 74, 178, 402, 872, 1842, 3821, 7830, 15913, 32161, 64761, 130091, 260911$$ which does not seem to appear in OEIS but seems to be the difference between two sequences which do: A095941 (which would also count cases where the polygons are of zero area) and OEIS A317910 (which seems to only count cases where the polygons are of zero area).

The various OEIS links suggest a relationship between this sequence and the number of ways of partitioning $n$ into distinct parts OEIS A000009; its generating function is $\prod\limits_{m\ge1} (1+x^m)$ while the generating function of this sequence seems to be $$\frac{1-x-x^2}{(1-x)^2(1-2x)} - \frac{1}{(1-x)^2} \prod\limits_{m\ge1} (1+x^m)$$