Re: k-permutations enumeration
- To: mathgroup at smc.vnet.net
- Subject: [mg116383] Re: k-permutations enumeration
- From: Michal Kvasnicka <michal.kvasnicka at gmail.com>
- Date: Sat, 12 Feb 2011 05:21:17 -0500 (EST)
- References: <ij0eaq$9eo$1@smc.vnet.net> <ij2umh$7kn$1@smc.vnet.net>
On Feb 11, 10:14 am, Ray Koopman <koopman at sfu.ca> 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 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