With regard to [my original question](https://mathoverflow.net/questions/7617/probability-question-closed):



> 
> A subset of k vertices is chosen from the vertices of a regular N-gon. What is the probability that two vertices are adjacent?
> 
> 
> 


I suppose that the responses that were elicited to my question were to be expected. You see, I have been in your position, and thought what you did, on many occasions. But mostly not in the area of mathematics.


By way of providing background, I am not a student at all. In fact, I am a biochemist and part-time university instructor. I have often provided answers to students who post chemistry/biochemistry questions (samples will be provided upon request). And, like you, I hope that I have not (or had not!) become a vehicle for students to avoid thinking through THEIR chemistry homework assignments.


The above question, believe it or not, comes from the local, Boston-based television program "extrahelp", hosted by a somewhat sarcastic character who went by the name "Mr. Math". It was intended for the K-12 demographic, but, according to the story behind the video, an M.I.T. student was listening, and asked the question, ostensibly to give this man his comeuppance. The video is no longer available online, but I can send you a copy, if you don't mind that it is 25.1 MB, and that I don't have access to any FTP server at the university where I teach. It is hilarious.


When I saw this video (and after I stopped laughing), I was interested by the question itself. And since at least one of you asked for any work that I have done on my own, here is as far as I got before I made my original post:


1) N must, of course, be a positive integer >= 3. k must be a positive integer <= N.
2) When k = 1, the solution is trivial (p = 0). In fact, the non-trivial values of k are: 2 <= k <= (N \ 2), where "\" is integer division. For other values of k, p = 1.
3) For non-trivial values of k, the denominator is C(N,k).
4) For k = 2, the numerator is N.
5) For k = 3, the numerator is N(N-k).
6) For N even, and k = N / 2, the numerator is N – 2. For N odd, and k = N \ 2, the numerator is C(N,k) – N.
7) For k = (N \ 2) -1, the numerator may be C(N,k) – N(N-k).


Where I am having trouble is, obviously, getting from here to a general solution. It has been suggested to me that I take the approach of finding the general expression for the probability of NOT selecting adjacent vertices, but the general answer of p = 1 - [C(N-k,k) / C(N,k)] is not confirmed by the examples that I am sure about (that is, where N is so small that the answers can be confirmed by enumeration)


I am sure that you would agree that, by now, enough time has passed that, if this really were a homework question, that the due date for such homework would have passed. Further, I hope that I have convinced you beyond a reasonable suspicion that a) this is definitely not a homework question, and b) that I have worked on the problem myself to such a degree that I haven't just passed this off on the respondents without making some effort.



Probability vertices are adjacent in a polygon
It's not so hard to calculate the probability that no two points are adjacent:


We may as well assume that the first vertex is chosen for us. So let's ignore it and unroll the rest of the polygon into a line. Now imagine that I write down a sequence of $0$s and $1$s along this line to indicate whether the corresponding vertices are chosen or not. The condition on this sequence is that: the first and last numbers in this sequence must not be $1$s, and any $1$ must be followed by a $0$. So, let's replace any subsequence of the form $01$ with an $x$ and ignore the last $0$ in the sequence, so for instance we'd have the transformation $01001010 \rightarrow x0xx$. Now there is no condition on the sequence of $0$s and $x$s, other than the length and number of $x$s.


The length of the new sequence will be $(n-1)-(k-1)-1 = n-k-1$, and will contain $k-1$ $x$s, so the number of such sequences is just $\binom{n-k-1}{k-1}$, while the number of all sequences of $0$s and $1$s (including ones violating our condition) is $\binom{n-1}{k-1}$. So the probability you want is just $1-\frac{\binom{n-k-1}{k-1}}{\binom{n-1}{k-1}}=1-\frac{(n-k-1)!(n-k)!}{(n-1)!(n-2k)!}$.


Just to be sure, let's check that with $n = 6, k = 3$. Our formula gives us a probability of $1-\frac{2!3!}{5!0!} = 1-\frac{12}{120} = \frac{9}{10}$. We can check by hand that there are two ways for the vertices to not all be adjacent - the two triangles in the hexagon, and there are a total of $\binom{6}{3} = 20$ ways to choose three vertices, and this gives us a probability of $1-\frac{2}{20} = \frac{9}{10}$. Hooray! No off by one errors!


