Finding the Total number of permutation using a selective formula

Question

I am a python programmer,trying to upgrade a python program I created.

I am aware the total number of permutations can be calculated using

n^r 

where n is the total number of things to choose from and r is how many we choose..

for example consider the string "abc" where need to generate three letter "words"..the result below

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

Question

What I am trying to accomplish is to derive a formula for the total number of permutations where each permutation has maximum nth characters of the same identity..consider this example

for example the total number of permutations that has only two letters of the same type repeating....

This is my results for generating all permutations from my program with two letters of the same type reaming

aab - only two 'a'
aac - only two 'a'
aba - onyl two 'a'
abb - only two 'b'
abc - maximum is two letters repeating..also good
aca - maximum is two letters repeating..also good
acb - maximum is two letters repeating..also good
acc - maximum is two letters repeating..also good
baa- .maximum is two letters repeating..also good
bab ..................
bac....................
bba
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb

TOTAL NUMBER OF PERMUTATION IS 24 I can't seem to derive a way to do this BEFORE outputing the results..

In a nutshell

I want to find A FORMULA for the number of permutation that only has nth letters in each permutation repeating not more than nth of the same type..

I want to precalculate the total number of permutations where each permutation has nth letter of the same type remaining and output this to the user of my program

---

My program is bulky but here is the permutation codes I am using (note I am using itertools from python built in libraries)

for perm in itertools.product(string,repeat=self.word_length):
    if args:
        args[0]()                    
    #print("after",self.counter)
    self.counter=self.counter+1
    result1=[perm.count(z) for z in perm]
    result1.sort(reverse=True)
    if result1[0]<=self.actual_repeat:
        yield perm

I am using itertools to generate the permutations , count each letter and find their fequency and filter for two letter words...the variable self.actual repeat is 2

Answer 1

Let us take a slightly more complex example: $5$ distinct characters, max $3$ of one kind:

You can have a number of possible patterns of string length $5$ (say):

$3-2,\quad 3-1-1,\quad2-2-1,\quad2-1-1-1,\quad$ and $\quad1-1-1-1-1$

The formula you can use is [Choose characters for pattern]$\times$[permute characters]

e.g. for the first pattern, $\binom51\binom41 \times \frac{5!}{3!2!}= 200$

and for the second pattern, $\binom51\binom42 \times \frac{5!}{3!1!1!!} = 600$

Note particularly $\binom42,\;not\; \binom41\binom31$ for the second pattern,
as choosing $aaabc$ and $aaacb$ are the same , the order in which we choose $b$ and $c$ doesn't matter.

For your particular example, only $2$ patterns are possible:
$2-1:\; \binom31\binom21 \times \frac{3!}{2!1!} = 18$
$1-1-1:\; \binom33 \times \frac{3!}{1!1!1!} = 6$
Adding up, ans = $24$

---

ADDED MATERIAL to make computation more mechanical, using multinomial coefficients:

Note down the frequencies of triples, doubles, singles, and non-occurrences for each pattern, e.g. for the pattern $3-1-1$, there is $1$ triple, $2$ singles, $2$ non-occurrences so the multinomial coefficient for choosing letters will be $\binom{5}{1,2,2}$ and that for permuting the pattern will be $\binom{5}{3,1,1}$ which is the same as $\frac{5!}{3!1!1!}$

For my example, you can now mechanically compute and add up:

$3-2: \binom5{1,1,3}\binom5{3,2}$
$3-1-1: \binom5{1,2,2}\binom5{3,1,1}$
$2-2-1: \binom5{2,1,2}\binom5{2,2,1}$
$2-1-1-1: \binom5{1,3,1}\binom5{2,1,1,1}$
$1-1-1-1-1:\binom55\binom5{1,1,1,1,1}$

Answer 2

For strings from $\{a,b,c\}$ of length $3$ the answer is simple. Take all the permutations (there are $3^3$) and subtract the number that have more than two of a single letter. In this case there are $3$, one triple for each letter.

$$3^3 - 3 = 24$$

As the next example, suppose we have strings of length $7$ from $\{a,b,c,d,e\}$ where we can't have more that $3$ of a single letter. There are $7^5$ strings without any restrictions. Now we need to subtract out the number of strings with $4, 5, 6,$ or $7$ of the same letter. A word with $4$ of the same letter will be a permutation of a set of one of the following forms:

$$\{w,w,w,w,x,y,z\} \text{ or } \{w,w,w,w,x,x,y\} \text{ or } \{w,w,w,w,x,x,x\}$$

where $w,x,y,z$ represent some choice of four letters from $\{a,b,c,d,e\}$. Now for the first form, there are $5$ choices for $w$, $\binom{4}{3}$ choices for $x,y,z$, and $\binom{7}{4}$ permutations of $\{w,w,w,w,x,y,z\}$.

(See here for details on the last part of the previous sentence).

Thus the number of strings with exactly $4$ of the same letter is

$$5\cdot\binom{4}{3}\cdot\binom{7}{4,1,1,1} = \frac{5 \cdot 4! \cdot 7!}{3! \cdot 4!} = 5 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 4200$$

Similarly, for $\{w,w,w,w,x,x,y\}$ and $\{w,w,w,w,x,x,x\}$ we have

$$5\cdot\binom{4}{2}\cdot\binom{7}{4,2,1} = \frac{5 \cdot 4! \cdot 7!}{2! \cdot 4! \cdot 2!} = 5 \cdot 7 \cdot 6 \cdot 5 \cdot 3 \cdot 2 = 6300$$

and

$$5\cdot\binom{4}{1}\cdot\binom{7}{4,3} = \frac{5 \cdot 4 \cdot 7!}{4! \cdot 3!} = 5 \cdot 4 \cdot 7 \cdot 5 = 700$$

Putting this all together so far,

$$5 \cdot \sum_{i=1}^3 \binom{4}{i}\binom{7}{4,4-i}$$

[... Running out of time for now. Will return later ... ]