Answer: Combinations Problem: 40 Elements, 20 Identical - How Many Orderings?

[Zorba]

Suppose I have a set containing 40 elements, 20 of these elements are identical, and the 20 other are identical. Suppose an ordering is some list of all elements of this set, how many different orderings are there?

These types of questions were never my forte and I have no idea how to go about it.

 

[Filip Larsen]

If we call the elements for A and B, then one particular ordering would look something like the pattern AABAAABBABABA...A such that there is 20 of each A and B, and you would like to know how to count how many of such different orderings there are.

Try first think about what constitutes a different ordering. Would you get a different ordering if you swap two A's? two B's? an A and a B? If we assume you conclude you can swap two A's and two B's (but not an A and B) without getting a different ordering, then think about how you can give a "minimal" description of one particular ordering such that your description would be different exactly when the pattern would be different. For instance, think how, in as few words as possible, you would tell a friend over the phone such that he could write down the same pattern you have. Hint: you may want to try think of the 20 A's and B's as as a stack of cards, say 20 black and 20 red, that have to be interleaved (i.e. shuffled without reordering).

Once you have such a minimal description think about how you can use this to calculate the number of different descriptions, which then would be the same as the number of different pattern orderings.

 

[Martin Rattigan]

Alternatively notice that once you've chosen places for the A's, the B's have to go in the places that are left. The number of of sequences can therefore be described as the number of ways of choosing 20 out of the 40 places to put the A's.

It's most efficient to calculate once a formula for the number of ways of choosing r things from n and then use it wherever it applies.

There are many places where you can find this formula derived. E.g. http://betterexplained.com/articles/easy-permutations-and-combinations/.

 

[Filip Larsen]

Alternatively notice that once you've chosen places for the A's, the B's have to go in the places that are left. The number of of sequences can therefore be described as the number of ways of choosing 20 out of the 40 places to put the A's.

Apparently I did not do a very good job in my post because this is exactly what I was hinting at. So please don't get confused trying to figure out in what way the above is an "alternative" to what I was saying.

 

[Martin Rattigan]

I would suspect it's more my comprehension of normal English.

What I wanted to say was that rather than going through the calculation of ⁿC_r in each situation (and I thought you were suggesting that OP did in this situation) it's better to calculate ⁿC_r once and then use it thereafter.

Admittedly the number of sequences of As and Bs of length n that contain A r times is trivially the same as the number of ways of choosing r things from n, but thinking of this number as the number of ways of choosing r things from n is probably intuitively easier to apply in most situations than thinking of it as the former.

The difference, as you say, is at least marginal.