1
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ A general approach would be to use the Inclusion-Exclusion Principle to exclude permutations that include pairs of adjacent identical objects. $\endgroup$ – N. F. Taussig Jul 31 at 5:04
  • $\begingroup$ Did you solve it for 7 objects at first? $\endgroup$ – Fareed Abi Farraj Jul 31 at 5:12
  • 2
    $\begingroup$ Markus Scheuer solved this related question using a generating function of generalized Laguerre polynomials. You may find my solution using the Inclusion-Exclusion Principle more accessible. $\endgroup$ – N. F. Taussig Jul 31 at 6:05
  • 1
    $\begingroup$ Note that if any $s_i$ is too big, the number of ways will be zero. This suggests there's no simple formula. $\endgroup$ – Gerry Myerson Jul 31 at 6:43
  • 1
    $\begingroup$ The details are still more in the title than in the statement of the question. As a rule, all data needed to figure out the framework of the question and the question itself in the question, should be given in the post. The question is still more present in the title as in the post. Now please tell us what are exactly ways and how can we deduce that permutations (with which property) should be counted. And most important, please show us explicitly what would be the solution in a simple case "like 11122", then we may have an idea what should be couted. And show us the own tries! $\endgroup$ – dan_fulea Jul 31 at 21:16
2
$\begingroup$

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.

In how many ways can the digits of the string $1112233$ be arranged so that no two identical digits are adjacent?

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.