At least I think that’s what this is called. It’s math, anyway.
I know how to do nCr to find the number of distinct ways to choose r elements from a group of n. But what if two or more set members are the same? How do you calculate that? The particular problem I’m doing now is 11 c 7 from a group of A,A,B,C,D,E,F,G,H,I,J. But I’m really interested in the general formula. Thanks in advance.
For your specific problem you break it down into cases: i.e. there are 9 c 7 ways to do it without picking any A’s, 9 c 6 ways to do with choosing exactly one A, and 9 c 5 ways to do it choosing two A’s, so your answer is (9 c 7) + (9 c 6) + (9 c 5).
I’m not certain if there’s a more general formula.
Oh, and the word is “combinatorics”.
There is a general formula. The phrase to type into google is “distinguishable combinations”.
Um, ultrafilter, I just put that phrase into Google and got bupkiss. Lots of stuff about how to calculate, say, the number of permutations of n elements when some of the elements are indistinguishable (i.e., references to multinomial coefficients) but that doesn’t answer the OP.
I can’t think of any nice general formula that isn’t just a straightforward case-by-case analysis based on the make-up of the original set. I’d be happy to be proven wrong, but I don’t see the answer in any of the stuff I got from the Google search you suggested.
Maybe that’s not exactly it. I’ve got a book at home that should answer this, so I’ll check that out.
Yeah, turns out the book didn’t have what I want.
This is a tricky problem, and I’ve tried to figure it out before but got stymied. It’s equivalent to determining how many factors a number has given its prime factorization.
Perhaps Wendell Wagner can shed some light on the situation.
ultrafilter:
That problem is trivial, actually. Did you mean to say, “It’s equivalent to determining how many divisors with a set number of prime factors (not necessarily distinct) a number has given its prime factorization.”
In other words, for example, 12 = (2^2)3, has 32 = 6 factors (1, 2, 3, 4, 6, and 12), but we can also talk about the factors of 12 with, say,
Exactly zero prime factors: 1
Exactly one prime factor: 2 and 3
Exactly two prime factors: 4 and 6
Exactly 3 prime factors: 12
I think that’s what you meant to say. So the OP would be equivalent to having a number with a prime factorization such as:
(2^2) * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29
and asking how many divisors with exactly seven prime factors that number has.
The best and most general way I can think of for this type of problem is to use generating functions.
For the example in the OP, do it like this: For each distinct object, we need a polynomial of the form:
1 + x + x^2 + … + x^n,
where n is the number of times the object is repeated in the original group.
For example, for the OP’s problem, the polynomial for A would be:
1 + x + x^2
and the polynomials for B through J would each be
1 + x.
Multiply all your polynomials together to get your generating function:
(1 + x + x^2) * (1 + x)^9
Since we want to know how many ways to select seven objects, our answer is the coefficient of x^7 in our generating function (which is 246 if I didn’t screw that up).
Do you see how that works?
Yeah, that is what I meant to say.
I’m not all that familiar with generating functions, so I’ll have to take your word for this problem.