- #1
- 5,102
- 20
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.
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: