Re: k-permutations enumeration
- To: mathgroup at smc.vnet.net
- Subject: [mg116498] Re: k-permutations enumeration
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Thu, 17 Feb 2011 05:18:32 -0500 (EST)
I looked here and there, but didn't find a closed form or a built-in function. Here's a brute force method (probably a repeat of someone else's), followed by a minor simplification (I think) of a Dana DeLouis solution. (I needed to work it out both ways for my own benefit, and brute force was surprisingly fast, I thought.) Timing[v = {4, 5, 8, 3}; 15!/Times @@@ Factorial@ Select[Flatten[ Permutations /@ ReplaceRepeated[ IntegerPartitions[15, 4], {x__} /; Length@{x} < 4 :> {x, 0}], 1], And @@ Thread[# <= v] &] // Total] {0.007887, 187957770} or fx[v_, n_] := Module[{t}, t = Normal@Series[E^x, {x, 0, Max@v}]; t = Times @@ (Take[t, 1 + #] & /@ v); n! Coefficient[t, x, n] ] fx[{4, 5, 8, 3}, 15] // Timing {0.000743, 187957770} Bobby On Wed, 16 Feb 2011 03:32:26 -0600, Daniel Lichtblau <danl at wolfram.com> wrote: > Michal Kvasnicka wrote: >> Once again... is there any enumeration (closed form) formula? The >> problem looks like simple combinatorics problem, but I can not find >> any relevant formula. >> >> The above mentioned algorithms looks very good, but I am still looking >> for closed form formula. >> >> Michal >> > > I do not believe there is a closed form in the sense you are seeking. > The method/algorithm that looks like > Coefficient[Product[Sum[...]],...] > is, in some sense, a closed form. That is to say, there is a notation in > the literature for exactly this computation. But like any special > function, that does not imply the numeric computation will be trivial. > > Daniel Lichtblau > Wolfram Research > > -- DrMajorBob at yahoo.com