Re: k-permutations enumeration

*To*: mathgroup at smc.vnet.net*Subject*: [mg116406] Re: k-permutations enumeration*From*: Dana DeLouis <dana.del at gmail.com>*Date*: Sun, 13 Feb 2011 05:50:33 -0500 (EST)

On Feb 10, 5:23 am, Michal Kvasnicka <michal.kvasni... at gmail.com> wrote: > How can I find the number of k-permutations of n objects, where there > are x types of objects, and r1, r2, r3 ... rx give the number of each > type of object? > > Example: > I have 20 letters from the alphabet. There are some duplicates - 4 of > them are a, 5 of them are b, 8 of them are c, and 3 are d. How many > unique 15-letter permutations can I make? > > In the example: > > n = 20 > k = 15 > x = 4 > r1 = 4, r2 = 5, r3 = 8, r4 = 3 > > Furthermore, if there isn't a straightforward solution: how > efficiently can this problem be solved? Any Mathematica code? Hi. Just an idea. This is the same algorithm as given by others, just re-worded fx[v_, n_] := Module[ {t}, t = Normal[Series[E^x, {x, 0, Max[v]}]]; (* Use what is already calculated *) t = Product[Take[t,v[[j]] + 1], {j, Length[v]}]; Coefficient[n!*t, x, n] ] fx[{4,5,8,3},15]//Timing {0.000753,187957770} = = = Dana DeLouis Mac Pro, V8=