Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
Part (b) asks what value of k maximizes
C(k - 10, 18) ⋅ C(10, 2) / C(k, 20).
The answer given at the back of the text is k = 100, but I don't see how to arrive at that solution. I've tried expanding
C(k - 10, 18) / C(k, 20)
into
(k - 10)! / [(k - 28)! ⋅ 18!] ⋅ 20! ⋅ (k - 20)! / k!
but I still don't see how one can get k = 100 as the value that maximizes this. Could you explain why k = 100 maximizes this probability?
I spent some time last night thinking about this one. According to my calculations, this simplifies to
f(k) = 17,100 (k-20)(k-21)⋅⋅⋅(k-27) / [ k(k-1)(k-2)⋅⋅⋅(k-9)]
This is a rational function, roughly c/k2 for large k. This means that, if we can prove that f′(k) < 0 for k > some large K, we only have to look for the maximum between 0 and K. I've used a spreadsheet to convince myself that k=100 is the correct answer. I've also convinced myself that f′(k) is negative eventually. Alas, I have no elegant proof yet that k=100 is where f(k) is largest.
Maybe you could try the same sorts of things?
A student writes: I think that since k can only take on discrete numbers, it is enough to look at the when the ratio P(k) / P(k-1) > 1, where P(k) = C(10,2) · C(k-10,18) / C(k,20). (This is exactly when P(k) is increasing, as it is when P(k) > P(k-1).) Then P(k-1)=C(10,2) · C(k-11,18) / C(k-1,20), so we can find the largest value of k for which the ratio is greater than 1. This is when k=100, since the ratio can be written as P(k)/P(k-1) = 1 + (-2k+200)/(k2-28k).
I was just wondering if you could provide a hint for part (b).
Okay: how many 3-colourings does a circuit of 5 vertices have? Another hint: what does Pk(G) (the chromatic polynomial) represent?
What we're looking for is P4(G), where G is the graph given in 60(b). This is a complicated graph colouring problem — I needed to take cases twice.