9
$\begingroup$

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.

  • 0
    @Henning: It is not the desire to understand that is my problem. It is that doing so impatiently is. And in a manner which I find offensive.2011-09-24

3 Answers 3

1

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$.

6

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

4

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.