# Permutations with repetitions

1. May 3, 2007

### vanesch

Staff Emeritus
Hi all,

I have a question, which I would have thought has been resolved already since a few centuries, but I can't find anything on it. I'm looking for the following quantity: the number of permutations with repetition of a set of cardinality k, drawn from a set with n elements, of which there are exactly l elements different. I call that number, Z_{k,n}^l (I haven't found any standard notation for it).

Now, I've found a recursive definition for Z:
$$Z_{k,n}^l = Z_{k-1,n}^l.l + Z_{k-1,n}^{(l-1)}.(n-l+1)$$

and boundary conditions:
$$Z_{k,n}^k = P^n_k = \frac{n!}{(n-k)!}$$

(indeed, a permutation of k elements out of n, with repetition, but of which there are k different elements, is simply a permutation without repetition)

and:
$$Z_{k,n}^1 = n$$

(indeed, if there is only one "different" element, all k elements drawn are the same, and hence there are exactly n possibilities: they are all equal to the first of the n elements, or to the second, or...)

The recursion relation has been found by considering (k-1) elements drawn, and by adding the k-th element. The first term corresponds to the case where the k-1 elements already have l different elements in them, so the k-th one must be one of them, while the second term corresponds to the case where the k-1 elements have only l-1 different elements in them, so the k-th element must be distinct.

The recursion + boundary conditions are complete, I can program them in Mathematica, and seem to obtain good results.

We have of course that $$\sum_{l=1}^k Z_{k,n}^l = n^k$$, as the sum over all possible numbers of different elements comes down to picking all possible permutations with repetition.

But I would have expected this problem to have been solved already some centuries ago, with some explicit, closed-form expression, which I can't find.

Anybody any suggestion?
thanks,
Patrick.

Last edited: May 3, 2007
2. Dec 18, 2007