Probability vertices are adjacent in a polygon

Question

With regard to my original question:

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.

Answer 1

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!

Answer 2

I apologize for prejudging the question. A shorter version of this background explanation at the beginning would have been helpful. The truth is that many questions of this sort do show up as homework in undergraduate probability and combinatorics courses.

An equivalent problem is to count non-adjacent subsets of the vertices of size $k$. It helps to mark one of the chosen vertices, which increases the answer by a factor of $k$. Any one of the $n$ vertices can be marked, and after that, the vertex to the right of the marked one cannot be chosen. If you marry every chosen vertex to the unused one to its right, the combinatorial pattern (again excluding the marked vertex and the one to its right) is equivalent to a word of length $(n-2)-(k-1)$ in two symbols, "a" for unused, and "b" for "used married to unused"; and there are $k-1$ of the "b" letters. So the final answer for this counting problem is: $$N(n,k) = \frac{n}{k}\binom{n-k-1}{k-1}.$$ Of course the counting answer can also be converted to a probability.

(The problem may still belong better in AoPS rather than here, but I don't mind too much.)