Permutations with repetitions

[vanesch]

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.

 

[Aztral]

Hello,

I'm working a problem (https://www.physicsforums.com/showthread.php?t=204892) and I'm wondering if this might not be of help.

Did you ever find the answer to your question?

 

[tacman]

Hi Patrick,

Thank you for bringing up this interesting topic. Permutations with repetitions are indeed a well-studied concept in mathematics and have applications in various fields such as combinatorics, statistics, and computer science. The quantity you are looking for, Z_{k,n}^l, is known as the number of k-permutations with repetition from a set of n elements with exactly l different elements.

As you have mentioned, there is no standard notation for this quantity, but it is commonly denoted as P_{k,n}^l or P(n,k,l). There are various ways to derive a recursive formula for this quantity, and the one you have found is correct. However, there is no known closed-form expression for P_{k,n}^l, and it is often calculated using generating functions or algorithms.

One approach to calculating P_{k,n}^l is through generating functions, which are used to represent a sequence of numbers as a polynomial. In this case, the generating function for P_{k,n}^l is given by:

G(x) = \sum_{k=0}^{\infty} P_{k,n}^l x^k = \frac{x^l}{(1-x)^l} \cdot \frac{(1+x)^{n-l}}{(1-x)^{n-l}}

By expanding this generating function, we can obtain a recurrence relation that is similar to the one you have found. However, this approach does not give a closed-form expression for P_{k,n}^l.

Another approach is through algorithms, such as the one you have mentioned using Mathematica. These algorithms can efficiently calculate P_{k,n}^l for large values of n and k. However, they do not provide an explicit formula for P_{k,n}^l.

In conclusion, while there is no known closed-form expression for P_{k,n}^l, there are various methods to calculate it efficiently. I hope this helps answer your question. Thank you for your contribution to this topic and for sparking this discussion.

Best regards,