How to find the probability that the permutation does not have adjacent digits? 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})$.
 A: 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.
A: 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}.$$
