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$.

  • $\begingroup$ Usually , $1$ is not considered to be a prime number. $\endgroup$ – Peter Sep 5 '18 at 7:44
  • $\begingroup$ If I understand your question correctly, you wish to count how many $N$-digit numbers can be formed with the digits $1, 2, 3, 5, 7$ if the order in which the digits appear does not matter. Please confirm or clarify. $\endgroup$ – N. F. Taussig Sep 5 '18 at 7:56
  • $\begingroup$ The order in which the digits appear does matter, but only for different digits. It is just like, if I have the array {2, 2, 3, 5} in which the first 2 has the index 1 and the second 2 has the index 2, inverting them will not count as another "combination", but if I permute the indices array and obtain {2, 3, 2, 5}, then this counts as another "combination". $\endgroup$ – silviubogan Sep 5 '18 at 8:26
  • $\begingroup$ In that case, there are five choices ($1, 2, 3, 5, 7$) for each of the $N$ positions, so there are $5^N$ possible sequences. $\endgroup$ – N. F. Taussig Sep 5 '18 at 9:47
  • $\begingroup$ @N.F.Taussig I updated the question with a new example, for which your formula is not functioning well. $\endgroup$ – silviubogan Sep 7 '18 at 8:50

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.


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.