With regard to my original questionmy 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:
- N must, of course, be a positive integer >= 3. k must be a positive integer <= N.
- 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.
- For non-trivial values of k, the denominator is C(N,k).
- For k = 2, the numerator is N.
- For k = 3, the numerator is N(N-k).
- 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.
- 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.