       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

```

• Prev by Date: Re: k-permutations enumeration
• Next by Date: Re: ndsolve of coupled equation
• Previous by thread: Re: k-permutations enumeration
• Next by thread: Re: k-permutations enumeration