0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Commented Sep 13, 2021 at 13:05

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Paramanand Singh
    Commented Jan 3, 2022 at 5:27
2
$\begingroup$

I will divide the solution into $3$ cases and make use of exponential generating functions.

$\mathbf{Case-I-)}$ Three digits repeats two times , the rest repeats at most one times:

Step-I-) Choose which digits will be repeating by $C(10,3)$

Step II-) Write exponential generating function form such that $$10! \times [x^{10}]\bigg(\frac{x^2}{2!}\bigg)^3 \bigg(1+\frac{x}{1!}\bigg)^7 $$

Step III-) $$C(10,3) \times 10! \times [x^{10}]\bigg(\frac{x^2}{2!}\bigg)^3 \bigg(1+\frac{x}{1!}\bigg)^7 $$

Step IV-) https://www.wolframalpha.com/input/?i=expanded+form+of+%28x%5E2+%2F+2%29%5E3+%281%2Bx%29%5E7 $$120 \times 10! \times \frac{35}{8} = 1,905,120,000$$

$\mathbf{Case-II)}$ One digits repeats three times and one digits repeats two times , the rest can appear at most once :

Step-I-) Choose which digits appears three times and which appear two times by $C(10,1) \times C(9,1)$

Step II-) Write exponential generating function form such that $$10! \times [x^{10}]\bigg(\frac{x^3}{3!}\bigg)\bigg(\frac{x^2}{2!}\bigg)\bigg(1+\frac{x}{1!}\bigg)^8$$

Step III-) $$C(10,1) \times C(9,1) \times 10! \times [x^{10}]\bigg(\frac{x^3}{3!}\bigg)\bigg(\frac{x^2}{2!}\bigg)\bigg(1+\frac{x}{1!}\bigg)^8 $$ Step IV-) https://www.wolframalpha.com/input/?i=expanded+form+of+%28x%5E2+%2F+2%29+%281%2Bx%29%5E8+%28x%5E3+%2F+6%29

$$90 \times 10! \times \frac{14}{3} =1,524,096,000$$

$\mathbf{Case-III-)}$ One digits repeats $4$ times ,the rest at most once :

Step I- ) Select which one repeats $4$ times by $C(10,1)$

Step II-) $$10! \times [x^{10}]\bigg(\frac{x^4}{4!}\bigg)\bigg(1+\frac{x}{1!}\bigg)^9$$

Step III-) $$C(10,1) \times 10! \times [x^{10}]\bigg(\frac{x^4}{4!}\bigg)\bigg(1+\frac{x}{1!}\bigg)^9 $$

Step IV-)https://www.wolframalpha.com/input/?i=expanded+form+of+%28x%5E4+%2F+24%29+%281%2Bx%29%5E9

$$10 \times 10! \times \frac{7}{2}=127,008,000$$

At last , find the summation of all step III 's in each cases . You can use wolfram alpha to calculate exponential generating funcions.

Answer is $$1905120000+1524096000+127008000=3,556,224,000$$

$\endgroup$
14
  • $\begingroup$ Would you please edit the answer to cover 0000000000 to 9999999999. And also please explain how could I use it to cover 100 digits instead of 10 digits. I have 100 distinct values that created big numbers consisting of 100 digits each. $\endgroup$
    – Eftekhari
    Commented Sep 12, 2021 at 18:47
  • 1
    $\begingroup$ @Eftekhari if you use $100$ digits , it is impossible for $3$ global repetiton if there are $10$ distinct digits $\endgroup$ Commented Sep 12, 2021 at 18:55
  • 1
    $\begingroup$ @Eftekhari if you have $100$ distict digits , then use $100$ instead of $10$ in combination and change the exponents of generating function and calculate the result for $[x^{100}]$ $\endgroup$ Commented Sep 12, 2021 at 19:00
  • $\begingroup$ Yes! 3,556,224,000 is correct according to my algorithm. Thank you. I'll study your solution and come back for accepting the answer. $\endgroup$
    – Eftekhari
    Commented Sep 12, 2021 at 20:20
  • $\begingroup$ @Eftekhari you are welcome! $\endgroup$ Commented Sep 12, 2021 at 20:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .