MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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=


  • Prev by Date: Finding inverse of non-linear transformation
  • Next by Date: Re: changing variable in an equation
  • Previous by thread: Re: k-permutations enumeration
  • Next by thread: Re: k-permutations enumeration