I’m generally pretty good at counting problems … combinations, permutations, etc., but I can’t figure out how to solve this one.
Let’s say you have m letter As and n letter Bs. How many distinct strings (of m+n length) can you make?
For example, 3 As and 2 Bs
AAABB, AABAB, AABBA, ABAAB, ABABA, etc.
(m+n)!/(m! * n!). Aka, nCr(m+n, m) = nCr(m + n, n). The number of ways to choose m out of m + n; equivalently, the number of ways to choose n out of m + n.
The idea is, you can completely describe such a string by saying which, out of the m + n many letters in total, are the particular m many which are As (equivalently, the particular n many which are Bs).
Yes, I get that, although it took me a few minutes to parse your explanation. Out of the m+n possible positions in the string, you have to choose m of them to be As, so (m+n) choose m is the answer. Thanks!
I believe it is (m+n)!/m!n!
You have m+n things, so there are (m+n)! permutations of them, but since the things aren’t distinct, several different permuations differ only in the arrangement of the non-distinct items relative to each other. So you divide by the number of ways of permuting the A’s relative to each other (m!) and the number of ways of arranging the B’s (n!)
So for 3 A’s and 2 B’s, you get 5!/3!2! = 120/6*2 = 10 distinct arrangements
Yes, Manduck, that’s right too. You’re just going a step further and deriving the formula for “n choose m”, aka nCr … or in this case n+m choose m.