How to find the probability that the permutation does not have adjacent digits?

Question

I am learning how to use exclusion-inclusion principle (PIE). I wish to find the probability that a random permutation of $1112345$ does not have adjacent digits like for example $1121345$ and $2345111$ are not allowed.

There are $\frac{7!}{3!}=840$ possible permutations.

I think the probability can be calculated using the principle of inclusion-exclusion:

$$ \begin{align} P(\text{does not have adjacent 1s})&=1-P(\text{have at least a pair of adjacent 1s}) \\&= 1-P(\text{have sequence 11 OR have sequence 111}) \\&= 1-(P(\text{have sequence 11})+P(\text{have sequence 111})-P(\text{have sequence 11 AND have sequence 111})) \end{align} $$

Is that the correct application of PIE?

I know how to calculate $P(\text{have sequence 11})$ and $P(\text{have sequence 11})$ but I am not sure how to calculate $P(\text{have sequence 11 AND have sequence 111})$.

Answer 1

It's a correct application of P.I.E., but not a useful one. The problem is that if your permutation contains $111$, it certainly also contains $11$. So you end up simplifying to $1 - P(\text{has }11) + P(\text{has }111) - P(\text{has }111)$ or just $1 - P(\text{has }11)$, which is what you started with.

A more profitable approach is to label the $1$'s to distinguish them: $1_a 1_b 1_c 2345$. Then do inclusion/exclusion on the three events "$1_a$ and $1_b$ are adjacent", "$1_b$ and $1_c$ are adjacent", and "$1_a$ and $1_c$ are adjacent".

Call these events $A_{ab}, A_{bc}, A_{ac}$ respectively. Then we want to find \begin{align} P(\text{no adjacent 1's}) &= 1 - P(A_{ab} \text{ or } A_{bc} \text{ or } A_c) \\ &= 1 - P(A_{ab}) - P(A_{bc}) - P(A_{ac}) \\ & \quad + P(A_{ab} \text{ and } A_{bc}) + P(A_{ab} \text{ and } A_{bc}) + P(A_{ac} \text{ and } A_{bc}) \\ & \quad - P(A_{ab} \text{ and } A_{bc} \text{ and } A_{ac}) \\ &= 1 - 3 P(A_{ab}) + 3 P(A_{ab} \text{ and } A_{bc}) \end{align} where the last line follows by symmetry (plus the fact that $1_a, 1_b, 1_c$ cannot all be adjacent to each other).

Here, $P(A_{ab}) = \frac{2 \cdot 6!}{7!} = \frac27$: if $1_a$ and $1_b$ are adjacent, we can treat them as one symbol $[1_a 1_b]$, so there are $6!$ ways to order the $6$ symbols we now have, and then $2$ ways to choose the order of $1_a$ and $1_b$. We can compute $P(A_{ab} \text{ and }A_{bc})$ similarly.

Answer 2

Alternative approach:

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

The $3$ 1's divide the sequence into $4$ regions.

Consider the number of solutions to :

• $x_1 + x_2 + x_3 + x_4 = 4.$

• $x_1, x_4 \in \Bbb{Z_{\geq 0}}.$

• $x_2, x_3 \in \Bbb{Z_{\geq 1}}.$

The 3rd bullet point above accommodates that none of the 1's can be adjacent to each other.

If $S$ is the number of solutions, then the probability will be

$$\frac{4! \times S}{D} ~: ~D = \frac{7!}{3!} = 840.$$

This is because for each satisfying solution, there are $4!$ ways of ordering the digits that are not equal to $1$.

---

$S$ may be readily computed via a change of variable.

Let $~y_2 = x_2 - 1, ~y_3 = x_3 - 1.$

Then the computation of $S$ corresponds to the number of solutions to

• $x_1 + y_2 + y_3 + x_4 = 4 - 2 = 2.$

• $x_1, x_4 \in \Bbb{Z_{\geq 0}}.$

• $y_2, y_3 \in \Bbb{Z_{\geq 0}}.$

By Stars and Bars theory,

$$S = \binom{2 + 3}{3} = \binom{5}{3} = 10 \implies $$

the corresponding probability equals

$$\frac{10 \times 4!}{840} = \frac{2}{7}.$$