Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: k-permutations enumeration

  • To: mathgroup at smc.vnet.net
  • Subject: [mg116376] Re: k-permutations enumeration
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sat, 12 Feb 2011 05:20:00 -0500 (EST)
  • References: <ij0eaq$9eo$1@smc.vnet.net> <201102110914.EAA07802@smc.vnet.net> <4D55A228.1070908@wolfram.com>

Daniel Lichtblau wrote:
> Ray Koopman wrote:
>> On Feb 10, 2:23 am, Michal Kvasnicka <michal.kvasni... at 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


  • Prev by Date: Re: new Graph function + combinatorica: various problems
  • Next by Date: Re: Apply a rule to an expression only once
  • Previous by thread: Re: k-permutations enumeration
  • Next by thread: Re: k-permutations enumeration