Maybe we're confused about your question.... Actually, I just reread it and came up with a different, much more interesting, interpretation. Perhaps you want to compute the number of possible choices under a few constraints, rather than actually writing a program that simulates making those choices.
Originally Posted by gordoncom
Given n objects to bet on and k of those objects to select, there are (n choose k) different possible ways to make those selections. You gave the n=4, k=2 example (AB, AC, AD, BC, BD, CD) in your first post; there are 6 = (4 choose 2) of them. Here, "n choose k" is the binomial coefficient. It can be calculated using many libraries, or you could write your own function. The formula is...
Note that 4 choose 2 = 4*3 / [2*1] = 6.
(n choose k) = n*(n-1)*...*(n-(k-1)) / [k*(k-1)*...*2*1]
Now, suppose that m of the original objects are taken away. Here your question becomes fuzzy again. What precisely do you want to calculate? "I need to be able to compute the changed multiples ie doubles trebles singles"--how many q-element selections are left, for each q between 1 and k? Distinct or not? For instance, with n=4, k=2, m=2, we can simulate the process by removing AB from ABCD:
AB -> empty
AC -> C
AD -> D
BC -> C
BD -> D
CD -> CD
So, for q=1, we have C or D (though these both occur twice; does that matter?), and for q=2 we have only CD. Wrapping this all up in a function f(n, k, m, q), we have f(4, 2, 2, 2) = 1 and f(4, 2, 2, 1) = 2 (or 4?). And you want a general formula for f so you don't have to brute force the situation? Let me think....
It boils down to picking a final arrangement after the objects are taken away and figuring out how many initial arrangements turn in to that final arrangement. Given a length q final arrangement, length k initial arrangements have to take away (k-q) objects just to get the length right. These of course must be chosen from the m total objects which get taken away. In all, (m choose k-q) initial arrangements hit the same final arrangement.
How many length q final arrangements are there? They must be chosen from the n-m remaining objects, so there are (n-m choose q) of them. The explicit form of f is then either
f_nodup(n, k, m, q) = (n-m choose q)
f_dup(n, k, m, q) = (n-m choose q) * (m choose k-q)
As a sanity check, try the n=5, k=3, m=2 case, again removing AB:
ABC -> C
ABD -> D
ABE -> E
ACD -> CD
ACE -> CE
ADE -> DE
BCD -> CD
BCE -> CE
BDE -> DE
CDE -> CDE
=> f_nodup(5, 3, 2, 1) = 3 [C, D, E]
=> f_dup(5, 3, 2, 1) = 3 [each appears once]
=> f_nodup(5, 3, 2, 2) = 3 [CD, CE, DE]
=> f_dup(5, 3, 2, 2) = 6 [each appears twice]
=> f_nodup(5, 3, 2, 3) = 1 [CDE]
=> f_dup(5, 3, 2, 3) = 1 [each appears once]
[I checked, and my formulae agree.]
Finally, a nice mathy point. When counting with duplicates, each initial arrangement was included precisely once, which gives us a roundabout method to compute the number of initial arrangements. Since this is by definition (n choose k), we have the formula
I just looked it up, and this is (the most important special case of a slightly rearranged version of) Vandermonde's identity. It was apparently known to a 14th century Chinese mathematician. The calculations above resulting in this formula constitute what's known as a combinatorial proof.
(n choose k) = sum for q from 0 to m of (n-m choose q) * (m choose k-q)