# Identity in surjective functions from N to X, up to a permutation of N

I'm studying the combinatorics "twelvefold way", and found an identity that cannot explain myself.
The case, $${x-1 \choose b-1}$$ as far as I understand is derived the following way: $${(x-b)+b-1 \choose x-b}={x-1 \choose x-b}={x-1 \choose b-1}$$ The first identity is evident, but I don't understand the second one: $${x-1 \choose x-b}={x-1 \choose b-1}$$ Why x-b is equal to b-1?

Thanks

-

For any $n$ and $k$, $$\binom{n}k=\binom{n}{n-k}\;;$$ let $n=x-1$ and $k=b-1$, and you immediately get $$\binom{x-1}{b-1}=\binom{x-1}{x-b}\;,$$ since $(x-1)-(b-1)=x-b$. This does not mean that $b-1=x-b$; in general this is false.

There are at least two ways to see the identity $$\binom{n}k=\binom{n}{n-k}\;.$$ If you know that $$\binom{n}k=\frac{n!}{k!(n-k)!}\;,$$ it’s clear:

$$\binom{n}{n-k}=\frac{n!}{(n-k)!\big(n-(n-k)\big)!}=\frac{n!}{(n-k)!k!}=\binom{n}k\;.$$

Alternatively, if you know that $\binom{n}k$ is the number of $k$-element subsets of $\{1,\dots,n\}$, just observe that complementation is a bijection between $k$-element subsets and $(n-k)$-element subsets, so $\binom{n}k$ and $\binom{n}{n-k}$ must be equal.

-

It is not that $x-b$ is equal to $b-1$ but rather the following. Fix $n=x-1$ and $r=b-1$ for notation purpose.

The number of ways to choose $r$ objects from a set of $n$ is given by the binomial coefficient $$n\choose r$$ However, choosing $r$ is the same as chossing which $n-r$ will be left out, so $${n\choose r}={n\choose{n-r}}.$$ Substitute your values back to get $${{x-1}\choose{b-1}}={{x-1}\choose{x-1-(b-1)}}={{x-1}\choose{x-b}}.$$

Of course, you can also prove this identity with the definition, but the combinatorial way of seeing it is, I believe, more convincing.

Edit

One has to be careful in the case $n=b=0$ The rightmost part will give the correct answer of $1$ (correct given the context of surjective maps, while the left most term will give ${-1\choose-1}$, which is not well defined.

-
@Brian M. Scott and Jean-Sébastien Thank you very much for your kind and complete explanations. There is just one more thing left: numerically $${x-1 \choose x-b}$$ is not the same as $${x-b \choose b-1}$$ if I replace directly the values x and b. For example, let x=10 and b=5 $${9 \choose 5}$$ is not the same as $${9 \choose 4}$$ Therefore, should I use just $${x-1 \choose b-1}$$ ???. Thanks again – Diego Oct 26 '12 at 22:09
the upper part of the binomial coefficient remains the same, its the lower part that changes – Jean-Sébastien Oct 26 '12 at 22:13
@Diego Look at what I and Brian have done carefully, you'll see what the relation is ${n\choose r}={n\choose{n-r}}$ – Jean-Sébastien Oct 26 '12 at 22:15
Thank you. That's the point, I mean, being an identity I'd expect to be able to use any side of it with confidence that the result will be the same. But in this particular case that does not happen. – Diego Oct 26 '12 at 22:17
I added something that needs to be considered – Jean-Sébastien Oct 26 '12 at 22:20

In general, ${n\choose k}={n\choose n-k}$.

-
I just saw your second message. Yes I have look at it, and I understand it and appreciate it. My comment is just directed to highlight the numerical difference between the 2 sides of the identity, that was the reason I got confused in the first place. But yeah, I got your explanation and I'm very happy with it. :) – Diego Oct 26 '12 at 22:20

I finally understood this through the "stars and bars" approach and the case $${𝑥+𝑏−1 \choose 𝑥}$$ which is simpler.

Let x=10 (dots) and b=5 (subsets) (b-1= 4 bars)
$$..|...|..|..|.$$ So if I focus on the subsets the answer will be $${14 \choose 4}$$ But if I focus on the dots the answer will be $${14 \choose 10}$$
I had to toss a coin for choosing the accepted answer :)
Thank you very much Brian and Jean

Since somebody can find this post useful, I post the results obtained by using Pascal's triangle for the same problem, which I believe can complement the nice explanation provided by Brian and Jean.

-