Mathematics desk
< October 10	<< Sep \| October \| Nov >>	October 12 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 11[edit]

polygon disjoint sets[edit]

Let a polygon with m vertices labeled as 1,2,3,..,m. How many subsets of {1,2,..m} having two or more elements exists with the property that they should not include any two consecutive vertices of polygon. — Preceding unsigned comment added by 182.187.95.175 (talk) 21:29, 11 October 2014 (UTC)[reply]

Let's count this for subsets of size k, then sum over k. We'll break these into two categories: those containing 1, and those omitting it.

Let's start with those containing one. Then there are k "gaps"--one after every element. Each of these gaps has at least 1 element in it, which leaves (m-2k) elements unaccounted for. These remaining elements need to be distributed amongst the gaps. Stars and bars is good for counting the number of ways to do this, giving us

{\frac {(m-k-1)!}{(m-2k)!(k-1)!}}

different sets with k elements including 1.

Next, we'll consider those sets omitting 1. Here there are k+1 gaps--one after every element, and one before 1. Each has at least 1 element, except possibly the last one. So still (m-2k) elements unaccounted for, but this time k+1 many gaps to distribute them in. So

{\frac {(m-k)!}{(m-2k)!k!}}

sets with k elements and excluding 1.

Note that k can be at most half of m, so the total number of sets is

\sum _{k=2}^{m/2}{\frac {(m-k-1)!}{(m-2k)!(k-1)!}}+{\frac {(m-k)!}{(m-2k)!k!}}

. The interior can be simplified a bit, getting you

\sum _{k=2}^{m/2}{\frac {m(m-k-1)!}{(m-2k)!k!}}

.--80.109.80.31 (talk) 23:19, 11 October 2014 (UTC)[reply]

This is A023548. I don't know why it is, but the first 20 terms all match. -- BenRG (talk) 00:42, 12 October 2014 (UTC)[reply]

As perhaps a clue, I understand why the terms representing the prime m have to be divisible by m in the polygon disjoint sets, if we understood why it was true in A023548... (note A023548 needs to be shifted by 3, since a square is the first one that can be disjoint...Naraht (talk) 01:05, 12 October 2014 (UTC)[reply]

It's well known that the Lucas numbers represent the number of cyclic 0-1 sequences that have no consecutive 1's; it's not mentioned in our article but the oeis entry OEIS: A000204 mentions it. It's a small leap to get from that the numbers of subsets of the vertices of a polygon with no consecutive elements are Lucas numbers. You can also state this as the number of independent sets in a cyclic graph. The number of sets with 0 or 1 element is easy to determine so that gives a formula for the number in question. Lucas numbers can be given in terms of Fibonacci numbers so it's probably not hard to turn this formula into a proof that the sequence in question is A023548. --RDBury (talk) 13:21, 12 October 2014 (UTC)[reply]