Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations with repetitions

  1. May 3, 2007 #1

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:
    [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.
     
    Last edited: May 3, 2007
  2. jcsd
  3. Dec 18, 2007 #2
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?