# Probability puzzle with balls in an urn

I need help with a problem about classic probability and possible extensions to it. Suppose you have an urn with $N$ distinguishable balls. Every time you draw $k$ balls out of $N$. Some possible questions I haven't figured out yet are

• what is the probability that two given balls never appear in two consecutive draws, out of, say, $5$ draws (or $M$ draws, more broadly)?
• what is the probability that this is true for any pair of balls?
-
Could you please clarify your question. Every time you draw $k$ balls out of $n$, with replacement? Given two balls, say A and B, you do not want both of them occurring in any each of any two consecutive draws? It is a little confusing. –  Sasha May 22 '12 at 23:24

I'll assume you draw $k$ balls, put them back in the urn, draw $k$ balls, put them back, etc., etc.
The number of $k$-sets of balls is $N\choose k$.
Well, you might have none of the balls from the 17th draw. There are $N-k\choose k$ ways to do that (note that this is interpreted as zero if $N\lt2k$). Or, you might have exactly one of the balls from the 17th draw. There are ${k\choose1}{N-k\choose k-1}$ ways to do that (zero, if $N\lt2k-1$). All told, $${N-k\choose k}+{k\choose1}{N-k\choose k-1}$$ ways to make the 18th draw and not have two balls from the 17th draw.
So, the probability of not having two balls from the 17th draw in the 18th draw is $$\left({N-k\choose k}+{k\choose1}{N-k\choose k-1}\right)\div{N\choose k}$$ Let's call this quantity $P=P(N,k)$. It follows that if you draw balls $r$ times, the probability that you never have two balls in common in two consecutive draws is $P^{r-1}$. This answer the second question.