Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #15639 > unrolled thread

k-permutations enumeration

Started byMichal Kvasnicka <michal.kvasnicka@gmail.com>
First post2011-02-10 10:23 +0000
Last post2011-02-11 09:14 +0000
Articles 6 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  k-permutations enumeration Michal Kvasnicka <michal.kvasnicka@gmail.com> - 2011-02-10 10:23 +0000
    Re: k-permutations enumeration Michal Kvasnicka <michal.kvasnicka@gmail.com> - 2011-02-12 10:21 +0000
    Re: k-permutations enumeration Ray Koopman <koopman@sfu.ca> - 2011-02-11 09:12 +0000
    Re: k-permutations enumeration Daniel Lichtblau <danl@wolfram.com> - 2011-02-12 10:18 +0000
    Re: k-permutations enumeration Daniel Lichtblau <danl@wolfram.com> - 2011-02-12 10:19 +0000
    Re: k-permutations enumeration Ray Koopman <koopman@sfu.ca> - 2011-02-11 09:14 +0000

#15639 — k-permutations enumeration

FromMichal Kvasnicka <michal.kvasnicka@gmail.com>
Date2011-02-10 10:23 +0000
Subjectk-permutations enumeration
Message-ID<ij0eaq$9eo$1@smc.vnet.net>
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?

[toc] | [next] | [standalone]


#15688

FromMichal Kvasnicka <michal.kvasnicka@gmail.com>
Date2011-02-12 10:21 +0000
Message-ID<ij5muj$jn3$1@smc.vnet.net>
In reply to#15639
On Feb 11, 10:14 am, Ray Koopman <koopman@sfu.ca> wrote:
> On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni...@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?
>
> Please disregard my previous post, which counted only
> "words" containing all of the x different "letters".
>
> k = 15; r = {4,5,8,3};
> Tr[Multinomial@@@Select[Tuples[Range[0,#]&/@r],Tr@#==k&]]
>
> 187957770

Ooooh ... nice work!!! This is really very compressed mathematica
code.

Is there any chance to find general enumeration closed form for k-
permutation of multiset? Just
like following form for special case (k=n):
(r1+r2+...+rx)!/(r1!r2!... rx!), n=r1+r2+...rx.

Michal

[toc] | [prev] | [next] | [standalone]


#15729

FromRay Koopman <koopman@sfu.ca>
Date2011-02-11 09:12 +0000
Message-ID<ij2uii$7go$1@smc.vnet.net>
In reply to#15639
On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni...@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?

k = 15; r = {4,5,8,3};
Tr[Multinomial@@@Select[Tuples[Range/@r],Tr@#==k&]]

184984800

[toc] | [prev] | [next] | [standalone]


#15792

FromDaniel Lichtblau <danl@wolfram.com>
Date2011-02-12 10:18 +0000
Message-ID<ij5mpa$jif$1@smc.vnet.net>
In reply to#15639
Ray Koopman wrote:
> On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni...@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?
> 
> Please disregard my previous post, which counted only
> "words" containing all of the x different "letters".
> 
> k = 15; r = {4,5,8,3};
> Tr[Multinomial@@@Select[Tuples[Range[0,#]&/@r],Tr@#==k&]]
> 
> 187957770

Another approach is to use an exponential generating function. It seems 
to be fairly fast.

multvals = {4, 5, 8, 3};
select = 15;
factors = Map[summand[x, #] &, multvals];
Coefficient[Factorial[select]*Times @@ factors, x^select]

187957770

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [next] | [standalone]


#15879

FromDaniel Lichtblau <danl@wolfram.com>
Date2011-02-12 10:19 +0000
Message-ID<ij5ms9$jkv$1@smc.vnet.net>
In reply to#15639
Daniel Lichtblau wrote:
> Ray Koopman wrote:
>> On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni...@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?
>>
>> Please disregard my previous post, which counted only
>> "words" containing all of the x different "letters".
>>
>> k = 15; r = {4,5,8,3};
>> Tr[Multinomial@@@Select[Tuples[Range[0,#]&/@r],Tr@#==k&]]
>>
>> 187957770
> 
> Another approach is to use an exponential generating function. It seems 
> to be fairly fast.
> 
> multvals = {4, 5, 8, 3};
> select = 15;
> factors = Map[summand[x, #] &, multvals];
> Coefficient[Factorial[select]*Times @@ factors, x^select]
> 
> 187957770
> 
> Daniel Lichtblau
> Wolfram Research

Ray Koopman pointed out to me that I forgot to show the definition of 
summand. (He even provided me with a shorter variant, which I will use. 
How thoughtful.)

summand[x_,n_] := Sum[x^r/r!,{r,0,n}]

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [next] | [standalone]


#15887

FromRay Koopman <koopman@sfu.ca>
Date2011-02-11 09:14 +0000
Message-ID<ij2umh$7kn$1@smc.vnet.net>
In reply to#15639
On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni...@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?

Please disregard my previous post, which counted only
"words" containing all of the x different "letters".

k = 15; r = {4,5,8,3};
Tr[Multinomial@@@Select[Tuples[Range[0,#]&/@r],Tr@#==k&]]

187957770

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web