General formula for number of strings created from $n$ letters, where $m$ are identical and the rest are distinct.

Question

The problem:

Given $n$ letters, of which $m$ are identical and the rest are distinct, find a formula for the number of strings which can be made.

Tests:

Ex 1. n = 3, m = 0: DOG: { , D, O, G, DO, DG, OD, OG, GD, GO, DOG, DGO, ODG, OGD, GOD, GDO} = 16 strings where there are 1 len(0), 3 len(1), 6 len(2), and 6 len(3).

Ex 2. n = 3, m = 2: HII: { , H, I, II, HI, IH, HII, IIH, IHI} (the I's are indistinguishable) = 9 strings where there are 1 len(0), 2 len(1), 3 len(2), and 3 len(3).

I am trying to arrive at a general formula but it difficult to grasp the relation. I understand that the ways to permute $n$ distinct letters is just $n!$ but don't know how to extend my understanding of letters being repeated from a case by case basis to a general formula.

Any assistance would be appreciated.

Answer 1

If all letters are different, you get $n!$ ways to arrange them. If now $m$ are different, and $n - m$ are the same, you have $n!$, but by a factor $(n - m)!$ too large (consider you have $n - m$ letters $a_1, \dotsc, a_{n - m}$ and then $b, c, \dotsc$, arranging those gives $n!$ possibilities; if you "turn off" the subindices, collections of $(n - m)!$ collapse into strings of just $a, b, \dotsc$).

Check out The Tao of BOOKKEEPER for enlightenment.

Answer 2

It has been some time, and I only saw this after going through my previous questions, but I figured out the answer to this question awhile back.

To reiterate, we are given $n$ letters, of which $m$ are identical and the rest distinct, and want to find a formula for the number of strings which can be made from them.

We have that the number of strings is equal to

$$\sum_{k\geq 0} \sum_{j=0}^m \binom{k}{j}\binom{n-m}{k-j}(k-j)!$$

This can be interpreted as first choosing the places in the string for the copies of repeated letters, then choosing the rest of the letters, and then finally ordering them.