For example, consider the collection of $7$ objects $1112233$, where identical objects are marked with the same number.
One possible valid arrangement would be $1231231$, in which no two $1$s, $2$s or $3$s are together, i.e. next to each other either to the left or right.
I am looking for a general approach/formula for $n$ objects with $k$ groups of identical objects of sizes $s_1, \dots , s_k$ such that $s_i \geq 1$ and $\sum_{i=1}^{k} s_i = n$
Edit: For a simple case like $11122$, there is only one possible arrangement(permutation), i.e. $12121$
Best Answer
As indicated in the comments, if the problem has a solution, then the Inclusion-Exclusion Principle can be applied by excluding those arrangements in which a pair of identical digits are adjacent. A general formula would be hard to formulate since the number of admissible arrangements depends on the number of times each digit appears in the sequence.
Method 1: Here is a simple method that is hard to generalize to more complicated problems.
We first arrange the string $2233$, which can be done in $\binom{4}{2} = 6$ ways. They are: $$2233, 2323, 2332, 3223, 3232, 3322$$
Doing so creates five spaces in which we can place the three ones, three between successive digits and two at the ends of the row.
We consider cases.
$2233$: To ensure that no two consecutive digits are adjacent, we must place a $1$ between each pair of identical digits. Doing so leaves three spaces in which we can place the remaining $1$.
$$\square 212 \square 313\square$$ Choosing one of these spaces determines the arrangement. Hence, there are $3$ such arrangements.
$3322$: By symmetry, there are also three arrangements that can be created by inserting three ones into the string $3322$.
$2323$: To ensure that no two consecutive digits are adjacent, we must insert a $1$ in three of the five spaces determined by the string. $$\square 2 \square 3 \square 2 \square 3 \square$$ This can be done in $\binom{5}{3} = 10$ ways.
$3223$: By symmetry, there are also ten arrangements that can be created by inserting three ones into the string $3232$.
$2332$: To ensure that no two consecutive digits are adjacent, we must insert a $1$ between the pair of identical digits and in two of the remaining four spaces. $$\square 2 \square 313 \square 2 \square$$ This can be done in $\binom{4}{2} = 6$ ways.
$3223$: By symmetry, there are also six arrangements that can be created by inserting three ones into the string $3223$.
In total, there are $$2\left[\binom{3}{1} + \binom{5}{3} + \binom{4}{2}\right] = 38$$ arrangements of the string $1112233$ in which no two adjacent digits are identical.
Method 2: We apply the Inclusion-Exclusion Principle.
An arrangement is determined by choosing three of the seven positions in the string for the ones, two of the remaining four positions for the twos, and filling the final two positions with the threes. This can be done in $$\binom{7}{3, 2, 2} = \binom{7}{3}\binom{4}{2}\binom{2}{2} = \frac{7!}{3!2!2!}$$ ways.
From these, we must subtract those arrangements in which one or more pairs of identical digits are adjacent.
A pair of identical adjacent digits: We consider cases.
Two ones are adjacent: We have six objects to arrange: $11, 1, 2, 2, 3, 3$. Choose two of the six positions in the string for the twos and two of the remaining four positions for the threes. That leaves us with two positions to fill with the distinct objects $11$ and $1$. These positions can be filled in $2!$ ways. Hence, there are $$\binom{6}{2, 2, 1, 1} = \binom{6}{2}\binom{4}{2}2! = \frac{6!}{2!2!1!1!}$$ such arrangements.
Two twos are adjacent: We have six objects to arrange: $1, 1, 1, 22, 3, 3$. Choose three of the six positions in the string for the ones and two of the remaining three positions for the threes. The block $22$ must occupy the remaining position in the string. Hence, there are $$\binom{6}{3, 2, 1} = \binom{6}{3}\binom{3}{2}\binom{1}{1} = \frac{6!}{3!2!1!}$$ such arrangements.
Two threes are adjacent: By symmetry, there are $$\binom{6}{3, 2, 1} = \binom{6}{3}\binom{3}{2}\binom{1}{1} = \frac{6!}{3!2!1!}$$ such arrangements.
Two pairs of adjacent identical digits: We consider cases.
Two pairs of adjacent ones: This can only occur if the three ones are consecutive. Thus, we have five objects to arrange: $111, 2, 2, 3, 3$. Choose two the five positions in the string for the twos and two of the remaining three positions in the string for the threes. The block $111$ must occupy the remaining position. Hence, there are $$\binom{5}{2, 2, 1} = \binom{5}{2}\binom{3}{2}\binom{1}{1} = \frac{5!}{2!2!1!}$$ such arrangements.
A pair of adjacent ones and a pair of adjacent twos: We have five objects to arrange: $11, 1, 22, 3, 3$. Choose two of the five positions in the string for the threes. The remaining three positions must be filled with the three distinct objects $11, 1, 22$, which can be done in $3!$ ways. Hence, there are $$\binom{5}{2, 1, 1, 1} = \binom{5}{2}3! = \frac{5!}{2!1!1!1!}$$ such arrangements.
A pair of adjacent ones and a pair of adjacent threes: By symmetry, there are $$\binom{5}{2, 1, 1, 1} = \binom{5}{2}3! = \frac{5!}{2!1!1!1!}$$ such arrangements.
A pair of adjacent twos and a pair of adjacent threes: We have five objects to arrange: $1, 1, 1, 22, 33$. Choose three of the five positions in the string for the ones. The remaining two positions can be filled with the distinct objects $22$ and $33$ in $2!$ ways. Hence, there are $$\binom{5}{3, 1, 1} = \binom{5}{3}2! = \frac{5!}{3!1!1!}$$ such arrangements.
Three pairs of adjacent identical digits: We consider cases.
Two pairs of adjacent ones and a pair of adjacent twos: We have four objects to arrange: $111, 22, 3, 3$. Choose two of the four positions in the string for the threes. The remaining two positions can be filled with the distinct objects $111$ and $22$ in $2!$ ways. Hence, there are $$\binom{4}{2, 1, 1} = \binom{4}{2}2! = \frac{4!}{2!1!1!}$$ such arrangements.
Two pairs of adjacent ones and a pair of adjacent threes: By symmetry, there are $$\binom{4}{2, 1, 1} = \binom{4}{2}2! = \frac{4!}{2!1!1!}$$ such arrangements.
A pair of adjacent ones, a pair of adjacent twos, and a pair of adjacent threes: We have four objects to arrange: $11, 1, 22, 33$. Since they are all distinct, they can be arranged in $4!$ ways.
Four pairs of adjacent identical digits: We have three objects to arrange: $111, 22, 33$. Since they are all distinct, they can be arranged in $3!$ ways.
By the Inclusion-Exclusion Principle, the number of admissible arrangements is $$\binom{7}{3, 2, 2} - \binom{6}{2, 2, 1, 1} - \binom{6}{3, 2, 1} - \binom{6}{3, 2, 1} + \binom{5}{2, 2, 1} + \binom{5}{2, 1, 1, 1} + \binom{5}{2, 1, 1, 1} + \binom{5}{3, 1, 1} - \binom{4}{2, 1, 1} - \binom{4}{2, 1, 1} - 4! + 3! = 38$$
Notice that exploiting symmetry can simplify the calculations.