Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #15792
| From | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| Newsgroups | comp.soft-sys.math.mathematica |
| Subject | Re: k-permutations enumeration |
| Date | 2011-02-12 10:18 +0000 |
| Organization | Steven M. Christensen and Associates, Inc and MathTensor, Inc. |
| Message-ID | <ij5mpa$jif$1@smc.vnet.net> (permalink) |
| References | <ij0eaq$9eo$1@smc.vnet.net> <201102110914.EAA07802@smc.vnet.net> |
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
Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web