Combinatorics:
I know that to calculate the number of combinations of $$k$$ elements chosen from a set of $$n$$, you use the binomial coefficient $$C(n,k)={n!\over {k!(n-k)!}}$$
But if the set contains more times the same element, how then? I men what if I want to know the combinations of four letters from the set {A,A,A,A,B,B,B,C,C,D} ?

Question

Combinatorics:
I know that to calculate the number of combinations of $$k$$  elements chosen from a set of $$n$$, you use the binomial coefficient $$C(n,k)={n!\over {k!(n-k)!}}$$
But if the set contains more times the same element, how then? I men what if I want to know the combinations of four letters from the set {A,A,A,A,B,B,B,C,C,D} ?

anonymous · Answer

I know that in permutations (if n = k), you just divide by the product of the factorials of the number of repeated elements. in the case it would be:
$$10! \over {5!4!3!2!1}$$
But, what about combinations?

anonymous · Answer

(if k<n)

kinggeorge · Answer

As far as I know there's no easy formula for this kind of problem.

amistre64 · Answer

does combination mean that order is important? or not important?

kinggeorge · Answer

Basically, you're asking how many unique subsets of multisets exist. As far as I can tell, there's no formula to do that.

anonymous · Answer

I was wrong, terribly sorry. The order does _not_ matter.
If n = k you get 1, even if you have n! permutations.

anonymous · Answer

Even if there isn't a formula, how would you solve the specific case {A,A,A,A,B,B,B,C,C,D}?

kinggeorge · Answer

For this example (which is small enough) I would do a case by case analysis. Not pretty, but it gets the job done.

kinggeorge · Answer

Perhaps fool can impart some wisdom on us.

anonymous · Answer

Hmm, there are two ways to approach this one. 

First, somewhat tedious case analysis which is somewhat error prone.

Second, using a generating function.

PS: You forgot to mention 'distinct' in your definition of $ \large \binom nk $

anonymous · Answer

well, how would you solve this?

amistre64 · Answer

in combo abba = baba = aabb = etc ... and are only counted once, if i recall correctly

anonymous · Answer

Yeah, you're right.

amistre64 · Answer

could we simplified the set to {a,b,c,d} if they represent doubled elements?

anonymous · Answer

I don't think so. ABBA is a valid combination. You can't get that from your set.
Anyway, C(10,4) = 210.
The number of those with 2 A are
C(8,2) = 28, so I subtract 14.
Could I go on like this?

anonymous · Answer

I don't really think so...

amistre64 · Answer

aaaa = 1

aaab = 4
aaac = 4
aaad = 4

aabb = 6
aacc = 6

bbbc = 4
bbcc = 6

bbbd = 4

ccd = 0

d = 0

i think i sorted them right

amistre64 · Answer

abbb = 4  forgot that one

kinggeorge · Answer

It looks like a case-by-case analysis you're starting, so you could continue how you started, but I think you calculated the number of sets with 2 a's incorrectly.

amistre64 · Answer

looks to me like there are 10 different set that can be formed by your example

anonymous · Answer

It really looked like a simple problem... That's disappointing, Math.

amistre64 · Answer

opps, 6 different sets :)  forgot how to count

kinggeorge · Answer

similar to Fool's generating function idea, you could make a recurrence relation to solve this problem.

anonymous · Answer

I love recursion, but really have no idea how to use it here.

kinggeorge · Answer

It's not a very nice problem.

kinggeorge · Answer

If you want more information on multisets however, wikipedia has a great page on them http://en.wikipedia.org/wiki/Multiset

anonymous · Answer

If I find out a general formula I'll let you know.
It really seems kind of easy.