R help - Jun 2010 - [OT] Combinatorials wtih constraints

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 the twice (Q).

Are there well-known methods for identifying the number of possible combinations
with this kind of constraint?

Thanks,
Harold


	[[alternative HTML version deleted]]

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 ------------------------------