Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm not a native speaker of English. I usually pride myself of my proficiency, but I think I may be stumped here. My problem arises out of this question, which among other things asked for a combinatorial proof of the identity

$$\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$$

(Equation shown only to provide context. I know how to prove this. I've written an answer. That's not the problem.) Another answer, however, provided a hint that reads in its entirety:

Hint. If I have a group of J objects, and I want to see how many ways I can count K of them, I can either do this by taking $J \choose K$ or by counting how many ways I can choose 1, or 2, or 3, or 4, ..., or K of them.

This hint received upvotes, which I consider empirical proof that it is not simply nonsense. My problem is that the hint makes no sense to me. I find this particularly distressing because its author claims that the solution it was a hint for is the same solution I gave in my answer -- but still I can't figure out what the hint even means.

What confuses me is the phrasing "how many ways I can count K of them". This conveys no meaning to me -- what does it mean to "count K of them"? What does a way to count K of them constitute, such that we can speak of how many such ways there are?

I'm fairly certain that "count _ of _" is not a standard mathematical concept with a technical meaning, so I'm assuming that it is an everyday English phrasing whose ordinary meaning I'm simply unfamiliar with. I'm asking because I suspect it may hint at a combinatorial shortcut that I don't know, which I'd like to add to my toolbox.

Yes, I did ask directly as in a comment to the answerer, but apparently I was unable to convince the answerer that I was asking for mere linguistic clarification rather than demanding additional technical details in the hint, and the discussion got a bit heated, and perhaps some fresh eyes will be better able to find a way to express whichever obvious thing I'm missing in a way that will penetrate my skull.

I think I have eliminated the possibility that the hint merely says that $\binom JK$ is one way to count K of them and there's another way involving "1, or 2, or 3, or 4, ... or K" plus possibly other different but irrelevant ways. I have also eliminated a theory that "count K of them" was a typo for "choose K of them". Beyond that I'm drawing blanks.

share|improve this question
3  
On looking again, I must say I do find the linked answer incomprehensible too. –  ShreevatsaR Sep 24 '11 at 4:50
2  
@ShreevatsaR: One of the few explicit clarifications I could get out of the answerer was that he did mean count not choose. It's a high-rep user who I don't think would normally have a problem with saying "oops, that's a typo" or "yeah, that was confusingly worded" if that were actually the case. So I'm assuming there's actually something to it and the problem is at my end. –  Henning Makholm Sep 24 '11 at 5:02
3  
Would the people who have voted to close speak up, please? I vote against closing. –  J. M. Sep 24 '11 at 5:28
3  
Under no circumstance would I ever expect an author to answer an email within 45 minutes. So when I read this question, I read it as a premature extension of a conversation between us. And let us suppose there is an answer: I would also suppose that I, as the person who wrote the offending passage, would be the one to give it? So ultimately, I find it very surprising that although I gave no indication that I would stop responding, you would post this here. I would also like to note that I voted to close, as I find this abrupt and a bit offensive. –  mixedmath Sep 24 '11 at 5:43
3  
@mixedmath, I suppose there is some criticism implicit in taking the question here. But I really did want to know what the hint was supposed to mean, and the 30+ comments we had already exchanged made it abundantly clear that I was not going to get you to tell me. Even now, it appears that you still think I was being rhetorical (i.e. that I understood the hint but was complaining about how you chose to present it), when the naked honest truth is that I did not understand what you were saying. What's one supposed to do then? –  Henning Makholm Sep 24 '11 at 14:33

3 Answers 3

up vote 4 down vote accepted

The idea of the hint was that if you want to select $n$ objects out of $x+n+1$, you could have selected $k$ out of the first $x+k,$ then skip the next, then take all the rest. To get the total you have to sum over the allowable $k$'s. I think select (or choose) is a better verb in this case. To me, count would be to count the number of ways to select a set of objects subject to the given condition.

share|improve this answer

The hint in question makes no sense as written. If one knows the combinatorial argument suggested here by Ross and André, which is essentially the one offered by Henning for the other question, one might suspect that the author of the hint had something like it in mind, but I don’t see how one could be sure. It doesn’t even make sense if select or choose is substituted for count, since one cannot select $K$ objects by selecting at most $K$ of them

share|improve this answer

Something connected with the hint can be made to work.

We have the $x$ negative numbers $-x$ to $-1$, together with the $n+1$ numbers $0$ to $n$. We want to choose $n$ numbers from these $x+n+1$ numbers. There are $\binom{x+n+1}{n}$ such choices.

Another way to do the choosing is to first pick a $k$ from $0$ to $n$. Let $\mathbb{C}_k$ be the collection of all sets $S$ of $n$ of our numbers such that:

(i) $S$ contains all numbers from $k+1$ to $n$;

(ii) $S$ does not contain the number $k$.

Then the collection of all choices of $n$ numbers is the disjoint union of the $\mathbb{C}_k$.

If $S\in \mathbb{C}_k$, then $S$ consists of the $n-k$ numbers from $k+1$ to $n$, together with any $k$ numbers chosen from the $x+k$ numbers $-x$ to $k-1$. Thus $\mathbb{C}_k$ has $\binom{x+k}{k}$ elements. Add up, $k=0$ to $n$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.