There’s probably a simple answer to this, but I can’t get my head around it.
I was just playing around with some combinatorial problems (Google calculator rocks - type “32 choose 2” into the search box and it’ll calculate it for you…) and I was wondering what the following would be (excuse my pseudo-notation):
max ( [sub]n[/sub]C[sub]m[/sub] )
m=1…n
i.e., given n items, what is the number, chosen at one time, that maximizes the number of combinations? I noticed that it’s not monotonic increasing, which I would have thought intuitively, though dumbly since clearly [sub]n[/sub]C[sub]1[/sub] = n and [sub]n[/sub]C[sub]n[/sub] = 1.
The maximum value occurs when you choose half of the items, if there are an even number of items. If there are an odd number of items, the max value occurs at both of the integers “adjacent” to half of n.
In other words, if you have 100 items to choose from, choosing 50 (=100/2) gives the maximum value. If you have 101 items to choose from, the max occurs at both 50 and 51 (both “adjacent” to 101/2 = 50.5).
There is a simple answer, which you can probably figure out.
Think about it this way. Remember that [sub]n[/sub]C[sub]m[/sub]=n!/(m!(n-m)!), so consider the ratio [sub]n[/sub]C[sub]m[/sub] / [sub]n[/sub]C[sub]m-1[/sub]. Most of the terms in the factorials cancel out; you can work out the ratio pretty easily.
Now if this ratio is greater than one, then [sub]n[/sub]C[sub]m[/sub] > [sub]n[/sub]C[sub]m-1[/sub], so the sequence is still increasing. If it’s less than one, the sequence is decreasing; if it’s equal to one, then [sub]n[/sub]C[sub]m[/sub] = [sub]n[/sub]C[sub]m-1[/sub]. You’ll find that the ratio is monotonically decreasing; the crossover point will tell you where the maximum is reached.
Take a look at Pascal’s Triangle sometime. The nth row has the values of [sub]n[/sub]C[sub]0[/sub] through [sub]n[/sub]C[sub]n[/sub]. You’ll notice that the biggest numbers occur in the middle of each row.
You’ll also notice that each row is symmetrical. [sub]n[/sub]C[sub]k[/sub] = [sub]n[/sub]C[sub]n-k[/sub], which makes sense because picking which k objects do get chosen is equivalent to picking which n-k objects don’t get chosen.
I guess, on reflection, a little reasoning by symmetry would have got me the answer: for suppose the maximum were in one “half” or the other - 1 -> n/2 or (n/2 + 1) -> n. That would imply there’d have to be a corresponding maximum in the other side - the “mirror image”, so the curve would be a dromedary rather than a bactrian camel Actually, now I think about it, I think that argument just proves that if the maximum were not at m = n/2, then there’d have to be at least two maxima.
DarrenS, I can think of a couple of intuitive ways to interpret it:
Algebraicly, C(n,k) = n(n-1)(n-2)…(n-k+1) / k!
The numerator has k factors, each of which is at most n, so the numerator is at most n[sup]k[/sup].
Combinatorially, C(n,k) is the number of ways you can choose k objects from n objects. n[sup]k[/sup] is the number of ways you can choose k objects from n objects with repetition and with the order of the selection mattering, too. That can only make n[sup]k[/sup] bigger.
You got your camels mixed up. You Bastard would have corrected you on both points. (Or looked at you with a supercilious air and then spat in your eye.)
Actually, now I think about it, I think that argument just proves that if the maximum were not at m = n/2, then there’d have to be at least two maxima.