Question

اگر n نقطه روی یک دایره قرار داشته باشند و همه آنها را به یکدیگر وصل کنیم حداکثر چند ناحیه داخل دایره ایجاد می‌شود؟

Answer 1

تعداد این ناحیه ها را $S(n)$ بگیرید.واضح است که :

$S(1)=1,S(2)=2,S(3)=4$

حالا فرض کنید که $n \geq 4$ وتوجه کنید حالت حداثر زمانی پیش می آید که هیچ سه پاره خط تشکیل شده به وسیلۀ این نقاط در داخل دایره همرس نباشند.حالا اگر این شکل را به عنوان یک گراف مسطح نگاه کنیم هر رأس آن که در داخل دایره است دارای درجۀ چهار و به وسیلۀ چهار نقطۀ متمایز روی دایره مشخص می شود.(هر چهار نقطه را می توان طوری به هم وصل کرد که در داخل دایره شبیه یک علامت ضرب همرس باشند).پس در این گراف $ \binom{n}{4} $ رأس از درجۀ $4$ داریم که در داخل دایره اند.و رأسهای روی دایره دارای درجۀ $n+1$ اند (دو کمان داره را هم بشمارید) حالا اگر فرمول اویلر را بکار ببریم داریم:

$v-e+f=2 \Rightarrow (n+ \binom{n}{4}) -\frac{ 4\binom{n}{k} +n(n+1)}{2} +v=2$

$v=-n- \binom{n}{4} +2 \binom{n}{4} + \frac{n(n+1)}{2} +2= \binom{n}{4} +\frac{n(n-1)}{2}+2= \binom{n}{4} + \binom{n}{2} +2$

$S(n)=v-1(?) \Rightarrow S(n)=\binom{n}{4} + \binom{n}{2} +1= \binom{n}{4} + \binom{n}{2} + \binom{n}{0} $

$ \Box $