Re: [R] [OT] Combinatorials wtih constraints

From: Ted Harding <Ted.Harding_at_manchester.ac.uk>
Date: Thu, 24 Jun 2010 21:53:03 +0100 (BST)


On 24-Jun-10 19:47:38, Doran, Harold wrote:
> This is not an R question, but a question on some combinatorial
> mathematics. Apologies for the OT if it is wildy inappropriate.
> The traditional C(n.k) method tells me how many combinations k
> I can make with n objects. However, suppose I want the number of
> combinations where an object cannot be used more than Q times
> where Q is a parameter that changes?
>
> For instance:
>
> combn(LETTERS[1:5], 3)
>
> shows the number of triplets I can make with the 5 letters.
> But, suppose I want the constraint that no letter can be used
> more than twice (Q).
>
> Are there well-known methods for identifying the number of possible
> combinations with this kind of constraint?
>
> Thanks,
> Harold

I think there is some confusion in the statement of the problem. "C(n,k)" gives the number of ways of choosing k distinct objects out of n distinct objects, so there is no repetition of an object in any of the selections of k objects. This can be observed in the result of your "combn(LETTERS[1:5], 3)" command:

combn(LETTERS[1:5], 3)

#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,] "A"  "A"  "A"  "A"  "A"  "A"  "B"  "B"  "B"  "C"  
# [2,] "B"  "B"  "B"  "C"  "C"  "D"  "C"  "C"  "D"  "D"  
# [3,] "C"  "D"  "E"  "D"  "E"  "E"  "D"  "E"  "E"  "E"  

So no letter is used more than once, let alone more than twice, so it is maximally constrained!

Is it the case that your question is

  In how many ways can we choose k objects out of n distinct   objects, with repetition allowed, but with no more than Q   replicates of any object in the selection?

If so, I'm not sure whether there is an R function which will handle it directly, and as a combinatorial problem it is one where you can quite easily drop stitches; so if there isn't one I'll wait for confirmation before thinking about how to implement it in R!

There may be some mileage in the 'partitions' package, see e.g.

http://finzi.psych.upenn.edu/R/library/partitions/html/ partitions.package.html

but I think one would need to experiment with it a bit in order to be sure what the functions do.

Ted.



E-Mail: (Ted Harding) <Ted.Harding_at_manchester.ac.uk> Fax-to-email: +44 (0)870 094 0861
Date: 24-Jun-10                                       Time: 21:51:49
------------------------------ XFMail ------------------------------

______________________________________________
R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Thu 24 Jun 2010 - 20:56:12 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Thu 24 Jun 2010 - 21:20:36 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive