A general formula for $n$ distinguishable arrangements of length $\ell$ of a sequence of a given size?

Solution 1:

This may indeed be "overkill", but there is a fairly simple general formula for the exponential generating function. Let $n_i$ be the number of times the $i$th letter is repeated - the order we put the letters in doesn't matter of course. In your example, if we put the word PROBABILITY we have one P, one R, one O, two B's, one A, two I's, one L, one T, and one Y, so we get $$(n_1, ..., n_8) = (1,1,1,2,1,2,1,1)$$ if I've counted correctly. Now let $a_l$ be the number of words of length $l$, and $m$ be the number of distinct letters. I claim $$\sum_l \frac{a_l}{l!} x^l = \prod_{i=1}^m \sum_{j=0}^{n_i} \frac{x^{n_i}}{n_i!};$$ in your example this is $$\sum_l \frac{a_l}{l!} x^l = (1+x)^6(1+x + x^2/2)^2$$ since we have $7$ letters appearing once and $2$ letters appearing twice each. So if you want to know the number of such words with a specific length, you can extract that coefficient (probably with a computer). In this case we get $$ (1+x)^7(1+x + x^2/2)^2 = 1 + 9x + 37x^2 + 92x^3 + 617/4 x^4 + 735/4x^5 + ...$$

and so the answer is $735/4 *5!$.

To see this, note that if we restrict ourselves to a given (multi)-set of letters (with possible repititions) and require that our word have all of these letters (each letter repeated as many times as it appears in our multiset, we can count the number of words by the so-called multinomial coefficient - if we have $r_i$ of the $i$th letters, the total number of words is $${ r_1 + \ldots + r_m \choose r_1, \ldots , r_m} :=\frac{(r_1 + ... + r_m)!}{r_1!...r_m!}$$ since we may choose any permutation of the total set of symbols with repetition, and then divide out the number of permutations of the like symbols.

Now consider the expansion of the right-hand side above: if we choose to use the $r_i$th power in the $i$th factor, we get the term $$\frac{x^{r_1 + ... + r_m}}{r_1! ... r_m!} = \frac{x^s}{s!} {s \choose r_1, ..., r_m} $$ where $s = \sum_i r_i$; and then summing all the terms gives the desired formula.

The same analysis shows that the answer is $$a_l = \sum_{r_1 + ... + r_m = l, r_i \leq n_i} {l \choose r_1, \ldots, r_m}$$ although this is not as pretty.

Solution 2:

I assume the problem is to find the number of $5$-letter words that can be formed, where we can use a letter no more times than it appears in PROBABILITY.

There is no useful general formula. The closest I could get would be to use generating functions, which are certainly overkill for the concrete problem you mentioned. I think it is best to attack this problem by breaking the words up into types, then counting and adding. We have two $B$, two I, and seven single letters. Our words are of four types:

(i) Two B, two I, and a single;

(ii) Two B, the rest singles;

(iii) Two I, the rest singles;

(iv) All singles.

For type (i), we can choose where the B's go in $\binom{5}{2}$ ways. For each of these ways we can choose where the I's go in $\binom{3}{2}$ ways, and for each choice of location for the B's and I's choose a letter from the remaining $7$, for a total of $\binom{5}{2}\binom{3}{2}(7)$.

For type (ii), decide where the B's go in $\binom{5}{2}$ ways. Then we have $8$ letters left, since the I can be used, but not twice. We can fill the $3$ empty spots in $(8)(7)(6)$ ways, for a total of $\binom{5}{2}(8)(7)(6)$ ways.

For type (iii) the analysis and answer are the same as for (ii).

For type (iv), we have $9$ distinct letters, and can do the job in $(9)(8)(7)(6)(5)$ ways.