3
$\begingroup$

We have $n$ points on the plane that non three are on a line.If $c_k$ denotes number of $k$ points that do not contain any point in a $k$-gon constructed by these points then prove that $\sum\limits_{k=3}^n (-1)^k c_k$ doesn't depend on how points are choosen in the plane and it only depends on the amount of $n$.

The answer wrote first prove $\sum\limits_{k=3}^n (-1)^k c_k=\sum\limits_{k=3}^n (-1)^k \binom{n}{k}$ but I can't do that.

$\endgroup$
6
  • $\begingroup$ In what context are you encountering this? Do you know about Mobius functions of posets or Euler characteristics, etc? $\endgroup$
    – Pedro
    Commented Nov 1, 2017 at 15:23
  • $\begingroup$ @PedroTamaroff I know non of them. $\endgroup$ Commented Nov 1, 2017 at 16:05
  • $\begingroup$ @zhoraster I've just tried to show $k$-gons that contain another point in them will be cancelled in the $R.H.S$ But I couldn't do that. $\endgroup$ Commented Nov 6, 2017 at 13:47
  • 1
    $\begingroup$ Can you explain what is the meaning of $c_k$? The defintion is a little bit confusing. I dont really know what $c_k$ is. $\endgroup$
    – Student
    Commented Nov 8, 2017 at 14:46
  • 3
    $\begingroup$ @Cuteboy Could it be just convex polygons that are being considered! In that case, $c_4$ would be zero. $\endgroup$ Commented Nov 8, 2017 at 18:13

2 Answers 2

5
+500
$\begingroup$

I will interpret the problem as Peter Košinár suggested in the comments: that $c_k$ is the number of convex $k$-gons with vertices in the given points that don't contain any other given points inside.

Let's denote the given set of $n$ points by $M$. For any subset $X\subseteq M$ with at least three elements, its convex envelope (which I will denote $CE(X)$) is a convex polygon whose vertices are (some) elements of $M$. Let $C$ be the set of all convex polygons whose vertices are elements of $M$ (including those polygons which contains other points of $M$ inside). Then in the sum $$ \sum\limits_{k=3}^n (-1)^k\binom{n}{k} = \sum\limits_{k=3}^n \sum\limits_{X: X\subseteq M, |X|=k} (-1)^k $$ we can group the subsets of $M$ by their convex envelopes and rewrite the sum as $$ \sum\limits_{P\in C}\sum\limits_{k=3}^n\sum\limits_{X:X\subseteq M, |X|=k, CE(X) = P}(-1)^{k}. $$

Let $P\in C$ be an $l$-gon, and let it have $m$ elements of $M$ lying strictly inside. Then for a given $k$, exactly $\binom{m}{k-l}$ of $k$-element subsets $X$ of $M$ are such that $CE(X) = P$, since these are the subsets which contain all $l$ vertices of $P$ and $k-l$ of the points lying inside. So the inner double sum is $\sum\limits_{k=3}^n\sum\limits_{X:X\subseteq M, |X|=k, CE(X) = P}(-1)^{k} = \sum\limits_{k=3}^n (-1)^k \binom{m}{k-l} = (-1)^l \sum\limits_{i=0}^m (-1)^i\binom{m}{i}$, which is equal to $(-1)^l$ if $m=0$ and $0$ otherwise. So the total sum is equal to $\sum\limits_{l=3}^n (-1)^lc_l$.

$\endgroup$
1
$\begingroup$

I think the polygons you are considering have to be convex, otherwise the formula you stated does not hold in general.

For example, for $n=5$, consider the points $(0,0)$, $(6,0)$, $(2,1)$, $(4,1)$, $(3,2)$ in the plane. Then these points span $7$ triangles not enclosing any points, $3$ quadrilaterals not enclosing any points, and one pentagon, that is not convex. Thus $c_3=7$, $c_4=3$, $c_5=1$, so the formula for these $5$ points is $-7+3-1=-5$.

But if we consider instead a regular pentagon, then $c_3=10$, $c_4=5$, $c_5=1$, so the formula will be $-10+5-1=-6$. So for these two arrangements, the formulae do not agree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .