Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

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:

[tex] Z_{k,n}^l = Z_{k-1,n}^l.l + Z_{k-1,n}^{(l-1)}.(n-l+1) [/tex]

and boundary conditions:

[tex] Z_{k,n}^k = P^n_k = \frac{n!}{(n-k)!} [/tex]

(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:

[tex] Z_{k,n}^1 = n [/tex]

(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 [tex]\sum_{l=1}^k Z_{k,n}^l = n^k[/tex], 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Permutations with repetitions

**Physics Forums | Science Articles, Homework Help, Discussion**