Here is a question from Meyer 2nd Edition, Introductory Probabilty and Statistical Applications, p32 number 2.16. I'm trying to teach myself and although I see this same problem (and answers) in other people's textbooks, I believe that the given answer is incorrect.
A box contains tags marked 1, 2, … n. Two tags are chosen at random. Find the probability that the numbers on the tags will be consecutive integers if a) the tags are chosen without replacement, and b) the tags are chosen with replacement.
Let n = 6. The possible consecutive integer pairs chosen are 12, 23, 34, 45, 56. These are the same combinations whether or not we replace the first tag after selection (this is where I think the other answers are incorrect). Extrapolating to n, the number of consecutive pairs is n-1.
Without replacement, the 15 possible selected pairs are:
12 13 14 15 16 23 24 25 26 34 35 36 45 46 56. This is (15 Choose 2). Note that I do not include both 12 and 21, 13 and 31, etc. I'm assuming that we are considering all pairs without regard to order.
Therefore, when n=6 the probability of choosing two consecutive tags without replacement is 5/15 = 1/3. Extrapolating this to n, this becomes (n-1)/(n choose 2). This matches the answer in the back of the book.
Next, consider the same set of tags where we select a pair with replacement. Again, with n=6, the possible consecutive pairs selected are 12 23 34 45 56. This is again n-1.
With replacement, we have the same 15 possible selected pairs as above, with the additional pairs: 11 22 33 44 55 66. This yields 15 + 6 = 21 total pairs, giving 5/21 as the answer. As above, I'm assuming that we are considering all pairs without regard to order. Extrapolating this to n, this is (n-1)/[ (n choose 2) + n ]. This does not match the answer in the back of the book which is 2(n-1)/n^2.
From the multiple online solutions that I found, the total number of possible selected pairs is n^2; this violates my assumption of choosing pairs without regard to order in part a. Also, the set of consecutive pairs also seems to have been computed without regard to order. I don't understand why we would choose pairs without regard to order in part a but with regard to order in part b. Or I may be misunderstanding this in some other way.
Thank you for any assistance you can offer.
Note that the same problem in my 1970s era text book can be found in this author's online text:
http://books.google.com/books?id=GG9rgn3yExwC&pg=PA9&lpg=PA9&dq=%22a+box+contains+tags+marked%22&source=bl&ots=ODAMoe5flZ&sig=Ua_FlaJ4v2hsQI4lJ4K1uq38eU8&hl=en&sa=X&ei=oGOeUrfrOKK2sASAjYDoBA&ved=0CCsQ6AEwAA#v=onepage&q=%22a%20box%20contains%20tags%20marked%22&f=false
Also, a similar problem is here:
https://www.cs.drexel.edu/classes/ProbStat/mcs311_Spring98/test1ans.pdf
Best Answer
You are assuming that order doesn't matter in the second case, but this is the wrong assumption. Order definitely matters. You have, in the case of $n=6$ a sample space of $6^2$ Even though when you finally pull both tags out, a $(2,1)$ is the same as $(1,2)$, these are still different events and must be treated differently. Since this is the case, let's look at $n=6$. All consecutive numbers then would be; $$(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,6),(6,5)$$ So here you have 10 events that are possible, not 5. And your sample space is 36... Therefore, your probability is $$\frac{10}{36}=\frac{2\cdot5}{6^2}=\frac{2(6-1)}{6^2}$$ And this makes sense. You can only have $n-1$ consecutive pairs, since the $n$-th pair would be $(n,1)$ which are not consecutive, and our sample space consists of $n^2$ events. Since there are two ways to get consecutive integers, the formula is $$P(\text{consecutive numbers with replacement of n tags})=\frac{2(n-1)}{n^2}$$
Also, in the first case, again, you are making the faulty assumption that $(1,2)$ is the same as $(2,1)$ and I think that you make this assumption because the probability is correct under both assumptions, i.e., yours, and the correct assumption. Why?
The sample space under sampling without replacement is in the case of $n=6$ is $6\cdot5=30$. This is the case because pairs such as $(1,1), (2,2)$ are impossible without replacement. However, you can still get the ten pairs of consecutive numbers listed above, so therefore, under the correct assumption $$P(\text{consecutive numbers without replacement of n tags})=\frac{2(n-1)}{n(n-1)}=\frac2{n}$$ If $n=6$, you get your probability is $\frac1{3}$, which is what you got under your faulty assumption. Hope this helps shed a little light.