If k integers are selected at random and without replacement from 1 to 100 what is the probability that any of the integers are adjacent?

Question

I understand the denominator would be 100 choose k, but I don't understand how to calculate the # of combinations which have any adjacent integers.

I remember the basics of probability and combinatorics from a college level statistics class from over 5 years ago, but many of the details escape me. I'm trying to figure out the probability of an event in a card game and I've condensed the most difficult part of the problem to the above statement.

Answer 1

Suppose you want to select $4$ tokens from $10\;\rightarrow \binom {10}4= 210$ ways

• Take out those $4$ tokens, $6$ remain with $7$ interstices shown by uparrows $\uparrow\,\bullet\uparrow\,\bullet\uparrow\,\bullet\uparrow\,\bullet\uparrow\bullet\uparrow\bullet\uparrow$

• Insert back the $4$ tokens in $\binom74 = 35$ non-adjacent ways

• P(Tokens with at least two adjacent members) $= 1 - \frac{35}{210}$

It follows that for the general case of choosing $k$ integers from $n$

P(any of the integers are adjacent) $=1 - \dfrac{\dbinom{n-k+1}{k}}{\dbinom{n}{k}}$

Answer 2

Repeating the ideas in my comments, and answering the question:

If k integers are selected at random and without replacement from 1 to 100 what is the probability that any of the integers are adjacent?

I will express the probability as

$$1 - \frac{N}{D} ~: ~D = \binom{100}{k},$$

where $N$ refers to the number of solutions to:

• $x_1 + x_2 + \cdots + x_k + x_{k+1} = 100 - k.$
• $x_1, x_{k+1} \in \Bbb{Z_{\geq 0}}$
• $x_2, x_3, \cdots, x_k \in \Bbb{Z_{\geq 1}}.$

With $~\dfrac{N}{D}~$ denoting the complementary probability, $~N~$ needs to represent the total number of ways of selecting $k$ (random) integers, from the set $~\{1,2,\cdots,100\},~$ such that no two of the selected integers are adjacent.

As indicated by my comments, the idea is that the $k$ selected integers create $(k+1)$ gaps between the unselected elements in $~\{1,2,\cdots,100\},~$ with the sum of these gaps totaling $(100 - k).$

Clearly, each of the variables $~x_1, x_2, \cdots, x_{k+1}~$ needs to be a non-negative integer, to validly represent the gap between any two of the selected integers.

The first and last gap, which are represented by $~x_1~$ and $~x_{k+1}~$ are allowed to equal $~0,~$ since these gaps represent the gap before the very first selected integer and after the very last (i.e. the $k$-th) selected integer.

For example, $~x_1 = 0~$ corresponds to the first selected integer equaling "1", while $~x_{k+1} = 0~$ corresponds to the last selected integer equaling "100".

Then, the constraint that no two of the selected integers are adjacent (i.e. consecutive numbers) will be satisfied if and only if each of $~x_2, x_3, \cdots, x_k~$ is $~\geq 1.$

---

For Stars and Bars theory, see this article and this article.

Basic Stars and Bars theory indicates that the number of solutions to:

• $x_1 + x_2 + \cdots + x_r = n, ~n \in \Bbb{Z^+}.$
• $x_1, x_2, \cdots, x_r \in \Bbb{Z_{\geq 0}}$

is $~\displaystyle \binom{n + [r-1]}{r-1}.$

The given problem may be easily transformed into the basic format by the change of variable:

$y_i = x_i - 1, ~i \in \{2,3,\cdots,k\}.$

This transforms the enumeration of $N$ into counting the number of solutions to

• $x_1 + y_2 + y_3 + \cdots + y_k + x_{k+1} = 100 - k - (k-1) = 101-2k.$
• $x_1, x_{k+1} \in \Bbb{Z_{\geq 0}}$
• $y_2, y_3, \cdots, y_k \in \Bbb{Z_{\geq 0}}.$

Per Stars and Bars theory:

$$N = \binom{[101-2k] + k}{k} = \binom{101 - k}{k}. \tag1 $$

The RHS of (1) above may be moderately sanity-checked.

• If $~k > 50,~$ there are no solutions, so $~N = 0.$

• For $~k = 50,~$ the $~51~$ solutions correspond to starting with the selection $~\{1,3,5,\cdots,99\},~$ and then (optionally) selecting one of the $50$ (odd) selected elements, and incrementing each element from that point to the end by $1$.

---

$\underline{\text{Final Computation}}$

The desired probability is

$$1 - \frac{N}{D} = 1 - \frac{\binom{101 - k}{k}}{\binom{100}{k}} = 1 - \frac{[(101 - k)!] \times [(100 - k)!]}{[(101 - 2k)!] \times [(100)!]}.$$