The first part of this month's solution is due to Alexey Vorobyov of Irvine CA. Lisa Schechner of Weber Middle School, Port Washington NY found the closed form C(n,4) + C(n-1,2), where C(n,k) is the binomial coefficient n!/(k!(n-k)!). Can anyone find a combinatorial proof of this result (namely one that directly uses the fact that C(n,k) is the number of ways of choosing k things from a collection of n)?
Here is Alexey Vorobyov's argument giving a non-closed formula:
I didn't find a closed form solution but I have an algorithm to find the
value for any polygon.
1. Let's enumerate vertices from 1 to N.
2. Let's draw N-3 diagonals from vertex 1. They'll divide the polygon on
N-2 regions.
3. Now let's draw diagonals from vertex 2. Every diagonal to vertex K will
cross diagonals from 1 to vertices with indices below K, i.e. to vertices
with indices from 3 to K-1, or K-3 diagonals. Every segment between
crossings will divide the existing area by two. Total number of segments
is K-2. Thus for all diagonals from vertex 2 to find total number of new
regions we need to sum values (K-3)+1 for K in range from 4 to N, i.e. 2,
3, ..., (N-3)+1
4. Now let's draw diagonals from vertex 2. Every diagonal to vertex K will
cross diagonals from 1 and 2 to vertices with indices below K, i.e. to
vertices with indices from 4 to K-1, or 2*(K-4) diagonals. Because no 3
diagonals cross in the same point, total number of segments this (3,K)
diagonal will be divided is 2*(K-4)+1 and once again every segment means
one new region because it splits one old region on two. To find total
number of new regions for diagonals from vertix 3 we need to sum 2*(K-4)+1
for K in range from 5 to N, i.e. 3, 5, 7, 9, ..., 2*(N-4)+1.
5. We can easily generalize it on any vertex M. Every diagonal to vertex K
will cross diagonals from 1, 2, ..., M-1 to vertices with indices below K,
i.e. to vertices with indices from M+1 to K-1, or (M-1)*(K-M-1) diagonals.
Because no 3 diagonals cross in the same point, total number of segments
this (M,K) diagonal will be divided is (M-1)*(K-M-1)+1 and once again
every segment means one new region because it splits one old region on
two. To find total number of new regions for diagonals from vertix M we
need to sum (M-1)*(K-M-1)+1 for K in range from M+2 to N, i.e. M,
2*(M-1)+1, 3*(M-1)+1, ..., (M-1)*(N-M-1)+1.
Thus for N=6 we have number of new regions for every vertex:
1: 1+1+1+1= 4
2: 2+3+4 = 9
3: 3+5 = 8
4: 4 = 4
Total number is 25.
Similarly we find for N=12:
1: 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1=10
2: 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+10 =6*9=54
3: 3+ 5+ 7+ 9+11+13+15+17 =10*8=80
4: 4+ 7+10+13+16+19+22 =13*7=91
5: 5+ 9+13+17+21+25 =15*6=90
6: 6+11+16+21+26 =16*5=80
7: 7+13+19+25 =16*4=64
8: 8+15+22 =15*3=45
9: 9+17 =13*2=26
10: 10 =10
Total number of regions is 550.
Some ideas on a closed form solution.
We've got very interesting triangle here.
1 1 1 1 1 1 1 1 1 1
2 3 4 5 6 7 8 9 10
3 5 7 9 11 13 15 17
4 7 10 13 16 19 22
5 9 13 17 21 25
6 11 16 21 26
7 13 19 25
8 15 22
9 17
10
Sum of all elements in columns from 1 to N gives us the number of regions
in N-gon. It can be easily seen that this triangle is symmetric and
values in N-th column are K*(N-K)+1. May be this will help to find closed
form solution. Now it looks like
sum(K=0:N){sum(M=0:K-1)[M*(K-M)+1]}=N(N+1)/2+sum(K=0:N){sum(M=0:K-1)[M*(K-M)]}