Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #15639 > unrolled thread
| Started by | Michal Kvasnicka <michal.kvasnicka@gmail.com> |
|---|---|
| First post | 2011-02-10 10:23 +0000 |
| Last post | 2011-02-11 09:14 +0000 |
| Articles | 6 — 3 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
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
| From | Michal Kvasnicka <michal.kvasnicka@gmail.com> |
|---|---|
| Date | 2011-02-10 10:23 +0000 |
| Subject | k-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]
| From | Michal Kvasnicka <michal.kvasnicka@gmail.com> |
|---|---|
| Date | 2011-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]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-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]
| From | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| Date | 2011-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]
| From | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| Date | 2011-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]
| From | Ray Koopman <koopman@sfu.ca> |
|---|---|
| Date | 2011-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