Permutations with Global Limited Repetition – Combinatorics Explained

combinatoricspermutations

Note: In my question by repetition I mean count of extra appearances of any digit in the number.
I found this answer for permutations with global limited repetition.
The problem with that answer (as far as I understand) is that the solution in that answer requires knowing repetitions specific to each digit, which makes it not useful if we need to know the permutations with global limited repetitions without the need for providing repetitions for each digit in each number, or maybe this formula does cover permutations with global limited repetition, but I didn't learn the correct way of using it.
What I need is an example using the linked answer (if it could provide my request) to learn how to get the result without the need for providing repetitions for each digit.
The example is: all the permutations of 10-digit numbers coming from digits 0 to 9 with global repetition of 3 (no matter from which digit; meaning repetition of all the digits during all the permutations will be covered) in each number, like:

9576545100 –> 5 appeared three times which in my algorithm one time considered valid, but three time considered two time repetition and 0 appeared one extra time (2+1=3times)

9901286787 –> 9 repeated one time and 8 repeated one time and 7 repeated one time (1+1+1=3times)

7890000234 –> 0 repeated three times (3times)

The example requests how many numbers from 0000000000 to 9999999999 exist that have 3 global repetitions in them and not specific to each digit but global between digits?

In the solution from the linked answer which you could see below, we need to provide k which is a number of elements (in my case digits) that has been repeated and l is the sum of all repetitions, no matter from which digit.
So this means this solution is not for providing permutations with global limited repetition, but a solution to provide permutations with global limited repetitions with knowing each digit has been repeated how many times as a necessity.
$$\sum _{k=0}^m\binom{m}{k}\binom{m-k}{n-(l+k)}\sum _{x_1+\cdots +x_k=l}\binom{n}{\underbrace{1,\cdots ,1}_{n-(l+k)},x_1+1,\cdots ,x_k+1}$$

Best Answer

You want to find $f(n,m,r)$, the number of strings of length $n$ choosing from $m$ distinct symbols, such that there are $r$ duplicate symbols. That is, a string will consist of $n-r$ distinct symbols and $r$ duplications.

After choosing distinct symbols $\binom{m}{n-r}$, we need to sum over all partitions of $r$. In this way, we cover all possible duplications. For every partition, we choose all possible combinations of symbols and then permute them as permutations with repetitions.

Denote partitions of $r$ as "$\{p_i\} \vdash r$", where $p$ is the part and $i$ is the multiplicity.

This means we can write the formula as follows,

$$ f(n,m,r)=\binom{m}{n-r}\sum_{\{p_i\}\, \vdash\, r}\left[ \prod_{p_i\in \{p_i\}}\binom{n-r-\sum j}{i} \cdot \frac{n!}{\prod_{p_i\in \{p_i\}}[ (p+1)!]^i}\right], $$

where $\sum j$ sums already used multiplicities (in previous coefficients in the product).

This is assuming $n \ge 2r$. Otherwise, some partitions (duplications) will not be possible. To be precise, if $n\lt 2r$, we sum only over partitions such that $\sum_{p_i\in \{p_i\}} (p+1)i\le n$.

For some examples, take $n=m=10$.

E.g. 1, Partitions of $3$ are $\{3_1\},\{2_1,1_1\},\{1_3\}$. This gives,

$$\begin{align} f&= \binom{10}{7}\left[ \binom{7}{1}\frac{10!}{4!} +\binom{7}{1}\binom{6}{1}\frac{10!}{3!2!} +\binom{7}{3}\frac{10!}{[2!]^3} \right] \\&= 3556224000. \end{align}$$

Essentially, we choose and permute symbols for AAAABCDEFG, AAABBCDEFG, AABBCCDEFG. This results agrees with Bulbasaur's answer (they use a different approach).

E.g. 2, Partitions of $4$ are $\{4_1\},\{3_1,1_1\},\{2_2\},\{2_1,1_2\},\{1_4\}$. This gives,

$$\begin{align} f&= \binom{10}{6}\left[\binom{6}{1}\frac{10!}{5!} +\binom{6}{1}\binom{5}{1}\frac{10!}{4!2!} +\binom{6}{2}\frac{10!}{[3!]^2} +\binom{6}{1}\binom{5}{2}\frac{10!}{3![2!]^2} +\binom{6}{4}\frac{10!}{[2!]^4}\right] \\&= 3451442400. \end{align}$$

Essentially, we choose and permute symbols for AAAAABCDEF, AAAABBCDEF, AAABBBCDEF, AAABBCCDEF, AABBCCDDEF.

I've generated these examples with a python script made to showcase the formula.

(length: 10, symbols: 10, repetitions: 3)
+ binom(10, 7)*binom(7, 1)*10!/(4!)
+ binom(10, 7)*binom(7, 1)*binom(6, 1)*10!/(3!2!)
+ binom(10, 7)*binom(7, 3)*10!/(2!2!2!)
= 3556224000

(length: 10, symbols: 10, repetitions: 4)
+ binom(10, 6)*binom(6, 1)*10!/(5!)
+ binom(10, 6)*binom(6, 1)*binom(5, 1)*10!/(4!2!)
+ binom(10, 6)*binom(6, 2)*10!/(3!3!)
+ binom(10, 6)*binom(6, 1)*binom(5, 2)*10!/(3!2!2!)
+ binom(10, 6)*binom(6, 4)*10!/(2!2!2!2!)
= 3451442400

To iterate partitions, I use sympy.utilities.iterables.partitions.

You can run it online on replit.com/@DexterousAlpaca/GlobalRepetitions.

Related Question