Number of combinations of digits where consecutive identical digits cannot be inverted to produce a new combination

combinatorics

I have a number in base $10$ containing $N$ digits of $1$, and $1$ or more digits that are $1$-digit prime numbers. The prime number digits can be repeated.

For example, $111225777$.

I wish to know how many "combinations" (not in the usual mathematical sense) of the digits of this number exist for which consecutive identical digits do not form a new "combination". In other words, the order of the indices of $2$ digits matter only if the digits are different. For example, $2235$ has the 1st digit and the 2nd digit equal to $2$, a counted combination is $2325$ but just by inverting the first and the second digit you do not create a counted combination.

Update: Another example:

The matching combinations of the digits $K1111$ are

  1. $K1111$
  2. $1K111$
  3. $11K11$
  4. $111K1$
  5. $1111K$

In total here are 5 possibilities, not $2^5$.

Best Answer

There seem to be two different questions here:

How many sequences of length $N$ can be formed using the digits $1, 2, 3, 5, 7$ with repetition?

There are five choices for each of the $N$ positions in the sequence, so there are $5^N$ such sequences.

This type of problem is called a permutation with repetition.

How many distinguishable sequences of length $N$ can be formed with $n_1$ $1$s, $n_2$ $2$s, $n_3$ $3$s, $n_5$ $5$s, and $n_7$ $7$s, where $n_1 + n_2 + n_3 + n_5 + n_7 = N$?

Let's consider the following example:

In how many distinguishable ways can the elements of the sequence $1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7$ be arranged?

There are a total of $1 + 2 + 3 + 5 + 7 = 18$ numbers in the sequence. We can fill one of the eighteen positions with the $1$ in $\binom{18}{1}$ ways, two of the remaining seventeen positions with the two $2$s in $\binom{17}{2}$ ways, three of the remaining fifteen positions with the three $3$s in $\binom{15}{3}$ ways, five of the remaining twelve positions with the five $5$s in $\binom{12}{5}$ ways, and all of the remaining seven positions with the seven $7$s in $\binom{7}{7}$ ways. Hence, there are $$\binom{18}{1}\binom{17}{2}\binom{15}{3}\binom{12}{5}\binom{7}{7} = \frac{18!}{1!17!} \cdot \frac{17!}{2!15!} \cdot \frac{15!}{3!12!} \cdot \frac{12!}{5!7!} \cdot \frac{7!}{7!0!} = \frac{18!}{1!2!3!5!7!}$$ such arrangements. The factors of $1!$, $2!$, $3!$, $5!$, $7!$ in the denominator represent, respectively, the number of ways the $1$s, $2$s, $3$s, $5$s, and $7$s can be permuted among themselves within a given arrangement without producing an arrangement that is distinguishable from the given arrangement.

By similar reasoning, the number of distinguishable arrangements of a sequence of length $N$ with $n_1$ $1$s, $n_2$ $2$s, $n_3$ $3$s, $n_5$ $5$s, and $n_7$ $7$s, where $n_1 + n_2 + n_3 + n_5 + n_5 + n_7 = N$ is $$\binom{N}{n_1}\binom{N - n_1}{n_2}\binom{N - n_1 - n_2}{n_3}\binom{N - n_1 - n_2 - n_3}{n_5}\binom{N - n_1 - n_2 - n_3 - n_5}{n_7} = \frac{N!}{n_1!n_2!n_3!n_5!n_7!}$$

This type of problem is called a permutation of a multiset.

Related Question