4 ms·
>We take our set of d things. We colour one of them red. We colour one of them blue. Then we pick some set of the things (k in number), including the red thing
by krackers 2y ago
>We take our set of d things. We colour one of them red. We colour one of them blue. Then we pick some set of the things (k in number), including the red thing and the blue thing
In this alternate view of the process, where does the k^2 term come from? Isn't the number of ways to do it in this perspective just
(d-1 choose k-1) # We already chose the red one (which is also the blue) and need to choose k-1 more
+
(d-2 choose k-2) # We chose both red and blue ones and need to choose the other k-2
Edit: I think it actually works out, seems to be equal to
d * 1 * Binomial[d - 1, k - 1] + d * (d - 1) * Binomial[d - 2, k - 2] = Binomial[d, k]*k^2
And then you apply your argument about fixing one of the elements in each of the two cases. Actually the proof seems to be a variant (same core argument) as sum of even binomial terms = sum of odd binomial terms [1]
[1] https://math.stackexchange.com/questions/313832/a-combinatorial-proof-that-the-alternating-sum-of-binomial-coefficients-is-zero https://math.stackexchange.com/questions/313832/a-combinator...
- gjm11 2y agoIn the alternate view, the k^2 isn't there any more. Not because we are computing a different number, but because we're organizing the computation differently. (It's turned into a d^2 factor, except that we then need to treat the red=blue case differently from the red!=blue case, so it's really a d factor plus a d^2-d factor.) And yes, the last bit of the proof is exactly the same thing as one way to prove that the sum of "even" and "odd" binomial coefficients are equal -- provided n>0. (For the (0 choose whatever) case, the "even" sum is 1 and the "odd" sum is 0.)